2

So here it goes.

For any integer $p > 1$, if $(p - 1)!$ is congruent to $-1 \pmod p$ then $p$ is prime.

Any help would be appreciated!

David R.
  • 1,236
  • 2
  • 12
  • 33
andrew749
  • 215
  • 1
    This is Wilson's Theorem. – MarkG Feb 28 '15 at 22:06
  • We show that if $m\gt 1$ is composite, then $(m-1)!\not\equiv -1\pmod{m}$. Since $m$ is composite, $m=ab$ where $a$ and $b$ are integers and $1\lt a\lt m$. Note that $a$ divides $(m-1)!$. If $(m-1)!\equiv -1\pmod{m}$, then since $a$ divides $(m-1)!$ and $m$, it follows that $a$ divides $1$, impossible. – André Nicolas Feb 28 '15 at 23:03

2 Answers2

1

This is Wilson's theorem, and it has been proven by many mathematicians (though perhaps not by Wilson himself, I'm not sure). Proofs can be found in Niven & Zuckerman's An Introduction to the Theory of Numbers and Ethan Bolker's Elementary Number Theory to name just two. On the Web I suggest you go to ProofWiki: https://proofwiki.org/wiki/Wilson%27s_Theorem But avoid Wikipedia at all costs or else you'll be led astray.

David R.
  • 1,236
  • 2
  • 12
  • 33
1

For composite number $n$ it is obvious that $\equiv 0$ since all divisors of $n$ are strictly smaller than $n$.

If it is prime. Then $\mathbb{F}_p$ is a field and $x=x^{-1}$ if and only if $x=\pm1$. Hence the other elements has different inverses. Therefore $1\cdots(p-1)\equiv=1.(-1)(a_1a_1^{-1})\cdots \equiv -1$

Note that: $-1 \equiv 1$ in modulo $2$.

vudu vucu
  • 1,040