Saturday, January 26, 2013

A simple number theory problem

Divisibility puzzle: Suppose that there are n integers which have the following
property: the difference between the product of any n - 1 integers and
the remaining one is divisible by n . Prove that the sum of the square of
these n numbers is also divisible by n.

Denote the n integers by a1, a2, a3, .., an. By the given property, it follows that:

(a1 – a2 a3…an) = k1n
(a2 – a1 a3 = k2n
(an – a1 a2… an-1) = knn

where k1, k2, .., kn are some integers. By multiplying equation 1 above by a1, similarly equation 2 by a2 and so on till the last equation above (which would be multiplied by an), the following set of equations are obtained:

a12 – C = k1na1
a22 – C = k2na2
an2 – C = knnan

where C = a1 a2 a3

Summing the above equations and then rearranging leads to:
(a12+ a22 + … + an2) = nC  + n(k1a1 + k2a2 + … + knan)  = n(C + k1a1 + k2a2 + … + knan)

which proves that the sum of squares of the n integers (a1, a2, a3, .., an) is a multiple of n.

No comments:

Post a Comment