Number Theory 691738.The answer is negative. To motivate our claim, assume the contrary, and let
a 0 ,a 1 ,...,a 1995 =a 0 be the integers. Then fori= 1 , 2 ,...,1995, the ratioak− 1 /akis
either a prime, or the reciprocal of a prime. Suppose the former happensmtimes and the
latter 1995−mtimes. The product of all these ratios isa 0 /a 1995 =1, which means that
the product of somemprimes equals the product of some 1995−mprimes. This can
happen only when the primes are the same (by unique factorization), and in particular
they must be in the same number on both sides. But the equalitym= 1995 −mis
impossible, since 1995 is odd, a contradiction. This proves our claim.
(Russian Mathematical Olympiad, 1995)
739.First solution: The casesp= 2 , 3 ,5 are done as before. Letp≥7. The numbers
p, 2 p,..., 9999999999 phave distinct terminating ten-digit sequences. Indeed, the dif-
ferencemp−np=(m−n)pis not divisible by 10^10 , sincepis relatively prime to 10
andm−n< 1010. There are 10^10 −1 ten-digit terminating sequences, so all possible
combinations of digits should occur. Many of these sequences consist of distinct digits,
providing solutions to the problem.
Second solution: The statement is true forp=2 andp=5. Suppose thatp = 2 ,5. Then
pis relatively prime to 10. From Fermat’s little theorem, 10p−^1 ≡ 1 (modp)and hence
10 k(p−^1 )≡ 1 (modp)for all positive integersk. Letabe a 10-digit number with distinct
digits, and leta≡n(modp), with 0≤n≤p−1. Sincep≥3, 10^6 (p−^1 )> 1010.
Therefore,
Na= 10 (p−n+^5 )(p−^1 )+···+ 106 (p−^1 )+a≡ 1 +···+ 1 +n≡ 0 (modp).For all positive integersk, the numbers of the form
1010 kp+Na,end inaand are divisible byp.
(proposed by T. Andreescu for the 41st International Mathematical Olympiad, 2000,
first solution by G. Galperin, second solution by Z. Feng)
740.The casep=2 is easy, so assume thatpis an odd prime. Note that ifp^2 =a^2 + 2 b^2 ,
then 2b^2 =(p−a)(p+a). In particular,ais odd. Also,ais too small to be divisible
byp. Hence gcd(p−a, p+a)=gcd(p−a, 2 p)=2. By changing the sign ofawe
may assume thatp−ais not divisible by 4, and so we must have|p+a|=m^2 and
|p−a|= 2 n^2 for some integersmandn.
Because|a|<p, bothp+aandp−aare actually positive, sop+a=m^2 and
p−a= 2 n^2. We obtain 2p=m^2 + 2 n^2. This can happen only ifmis even, in which
casep=n^2 + 2 (m 2 )^2 , as desired.
(Romanian Mathematical Olympiad, 1997)