1
$\begingroup$

If $p$ prime prove that there exists a permutation $a_1, a_2, \ldots , a_p$ of the numbers $1,2, \ldots p$ such that $a_1, a_1a_2, \ldots ,a_1a_2 \ldots a_p$ are all different modulo $p$.

I have no idea how to approach this problem. I tried to show that it is always possible to find an $a_i$ so that $a_1a_2\ldots a_i$ is different modulo $p$ to all the previous ones. I couldn't get anywhere.

$\endgroup$
6
$\begingroup$

Note that for $1 < h, k < p$, the following are all equivalent $$ \begin{cases}h = k,\\ hk - h = hk - k,\\ h (k-1) = k (h - 1),\\ h(h-1)^{-1} = k (k-1)^{-1}, \end{cases}$$ where inverses are meant modulo $p$

So we can get (all congruences modulo $p$) $$ \begin{cases} a_{1} \equiv 1\\ a_{1} a_{2} \equiv 2\\ a_{1} a_{2} a_{3} \equiv 3\\ \dots\\ a_{1} \cdots a_{k} \equiv k\\ \dots\\ a_{1} \cdots a_{p} \equiv p \equiv 0. \end{cases} $$ by choosing $a_{p} = p$, and then $a_{1} = 1$, and $$ a_{k} = k (k-1)^{-1} $$ for $1 < k < p$, where once more the inverse is modulo $p$. By the argument above, the $a_{k}$ are distinct (modulo $p$).

For instance for $p = 5$ you will have $$\begin{cases} a_{1} = 1,\\ a_{2} = 2,\\ a_{3} = 3 \cdot 2^{-1} \equiv 3 \cdot 3 \equiv 4,\\ a_{4} = 4 \cdot 3^{-1} \equiv 4 \cdot 2 \equiv 3,\\a_{5} = 5. \end{cases}$$

$\endgroup$
  • $\begingroup$ A very nice solution. Thanks. $\endgroup$ – user53970 Dec 16 '16 at 15:26
  • $\begingroup$ You're welcome! $\endgroup$ – Andreas Caranti Dec 16 '16 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.