Advanced book on Mathematics Olympiad

262 5 Number Theory

Example.Show that for every primepthere is an integernsuch that 2n+ 3 n+ 6 n− 1

is divisible byp.

Solution.The property is true forp=2 andp=3, since 2^2 + 32 + 62 − 1 =48. Let

pbe a prime greater than 3. By Fermat’s little theorem, 2p−^1 ,3p−^1 , and 6p−^1 are all

congruent to 1 modulop. Hence

3 · 2 p−^1 + 2 · 3 p−^1 + 6 p−^1 ≡ 3 + 2 + 1 = 6 (modp).

It follows that

6 · 2 p−^2 + 6 · 3 p−^2 + 6 · 6 p−^2 ≡ 6 (modp).

Dividing by 6, we find that 2p−^2 + 3 p−^2 + 6 p−^2 −1 is divisible byp, and we are

done. 

And here is a problem from the 2005 USA Mathematical Olympiad, proposed by the

first author of the book.^2

Example.Prove that the system

x^6 +x^3 +x^3 y+y= 147157 ,

x^3 +x^3 y+y^2 +y+z^9 = 157147

has no solutions in integersx, y,andz.

Solution.Add the two equations, then add 1 to each side to obtain the Diophantine

equation

(x^3 +y+ 1 )^2 +z^9 = 147157 + 157147 + 1.

The right-hand side is rather large, and it is natural to reduce modulo some number. And

since the left-hand side is a sum of a square and a ninth power, it is natural to reduce

modulo 19 because 2× 9 + 1 =19. By Fermat’s little theorem,a^18 ≡ 1 (mod 19)

wheneverais not a multiple of 19, and so the order of a square is either 1, 3, or 9, while

the order of a ninth-power is either 1 or 2.

Computed by hand, the quadratic residues mod 19 are− 8 ,− 3 ,− 2 , 0 , 1 , 4 , 5 , 6 , 7 ,9,

while the residues of ninth powers are− 1 , 0 ,1. Also, applying Fermat’s little theorem

we see that

147157 + 157147 + 1 ≡ 1413 + 53 + 1 ≡ 14 (mod 19).

An easy verification shows that 14 cannot be obtained as a sum of a quadratic residue and
a ninth-power residue. Thus the original system has no solution in integersx,y, andz.

(^2) The statement was improved by R. Stong and E. Johnston to prevent a simpler solution.