Difference between revisions of "Wilson's Theorem"

 
(Proof)
Line 4: Line 4:
  
 
== Proof ==
 
== Proof ==
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
+
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
 
<math>1, 2, 3, \dots, p-1</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>.
+
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 <math>a</math> 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 <math>1</math> and <math>p-1</math>, then the others can be grouped into pairs whose product is congruent to one,
 
     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 <math>a</math> 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 <math>1</math> and <math>p-1</math>, then the others can be grouped into pairs whose product is congruent to one,
 
<math>2*3*4*\dots*(p-2) \equiv 1\pmod{p}</math>
 
<math>2*3*4*\dots*(p-2) \equiv 1\pmod{p}</math>
 
Finally, multiply this equality by p-1 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:19, 17 June 2006

Statement

If and only if p is a prime, then $(p-1)! + 1$ is a multiple of p. Written more mathematically, $(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*3*4*\dots*(p-2) \equiv 1\pmod{p}$ Finally, multiply this equality by p-1 to complete the proof. Insert non-formatted text here

Invalid username
Login to AoPS