# Thread: Help with proof using Wilson's theorem

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

Let $\displaystyle p$ be an odd prime and let $\displaystyle a_1, . . . ,a_{p-1}\$ be a permutation of $\displaystyle \{1, 2, . . ., p-1\}$. Prove that there exist $\displaystyle i \not = j$ such that $\displaystyle 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 $\displaystyle p$ be an odd prime and let $\displaystyle a_1, . . . ,a_{p-1}\$ be a permutation of $\displaystyle \{1, 2, . . ., p-1\}$. Prove that there exist $\displaystyle i \not = j$ such that $\displaystyle 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 $\displaystyle i\not =j$ so that $\displaystyle ia_i \equiv ja_j(\bmod p)$. Therefore, $\displaystyle 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 $\displaystyle p-1$ of them which means that they are a permutation of $\displaystyle a_1,...,a_{p-1}$ by pigeonhole principle. Therefore, $\displaystyle (a_1)(2a_2)(3a_3)...((p-1)a_{p-1}) \equiv (a_1)...(a_{p-1})(\bmod p)$. Canceling we get, $\displaystyle (p-1)!\equiv 1(\bmod p)$, but this is a contradiction because $\displaystyle (p-1)!\equiv -1(\bmod p)$.