Advanced book on Mathematics Olympiad

5.2 Arithmetic 263

A different solution is possible using reduction modulo 13. Fermat’s little theorem

impliesa^12 ≡ 1 (mod 13)whenais not a multiple of 13.

We start by producing the same Diophantine equation. Applying Fermat’s little

theorem, we can reduce the right-hand side modulo 13. We find that

147157 + 157147 + 1 ≡ 41 + 12 ≡ 6 (mod 13).

The cubes modulo 13 are 0,±1, and±5. Writing the first equation of the original sys-

tem as

(x^3 + 1 )(x^3 +y)≡ 4 (mod 13),

it follows thatx^3 +ymust be congruent to 4, 2 ,5, or−1. Hence

(x^3 +y+ 1 )^2 ≡ 12 , 9 ,10 or 0(mod 13).

Note also thatz^9 is a cube; hencez^9 must be 0, 1 , 5 , 8 ,or 12 modulo 13. It is easy to check
that 6(mod 13)cannot be obtained by adding one of 0, 9 , 10 ,12 to one of 0, 1 , 5 , 8 ,12.
As a remark, the second solution also works ifz^9 is replaced byz^3. 

When solving the following problems, think that “work done with passion brings

results’’ (Virgil).

760.Show that ifnhasp−1 digits all equal to 1, wherepis a prime not equal to 2,3,

or 5, thennis divisible byp.

761.Prove that for any primep>17, the number

p^32 − 1

is divisible by 16320.

762.Letpbe an odd prime number. Show that if the equationx^2 ≡a(modp)has a

solution, thena

p− 1

(^2) ≡ 1 (modp). Conclude that there are infinitely many primes
of the form 4m+1.
763.Prove that the equationx^2 =y^3 +7 has no integer solutions.
764.Letn>1 be a positive integer. Prove that the equation(x+ 1 )n−xn=nyhas no
positive integer solutions.
765.Prove that the sequence 2n−3,n≥1, contains an infinite subsequence whose
terms are pairwise relatively prime.
766.Let(xn)nbe a sequence of positive integers satisfying the recurrence relationxn+ 1 =
5 xn− 6 xn− 1. Prove that infinitely many terms of the sequence are composite.