4
$\begingroup$

How do I prove Wilson's Theorem $$\large{(p-1)! \equiv -1 \pmod p}$$ using Euler's theorem $$ \large{a^{\varphi(n)} \equiv 1 \pmod n }$$ where $ \large{\varphi(n)} $ denotes Euler's Totient function?

Thanks in advance for any replies.

$\endgroup$
4
  • $\begingroup$ $\textbf{Hint}:\space \space \space \space \phi(p) = p-1$ because there are $p-1$ numbers that are relatively prime to any prime number $p$ $\endgroup$
    – alkabary
    May 20 '15 at 5:42
  • $\begingroup$ I edited the question because I am sure you meant $\pmod{p}$ in the statement of the theorem $\endgroup$
    – marwalix
    May 20 '15 at 5:52
  • 2
    $\begingroup$ As an aside, I wrote a blog post on Wilson's Theorem for the MSE Community blog. $\endgroup$
    – davidlowryduda
    May 20 '15 at 5:53
  • $\begingroup$ @alkabary I figured that out but not sure how to use it to prove the theorem. Can you give another hint? $\endgroup$
    – pseudogeek
    May 20 '15 at 16:37
5
$\begingroup$

We sketch a proof of an interesting result that does the job, though admittedly it is overkill. However, it is close in spirit to the first published proof of Wilson's Theorem.

Let $p$ be prime. Let $P(x)$ be the polynomial $x^{p-1}-1$ and let $Q(x)=(x-1)(x-2)\cdots (x-(p-1))$.

By Fermat's theorem, we have $P(a)\equiv 0\pmod{p}$ for every $a$ from $1$ to $p-1$. And it is obvious that $Q(a)\equiv 0\pmod{p}$ for every such $a$. Let $D(x)=P(x)-Q(x)$. Then $D(a)\equiv 0\pmod{p}$ for all $a$ such that $1\le a\le p-1$.

But $D(x)$ has degree $\lt p-1$, and has at least $p-1$ zeros modulo $p$. It follows by a theorem due to Lagrange that all the coefficients of $D(x)$ are congruent to $0$ modulo $p$. In particular, the constant terms of $P(x)$ and $Q(x)$ are congruent modulo $p$. This is Wilson's Theorem.

$\endgroup$

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.