Brahmagupta-Fibonacci Identity/Extension

From ProofWiki
Jump to navigation Jump to search

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 \left({ {a_j}^2 + m {b_j}^2}\right) = 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$