Advanced book on Mathematics Olympiad

702 Number Theory

nlim→∞xn=nlim→∞^3 n

(

A

(

2

3

)n

+B

)

=∞.

Letnbe sufficiently large thatxnis a prime number different from 2 and 3. Then for
k≥1,

xn+k(p− 1 )=A· 2 n+k(p−^1 )+B· 3 n+k(p−^1 )=A· 2 n·

(

2 p−^1

)k

+B· 3 n·

(

3 p−^1

)k

.

By Fermat’s little theorem, this is congruent toA· 2 n+B· 3 nmodulop, hence toxn
which is divisible byp. So the terms of the subsequencexn+k(p− 1 ),k≥1, are divisible
byp, and increase to infinity. This can happen only if the terms become composite at
some point, which contradicts our assumption. Hence the conclusion.

767.All congruences in this problem are modulo 13. First, let us show that for 0≤k<12,

∑^12

x= 0

xk≡ 0 (mod 13).

The casek=0 is obvious, so let us assumek>0. First, observe that 2 is a primitive
root modulo 13, meaning that 2m,m≥1, exhausts all nonzero residues modulo 13. So
on the one hand, 2k ≡1 for 1≤k<12, and on the other hand, the residue classes
2 , 4 , 6 ,...,24 are a permutation of the residue classes 1, 2 ,...,12. We deduce that

∑^12

x= 0

xk≡

∑^12

x= 0

( 2 x)k= 2 k

∑^12

x= 0

xk,

and because 2k ≡1, we must have

∑ 12

x= 0 x
k≡0.
Now letS ={(x 1 ,x 2 ,...,xn) | 0 ≤ xi ≤ 12 }. Because|S|= 13 nis divisi-
ble by 13, it suffices to show that the number ofn-tuples(x 1 ,...,xn)∈Ssuch that
f(x 1 ,x 2 ,...,xn) ≡0 is divisible by 13. Consider the sum
∑

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

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

This sum is congruent modulo 13 to the number ofn-tuples(x 1 ,x 2 ,...,xn)∈Ssuch
thatf(x 1 ,x 2 ,...,xn) ≡0, since by Fermat’s little theorem,

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

{

1iff(x 1 ,x 2 ,...,xn)  ≡ 0 ,

0iff(x 1 ,x 2 ,...,xn)≡ 0.

On the other hand,(f (x 1 ,x 2 ,...,xn))^12 can be expanded as

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

∑m

j= 1

cj

∏n

j= 1

x

αji

i ,