Maths Olympiad Prep

Library / /8 of 21

Number theory Difficulty 4.7 AIME Prove it Singapore

Let nn be a prime number. Show that there is a permutation a1,a2,…,ana_1, a_2, \dots, a_n of 1,2,…,n1, 2, \dots, n so that a1,a1a2,…,a1a2…ana_1, a_1a_2, \dots, a_1a_2 \dots a_n leave distinct remainders when divided by nn.

Solution

By the Chinese remainder Theorem, for every k=2,3,…,nk=2,3,\dots,n there exists bkb_k so that
bk≡0(mod(k−1)),bk≡k(modn). b_k \equiv 0 \pmod{(k-1)}, \quad b_k \equiv k \pmod{n}.
Let a1=1a_1 = 1 and for k=2,…,nk = 2, \dots, n, aka_k is the remainder when bk/(k−1)b_k/(k-1) is divided by nn. Since bn≡0(modn)b_n \equiv 0 \pmod{n}, we have an=0a_n = 0. Also if ai=aja_i = a_j, then bi/(i−1)≡bj/(j−1)(modn)b_i/(i-1) \equiv b_j/(j-1) \pmod{n}, i.e., i(j−1)≡j(i−1)(modn)i(j-1) \equiv j(i-1) \pmod{n}. Since nn is prime, i=ji = j. Thus a1,…,ana_1, \dots, a_n are distinct. Now
a1a2…ak≡b2…bk(k−1)!≡k(modn). a_1 a_2 \dots a_k \equiv \frac{b_2 \dots b_k}{(k-1)!} \equiv k \pmod{n}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.