Difference between revisions of "Wilson's Theorem"

(Statement)
(Proof)
Line 7: Line 7:
 
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 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,  
+
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,  
 
<center><math>2\cdot3\cdot4\cdots(p-2) \equiv 1\pmod{p}</math></center>  <br>
 
<center><math>2\cdot3\cdot4\cdots(p-2) \equiv 1\pmod{p}</math></center>  <br>
  

Revision as of 11:41, 18 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

Let ${p}$ be a prime number such that dividing ${p}$ by 4 leaves the remainder 1. Show that there is an integer ${n}$ such that $n^2 + 1$ is divisible by ${p}$.

<Solutions?>

See also