# Thread: Help with proof using Wilson's theorem

1. ## Help with proof using Wilson's theorem

Let $p$ be an odd prime and let $a_1, . . . ,a_{p-1}\$ be a permutation of $\{1, 2, . . ., p-1\}$. Prove that there exist $i \not = j$ such that $ia_i\equiv ja_j(\bmod p)$.

How can I use Wilson's theorem to prove this. I appreciate any help.

2. Originally Posted by didact273
Let $p$ be an odd prime and let $a_1, . . . ,a_{p-1}\$ be a permutation of $\{1, 2, . . ., p-1\}$. Prove that there exist $i \not = j$ such that $ia_i\equiv ja_j(\bmod p)$.

How can I use Wilson's theorem to prove this. I appreciate any help.
Say that there was no $i\not =j$ so that $ia_i \equiv ja_j(\bmod p)$. Therefore, $1\cdot a_1,2\cdot a_2, 3\cdot a_3, ... , (p-1)\cdot a_{p-1}$ are all incongruent to eachother. There are $p-1$ of them which means that they are a permutation of $a_1,...,a_{p-1}$ by pigeonhole principle. Therefore, $(a_1)(2a_2)(3a_3)...((p-1)a_{p-1}) \equiv (a_1)...(a_{p-1})(\bmod p)$. Canceling we get, $(p-1)!\equiv 1(\bmod p)$, but this is a contradiction because $(p-1)!\equiv -1(\bmod p)$.