Maths Olympiad Prep

Library / South-Afrika /55 of 64

South-Afrika, 2011

Number theory Difficulty 6.4 National Olympiad Prove it South Africa

Let pp be an odd prime number and let (a1,a2,…,ap)(a_1, a_2, \dots, a_p) and (b1,b2,…,bp)(b_1, b_2, \dots, b_p) be arbitrary arrangements of the pp-tuple (0,1,…,p−1)(0, 1, \dots, p-1). For each ii, let cic_i be the non-negative remainder when the product aibia_i b_i is divided by pp. Show that (c1,c2,…,cp)(c_1, c_2, \dots, c_p) cannot be a rearrangement of (0,1,…,p−1)(0, 1, \dots, p-1).

Solution

If ai=bj=0a_i = b_j = 0, then ci=cj=0c_i = c_j = 0. If (c1,c2,…,cp)(c_1, c_2, \dots, c_p) is a rearrangement of (0,1,…,p−1)(0, 1, \dots, p-1), then no entry can appear more than once. Hence i=ji = j.

Without loss of generality we may suppose that ap=bp=0a_p = b_p = 0 so that cp=0c_p = 0. Then we have
(p−1)!≡pa1a2…ap−1≡pb1b2…bp−1≡pc1c2…cp−1 (p-1)! \equiv_p a_1 a_2 \dots a_{p-1} \equiv_p b_1 b_2 \dots b_{p-1} \equiv_p c_1 c_2 \dots c_{p-1}
and so
(p−1)!≡pc1c2…cp−1≡p(a1a2…ap−1)(b1b2…bp−1)≡p((p−1)!)2, \begin{align*} (p-1)! &\equiv_p c_1 c_2 \dots c_{p-1} \\ &\equiv_p (a_1 a_2 \dots a_{p-1}) (b_1 b_2 \dots b_{p-1}) \\ &\equiv_p ((p-1)!)^2, \end{align*}
which implies that (p−1)!≡p1(p-1)! \equiv_p 1. However, since pp is odd, this contradicts Wilson's Theorem, and we conclude that (c1,c2,…,cp)(c_1, c_2, \dots, c_p) is not a rearrangement of (0,1,…,p−1)(0, 1, \dots, p-1).

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

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