710 Number Theory
787.Letm=m 1 m 2 .Ifx ∈{ 0 , 1 ,...,m− 1 }is such thatP(x)≡ 0 (modm), then
P(x)≡ 0 (modm 1 ). Leta 1 be the residue ofxmodulom 1. ThenP(a 1 )≡ 0 (modm 1 ).
Similarly, ifa 2 is the residue ofxmodulom 2 , thenP(a 2 )≡ 0 (modm 2 ). Thus for each
solutionxtoP(x)≡ 0 (modm), we have constructed a pair(a 1 ,a 2 )withaia solution
toP(x)≡ 0 (modmi),i= 1 ,2.
Conversely, given the residuesai such thatP(ai) ≡ 0 (modmi),i = 1 ,2, by
the Chinese Remainder Theorem there exists a uniquex∈{ 0 , 1 ,...,m− 1 }such that
x ≡ai(modmi),i = 1 ,2. ThenP(x)≡ 0 (modmi),i = 1 ,2, and consequently
P(x)≡ 0 (modm). We have established a bijection from the set of solutions to the
equationP(x)≡ 0 (modm)to the Cartesian product of the sets of solutions toP(x)≡
0 (modmi),i= 1 ,2. The conclusion follows.
(I. Niven, H.S. Zuckerman, H.L. Montgomery,An Introduction to the Theory of
Numbers, Wiley, 1991)
788.Since this is a game with finite number of possibilities, there is always a winning
strategy, either for the first player, or for the second. Arguing by contradiction, let us
assume that there are only finitely manyn’s, sayn 1 ,n 2 ,...,nmfor which Bob has a
winning strategy. Then for every other nonnegative integern, Alice must have some
move on a heap ofnstones leading to a position in which the second player wins. This
means that any other integernis of the formp− 1 +nkfor some primepand some
1 ≤k≤m.
We will prove that this is not the case. Choose an integerNgreater than all the
nk’s and letp 1 ,p 2 ,...,pNbe the firstNprime numbers. By the Chinese Remainder
Theorem, there exists a positive integerxsuch that
x≡− 1 (modp^21 ),
x≡− 2 (modp^22 ),
...
x≡−N(modp^2 r).Then the numberx+N+1 is not of the formp− 1 +nk, because each of the numbers
x+N+ 1 −nk−1 is composite, being a multiple of a square of a prime number. We
have reached a contradiction, which proves the desired conclusion.
(67th W.L. Putnam Mathematical Competition, 2006)
789.Letp 1 <p 2 <p 3 <···be the sequence of all prime numbers. Seta 1 =2.
Inductively, forn≥1, letan+ 1 be the least integer greater thananthat is congruent to
−kmodulopk+ 1 , for allk≤n. The existence of such an integer is guaranteed by the
Chinese Remainder Theorem. Observe that for allk≥0,k+an≡ 0 (modpk+ 1 )for
n≥k+1. Then at mostk+1 values in the sequencek+an,n≥1, can be prime, since