# 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 | + | 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 is a multiple of p. Written more mathematically,

## Proof

Wilson's theorem is easily verifiable for 2 and 3, so let's consider . If p 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 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 and , then the others can be grouped into pairs whose product is congruent to one,

Finally, multiply this equality by p-1 to complete the proof. Insert non-formatted text here