Difference between revisions of "Wilson's Theorem"

Revision as of 17:15, 17 June 2006

Statement

If and only if ${p}$ is a prime, then $(p-1)! + 1$ is a multiple of ${p}$ . In other words $(p-1)! \equiv -1 \pmod{p}$ .

Proof

Wilson's theorem is easily verifiable for 2 and 3, so let's consider $p>3$ . If ${p}$ is composite, then its positive factors are among $1, 2, 3, \dots, p-1$ . Hence, $\gcd((p-1)!, p) > 1$ , so $(p-1)! \neq -1 \pmod{p}$ .

However if ${p}$ is prime, then each of the above integers are relatively prime to ${p}$ . So for each of these integers a there is another $b$ such that $ab \equiv 1 \pmod{p}$ . It is important to note that this $b$ is unique modulo ${p}$ , and that since ${p}$ is prime, $a = b$ if and only if ${a}$ is $1$ or $p-1$ . Now if we omit 1 and $p-1$ , then the others can be grouped into pairs whose product is congruent to one, $2\cdot3\cdot4\cdots(p-2) \equiv 1\pmod{p}$

Finally, multiply this equality by $p-1$ to complete the proof.

Example Problem untilizing Wilson's

@@ Line 8: / Line 8: @@
 Finally, multiply this equality by <math>p-1</math> to complete the proof.
-Insert non-formatted text here
+==Example Problem untilizing Wilson's==
+<Maybe steal something from AoPS 2 with the Admin's permission?>

Page

Toolbox

Search

Difference between revisions of "Wilson's Theorem"

Revision as of 17:15, 17 June 2006

Contents

Statement

Proof

Example Problem untilizing Wilson's

See also