Difference between revisions of "Wilson's Theorem"
(→Proof) |
(→Statement) |
||
Line 1: | Line 1: | ||
== Statement == | == Statement == | ||
− | If and only if <math>{p}</math> is a prime, then <math>(p-1)! + 1</math> is a multiple of <math>{p}</math>. In other words <math>(p-1)! \equiv -1 \pmod{p}</math>. | + | If and only if <math>{p}</math> is a [[prime]], then <math>(p-1)! + 1</math> is a multiple of <math>{p}</math>. In other words <math>(p-1)! \equiv -1 \pmod{p}</math>. |
== Proof == | == Proof == |
Revision as of 10:40, 18 June 2006
Contents
[hide]Statement
If and only if is a prime, then is a multiple of . In other words .
Proof
Wilson's theorem is easily verifiable for 2 and 3, so let's consider . If is composite, then its positive factors are among
Hence, , so .
However if is prime, then each of the above integers are relatively prime to . So for each of these integers a there is another such that . It is important to note that this is unique modulo , and that since is prime, if and only if is or . Now if we omit 1 and , then the others can be grouped into pairs whose product is congruent to one,
Finally, multiply this equality by to complete the proof.
Example
Let be a prime number such that dividing by 4 leaves the remainder 1. Show that there is an integer such that is divisible by .
<Solutions?>