Suppose a number N can be written as P times Q times R times..., where all of P, Q, R... can each be written as the sum of two perfect nonzero squares.

Show that in this case N itself can also be written as the sum of two perfect squares.

We denote N = A_1*A_2*.... for simplicity rather than

N = P*Q*R.......

Let us denote, N_t = Prod(j=1 to t) A_j, where A_j= p_j^2 + q_j^2

for all j = 1,2,...,t

Now, N_1*N_2

= (p_1^2+q_1^2)((p_2^2+q_2^2)

= A^2 + B^2, where:

(A, B) = [(p_1*p_2 +q_1*q_2), |p_1*q_2 - p_2*q_1|]

Or, [|p_1*p_2 -q_1*q_2|, (p_1*q_2 + p_2*q_1)]

Thus, the result is true for t=2

Let the result be true for t=s

We know that A_(s+1) = p_(s+1)^2 + q_(s+1)^2

Letting N_s = C^2 + D^2, it can be easily proved as before that:

N_(s+1) = E^2 + F^2, where

(E, F) = (C*p_(s+1)+ D*q_(s+1)), |C*q_(s+1) - D*p_(s+1)|]

Or, [|C*p_(s+1)- D*q_(s+1)|, (C*q_(s+1) + D*p_(s+1)]

Thus, the result is also true for t=s+1

Consequently, the product N will always be expressible as the sum of two squares.

*Edited on ***May 18, 2007, 2:59 pm**