Brahmagupta-Fibonacci Identity/Extension
Contents
Extension to Brahmagupta-Fibonacci Identity
Let $a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$ be integers.
Then:
- $\displaystyle \prod_{j \mathop = 1}^n \paren { {a_j}^2 + {b_j}^2} = c^2 + d^2$
where $c, d \in \Z$.
That is: the product of any number of sums of two squares is also a sum of two squares.
General Version
Let $a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n, m$ be integers.
Then:
- $\displaystyle \prod_{j \mathop = 1}^n \paren { {a_j}^2 + m {b_j}^2} = c^2 + m d^2$
for some $c, d \in \Z$.
That is: the set of all integers of the form $a^2 + m b^2$ is closed under multiplication.
Proof 1
From the extension to the general Brahmagupta-Fibonacci Identity:
- $\displaystyle \prod_{j \mathop = 1}^n \paren { {a_j}^2 + m {b_j}^2} = c^2 + m d^2$
for some $c, d \in \Z$, for all $m \in \Z$.
The result follows by setting $m = 1$.
$\blacksquare$
Proof 2
The proof proceeds by induction.
For all $n \in \Z_{> 0}$, let $P \left({n}\right)$ be the proposition:
- $\displaystyle \prod_{j \mathop = 1}^n \left({ {a_j}^2 + {b_j}^2}\right) = c^2 + d^2$
for some $c, d \in \Z$.
$P \left({1}\right)$ is the trivial case:
| \(\displaystyle \prod_{j \mathop = 1}^1 \left({ {a_j}^2 + {b_j}^2}\right)\) | \(=\) | \(\displaystyle {a_1}^2 + {b_1}^2\) | |||||||||||
| \(\displaystyle \) | \(=\) | \(\displaystyle c^2 + d^2\) | setting $c = a_1$ and $d = b_1$ |
Thus $P \left({1}\right)$ is seen to hold.
Basis for the Induction
$P \left({2}\right)$ is the case:
| \(\displaystyle \prod_{j \mathop = 1}^2 \left({ {a_j}^2 + {b_j}^2}\right)\) | \(=\) | \(\displaystyle \left({ {a_1}^2 + {b_1}^2}\right) \left({ {a_2}^2 + {b_2}^2}\right)\) | |||||||||||
| \(\displaystyle \) | \(=\) | \(\displaystyle \left({a_1 a_2 + b_1 b_2}\right)^2 + \left({a_1 b_2 - b_1 a_2}\right)^2\) | Brahmagupta-Fibonacci Identity | ||||||||||
| \(\displaystyle \) | \(=\) | \(\displaystyle c^2 + d^2\) | setting $c = a_1 a_2 + b_1 b_2$ and $d = a_1 b_2 - b_1 a_2$ |
Thus $P \left({2}\right)$ is seen to hold.
This is the basis for the induction.
Induction Hypothesis
Now it needs to be shown that, if $P \left({k}\right)$ is true, where $k \ge 2$, then it logically follows that $P \left({k + 1}\right)$ is true.
So this is the induction hypothesis:
- $\displaystyle \prod_{j \mathop = 1}^k \left({ {a_j}^2 + {b_j}^2}\right) = c^2 + d^2$
for some $c, d \in \Z$.
from which it is to be shown that:
- $\displaystyle \prod_{j \mathop = 1}^{k + 1} \left({ {a_j}^2 + {b_j}^2}\right) = c^2 + d^2$
for some $c, d \in \Z$.
Induction Step
This is the induction step:
| \(\displaystyle \prod_{j \mathop = 1}^{k + 1} \left({ {a_j}^2 + {b_j}^2}\right)\) | \(=\) | \(\displaystyle \prod_{j \mathop = 1}^k \left({ {a_j}^2 + {b_j}^2}\right) \left({ {a_{k + 1} }^2 + {b_{k + 1} }^2}\right)\) | |||||||||||
| \(\displaystyle \) | \(=\) | \(\displaystyle \left({ {c'}^2 + {d'}^2}\right) \left({ {a_{k + 1} }^2 + {b_{k + 1} }^2}\right)\) | Induction Hypothesis: for some $c', d' \in \Z$ | ||||||||||
| \(\displaystyle \) | \(=\) | \(\displaystyle c^2 + m d^2\) | Basis for the Induction: for some $c, d \in \Z$ |
So $P \left({k}\right) \implies P \left({k + 1}\right)$ and the result follows by the Principle of Mathematical Induction.
Therefore, for all $n \in \Z_{> 0}$:
- $\displaystyle \prod_{j \mathop = 1}^n \left({ {a_j}^2 + {b_j}^2}\right) = c^2 + d^2$
for some $c, d \in \Z$.
$\blacksquare$
Proof 3
Let $z_1 = a_1 + i b_1, z_2 = a_2 + i b_2, \ldots, z_n = a_n + i b_n$.
Let $c + i d = z_1 z_2 \cdots z_n$.
Then:
| \(\displaystyle c + i d\) | \(=\) | \(\displaystyle z_1 z_2 \dotsm z_n\) | |||||||||||
| \(\displaystyle \) | \(=\) | \(\displaystyle \paren {a_1 + i b_1} \paren {a_2 + i b_2} \dotsm \paren {a_n + i b_n}\) |
As $a_1, a_2, \dotsc, a_n$ and $b_1, b_2, \dotsc, b_n$ are positive integers, then so are $c$ and $d$.
Thus:
| \(\displaystyle c^2 + d^2\) | \(=\) | \(\displaystyle \cmod {z_1 z_2 \ldots z_n}^2\) | Definition of Complex Modulus | ||||||||||
| \(\displaystyle \) | \(=\) | \(\displaystyle \cmod {z_1}^2 \cmod {z_2}^2 \dotsm \cmod {z_n}^2\) | Complex Modulus of Product of Complex Numbers: General Result | ||||||||||
| \(\displaystyle \) | \(=\) | \(\displaystyle \cmod {a_1 + i b_1}^2 \cmod {a_2 + i b_2}^2 \dotsm \cmod {a_n + i b_n}^2\) | |||||||||||
| \(\displaystyle \) | \(=\) | \(\displaystyle \paren { {a_1}^2 + {b_1}^2} \paren { {a_2}^2 + {b_2}^2} \dotsm \cmod { {a_n}^2 + {b_n}^2}\) | Definition of Complex Modulus | ||||||||||
| \(\displaystyle \) | \(=\) | \(\displaystyle p_1 p_2 \dotsm p_n\) |
$\blacksquare$
