Difference between revisions of "Wilson's Theorem"
(→Proof) |
(cleaned it up a little bit) |
||
| Line 1: | Line 1: | ||
== Statement == | == Statement == | ||
| − | If and only if p is a prime, then <math>(p-1)! + 1</math> is a multiple of p. Written more mathematically, | + | If and only if <math>{p}</math> is a prime, then <math>(p-1)! + 1</math> is a multiple of <math>{p}</math>. Written more mathematically, |
<math>(p-1)! \equiv -1 \pmod{p}</math> | <math>(p-1)! \equiv -1 \pmod{p}</math> | ||
== Proof == | == Proof == | ||
| − | Wilson's theorem is easily verifiable for 2 and 3, so let's consider <math>p>3</math>. If p is composite, then its positive factors are among | + | Wilson's theorem is easily verifiable for 2 and 3, so let's consider <math>p>3</math>. If <math>{p}</math> is composite, then its positive factors are among <math>1, 2, 3, \dots, p-1</math>. Hence, <math>\gcd((p-1)!, p) > 1</math>, so <math>(p-1)! \neq -1 \pmod{p}</math>. |
| − | <math>1, 2, 3, \dots, p-1</math> | + | |
| − | Hence, <math>gcd((p-1)!, p) > 1</math>, so <math>(p-1)! \neq -1 \pmod{p}</math>. | + | However if <math>{p}</math> is prime, then each of the above integers are relatively prime to <math>{p}</math>. So for each of these integers a there is another <math>b</math> such that <math>ab \equiv 1 \pmod{p}</math>. It is important to note that this <math>b</math> is unique modulo <math>{p}</math>, and that since <math>{p}</math> is prime, <math>a = b</math> if and only if <math>{a}</math> is <math>1</math> or <math>p-1</math>. Now if we omit 1 and <math>p-1</math>, then the others can be grouped into pairs whose product is congruent to one, <math>2\cdot3\cdot4\cdots(p-2) \equiv 1\pmod{p}</math> |
| − | + | ||
| − | <math>2 | + | Finally, multiply this equality by <math>p-1</math> to complete the proof. |
| − | Finally, multiply this equality by p-1 to complete the proof. | ||
Insert non-formatted text here | Insert non-formatted text here | ||
Revision as of 14:56, 17 June 2006
Statement
If and only if 
is a prime, then 
is a multiple of . Written more mathematically,
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.
Insert non-formatted text here
