Advanced book on Mathematics Olympiad

Number Theory 701

Now assume that there are only finitely many primes of the form 4m+1,man
integer, sayp 1 ,p 2 ,...,pn. The number( 2 p 1 p 2 ...pn)^2 +1 has only odd prime factors,
and these must be of the form 4m+1,man integer. Yet these are none ofp 1 ,p 2 ,...,pn,
a contradiction. Hence the conclusion.

763.Assume a solution(x, y)exists. Ifywere even, theny^3 +7 would be congruent to
3 modulo 4. But a square cannot be congruent to 3 modulo 4. Henceymust be odd, say
y= 2 k+1. We have

x^2 + 1 =y^3 + 23 =(y+ 2 )

[

(y− 1 )^2 + 3

]

=(y+ 2 )( 4 k^2 + 3 ).

We deduce thatx^2 +1 is divisible by a number of the form 4m+3, namely, 4k^2 +3.
It must therefore be divisible by a prime number of this form. But we have seen in the
previous problem that this is impossible. Hence the equation has no solutions.
(V.A. Lebesgue)

764.Assume that the equation admits a solution(x, y). Letpbe the smallest prime
number that dividesn. Because(x+ 1 )n−xnis divisible byp, andxandx+1 cannot
both be divisible byp, it follows thatxandx+1 are relatively prime top. By Fermat’s
little theorem,(x+ 1 )p−^1 ≡ 1 ≡xp−^1 (modp). Also,(x+ 1 )n≡xn(modp)by
hypothesis.
Additionally, becausepis the smallest prime dividingn, the numbersp−1 andn
are coprime. By the fundamental theorem of arithmetic, there exist integersaandbsuch
thata(p− 1 )+bn=1. It follows that

x+ 1 =(x+ 1 )a(p−^1 )+bn≡xa(p−^1 )+bn≡x(modp),

which is impossible. Hence the equation has no solutions.
(I. Cucurezeanu)

765.We construct the desired subsequence(xn)ninductively. Suppose that the prime num-
bers that appear in the prime factor decompositions ofx 1 ,x 2 ,...,xk− 1 arep 1 ,p 2 ,...,pm.
Because the terms of the sequence are odd, none of these primes is equal to 2. Define

xk= 2 (p^1 −^1 )(p^2 −^1 )···(pm−^1 )− 3.

By Fermat’s little theorem, 2(p^1 −^1 )(p^2 −^1 )···(pm−^1 )−1 is divisible by each of the numbers
p 1 ,p 2 ,...,pn. It follows thatxkis not divisible by any of these primes. Hencexk
is relatively prime tox 1 ,x 2 ,...,xk− 1 , and thus it can be added to the sequence. This
completes the solution.

766.The recurrence is linear. Using the characteristic equation we find thatxn=A·
2 n+B· 3 n, whereA= 3 x 0 −x 1 andB=x 1 − 2 x 0. We see thatAandBare integers.
Now let us assume that all but finitely many terms of the sequence are prime. Then
A, B =0, and