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
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?>
