Advanced book on Mathematics Olympiad

Number Theory 699

whereσis a certain permutation of 1, 2 ,...,n. The sides are parallel to the raysσ(k)k,

so the angle between two consecutive sides is indeed^2 nπ, except for maybe the first and

the last! For these two sides to form the appropriate angle, the equality

∑n−^1

i= 0

σ(i)i= 0

must hold. We are supposed to find a permutationσfor which this relation is satisfied.

It is here that residues come into play.

Letn=abwithaandbcoprime. Represent thenth roots of unity as

aj+bk,j= 0 , 1 ,...,b− 1 ,k= 0 , 1 ,...,a− 1.

Note that there areab=nsuch numbers altogether, and no two coincide, for ifaj+bk≡

aj′+bk′(modn), thena(j−j′)≡b(k′−k) (modn), which means thatj−j′is

divisible bybandk−k′is divisible bya, and soj =j′andk=k′. Thus we have

indeed listed allnth roots of unity.

Order the roots of unity in the lexicographic order of the pairs(j, k). This defines

the permutationσ. We are left with proving that

∑b−^1

j= 0

∑a−^1

k= 0

(aj+k)aj+bk= 0.

And indeed,

∑b−^1

j= 0

∑a−^1

k= 0

(aj+k)aj+bk=

∑b−^1

j= 0

aj aj

∑a−^1

k= 0

(

b

)k

+

a∑− 1

k= 0

kbk

∑b−^1

k= 0

(

a

)j

= 0.

759.LetSbe the set of all primes with the desired property. We claim thatS =

{ 2 , 3 , 5 , 7 , 13 }.

It is easy to verify that these primes are indeed inS. So let us consider a primepin

S,p>7. Thenp−4 can have no factorqlarger than 4, for otherwisep−pqq=4.

Sincep−4 is odd,p− 4 = 3 afor somea≥2. For a similar reason,p−8 cannot have

prime factors larger than 8, and sop− 8 = 3 a− 4 = 5 b 7 c. Reducing the last equality

modulo 24, we find thatais even andbis odd.

Ifc =0, thenp− 9 = 5 b 7 c− 1 = 2 d. Here we used the fact thatp−9 has no

prime factor exceeding 8 and is not divisible by 3, 5, or 7. Reduction modulo 7 shows

that the last equality is impossible, for the powers of 2 are 1,2, and 4 modulo 7. Hence

c=0 and 3a− 4 = 5 b, which, since 3a/^2 −2 and 3a/^2 +2 are relatively prime, gives

3 a/^2 − 2 =1 and 3a/^2 + 2 = 5 b. Thusa=2,b=1, andp=13. This proves the claim.

(American Mathematical Monthly, 1987, proposed by M. Cipu and M. Deaconescu,

solution by L. Jones)