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
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
![$1, 2, 3, \dots, p-1$](http://latex.artofproblemsolving.com/0/d/f/0dfe24d3485a7f19fa17e2195c625959c00dc811.png)
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,
![$2\cdot3\cdot4\cdots(p-2) \equiv 1\pmod{p}$](http://latex.artofproblemsolving.com/b/6/a/b6a67ca261ea87615017b0a10b367e711c9b801b.png)
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?>