Advanced book on Mathematics Olympiad

690 Number Theory

735.The numbersxandyhave the same prime factors,

x=

∏k

i= 1

pαii,y=

∏k

i= 1

pβii.

The equality from the statement can be written as

∏k

i= 1

pαii(x+y)=

∏k

i= 1

pβii(y−x);

henceαi(y+x)=βi(y−x)fori= 1 , 2 ,...,k. From here we deduce thatαi<βi,
i = 1 , 2 ,...,k, and thereforexdividesy. Writingy =zx, the equation becomes
xx(z+^1 )=(xz)x(z−^1 ), which impliesx^2 =zz−^1 and theny^2 =(xz)^2 =zz+^1. A power
is a perfect square if either the base is itself a perfect square or if the exponent is even.
Forz=t^2 ,t≥1, we havex=tt

(^2) − 1
,y=tt
(^2) + 1
, which is one family of solutions. For
z− 1 = 2 s,s≥0, we obtain the second family of solutionsx=( 2 s+ 1 )s,y=( 2 s+ 1 )s+^1.
(Austrian–Polish Mathematics Competition, 1999, communicated by I. Cucurezea-
nu)
736.Ifnis even, then we can write it as( 2 n)−n.Ifnis odd, letpbe the smallest odd
prime that does not dividen. Then writen=(pn)−((p− 1 )n). The numberpncontains
exactly one more prime factor thann. As for(p− 1 )n, it is divisible by 2 becausep− 1
is even, while its odd factors are less thanp, so they all dividen. Therefore,(p− 1 )n
also contains exactly one more prime factor thann, and thereforepnand(p− 1 )nhave
the same number of prime factors.
(Russian Mathematical Olympiad, 1999)
737.The only numbers that do not have this property are the products of two distinct
primes.
Letnbe the number in question. Ifn=pqwithp, qprimes andp =q, then any
cycle formed byp, q, pqwill havepandqnext to each other. This rules out numbers
of this form.
For any other numbern=pα 11 p 2 α^2 ···pαkk, withk≥1,αi ≥1 fori= 1 , 2 ,...,k
andα 1 +α 2 ≥3ifk=2, arrange the divisors ofnaround the circle according to the
following algorithm. First, we placep 1 ,p 2 ,...,pkarranged clockwise around the circle
in increasing order of their indices. Second, we placepipi+ 1 betweenpiandpi+ 1 for
i= 1 ,...,k−1. (Note that the text haspi+i, which is a typo and letsigo up tok, which
is a problem ifk=2, sincep 1 p 2 gets placed twice.) Third, we placenbetweenpkand
p 1. Note that at this point every pair of consecutive numbers has a common factor and
each primepioccurs as a common factor for some pair of adjacent numbers. Now for
any remaining divisor ofnwe choose a primepithat divides it and place it betweenpi
and one of its neighbors.
(USA Mathematical Olympiad, 2005, proposed by Z. Feng)