Track / Stage 4 / 171 of 340 #911 of 2444

Problem 911

AMC 12 late, AIME early

Number theory Difficulty 4.7 Prove it Singapur · Singapore

Let $n$ be a prime number. Show that there is a permutation $a_1, a_2, \dots, a_n$ of $1, 2, \dots, n$ so that $a_1, a_1a_2, \dots, a_1a_2 \dots a_n$ leave distinct remainders when divided by $n$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

By the Chinese remainder Theorem, for every $k=2,3,\dots,n$ there exists $b_k$ so that
$b_k \equiv 0 \pmod{(k-1)}, \quad b_k \equiv k \pmod{n}.$
Let $a_1 = 1$ and for $k = 2, \dots, n$ , $a_k$ is the remainder when $b_k/(k-1)$ is divided by $n$ . Since $b_n \equiv 0 \pmod{n}$ , we have $a_n = 0$ . Also if $a_i = a_j$ , then $b_i/(i-1) \equiv b_j/(j-1) \pmod{n}$ , i.e., $i(j-1) \equiv j(i-1) \pmod{n}$ . Since $n$ is prime, $i = j$ . Thus $a_1, \dots, a_n$ are distinct. Now
$a_1 a_2 \dots a_k \equiv \frac{b_2 \dots b_k}{(k-1)!} \equiv k \pmod{n}.$

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