Advanced book on Mathematics Olympiad

Number Theory 703

for some integersm, cj,αji. Becausefis a polynomial of total degree less thann,we
haveαj 1 +αj 2 + ··· +αjn< 12 nfor everyj, so for eachjthere existsisuch that
αji<12. Using what we proved above, we obtain for 1≤j≤m,

∑

(x 1 ,x 2 ,...,xn)∈S

cj

∏n

i= 1

xiαji=cj

∏n

i= 1

∑^12

xi= 0

xiαji≡ 0 ,

since one of the sums in the product is congruent to 0. Therefore,

∑

(x 1 ,x 2 ,...,xn)∈S

(f (x 1 ,x 2 ,...,xn))^12 =

∑

(x 1 ,x 2 ,...,xn)∈S

∑m

j= 1

cj

∏n

i= 1

xiαji≡ 0.

This implies that the number ofn-tuples(x 1 ,x 2 ,...,xn)inSwith the property that
f(x 1 ,x 2 ,...,xn) ≡ 0 (mod 13)is divisible by 13, and we are done.
(Turkish Mathematical Olympiad, 1998)

768.We have 12321=( 111 )^2 = 32 × 372. It becomes natural to work modulo 3 and
modulo 37. By Fermat’s little theorem,

a^2 ≡ 1 (mod 3),

and since we must haveak≡− 1 (mod 3), it follows thatkis odd. Fermat’s little theorem
also gives

a^36 ≡ 1 (mod 37).

By hypothesisak≡− 1 (mod 37). By the fundamental theorem of arithmetic there exist
integersxandysuch thatkx+ 36 y=gcd(k, 36 ). Since the gcd(k, 36 )is odd,xis odd.
We obtain that

agcd(k,^36 )≡akx+^36 y≡(− 1 )· 1 =− 1 (mod 37).

Since gcd(k, 36 )can be 1, 3, or 9, we see thatamust satisfya ≡−1,a^3 ≡−1, or
a^9 ≡−1 modulo 37. Thusais congruent to−1 modulo 3 and to 3, 4, 11, 21, 25, 27, 28,
30, or 36 modulo 37. These residue classes modulo 37 are precisely those for whichais
a perfect square but not a perfect fourth power. Note that if these conditions are satisfied,
thenak≡− 1 (mod 3× 37 ), for some odd integerk.
How do the 3^2 and 37^2 come into the picture? The algebraic identity

xn−yn=(x−y)(xn−^1 +xn−^2 y+···+xyn−^2 +yn−^1 )

shows that ifx≡y(modn), thenxn≡yn(modn^2 ). Indeed, modulon, the factors on
the right are 0, respectively,nxn−^1 , which is again 0.