Difference between revisions of "Wilson's Theorem"
(mild rewrite) |
|||
Line 1: | Line 1: | ||
− | + | '''Wilson's Theorem''' is a result in elementary [[number theory]]. It states that if <math>p > 1</math> is in [[integer]], then <math>(p-1)! + 1</math> is a multiple of <math>p</math> if and only if <math>p</math> is a prime. | |
− | |||
− | == | + | == Proofs == |
− | |||
− | |||
− | |||
− | + | Suppose first that <math>p</math> is composite. Then <math>p</math> has a factor <math>d > 1</math> that is less than or equal to <math>p-1</math>. Then <math>d</math> divides <math>(p-1)!</math>, so <math>d</math> does not divide <math>(p-1)! + 1</math>. Therefore <math>p</math> does not divide <math>(p-1)! + 1</math>. | |
− | |||
− | + | The converse of this statement is more interesting. We provide two proofs: an elementary one that rests close to basic principles of [[modular arithmetic]], and an elegant method that relies on more powerful algebraic tools. | |
+ | |||
+ | === Elementary proof === | ||
+ | |||
+ | Suppose <math>p</math> is a prime. Then each of the integers <math>1, \dotsc, p-1</math> has an inverse modulo <math>p</math>. (Indeed, if one such integer <math>a</math> does not have an inverse, then for some distinct <math>b</math> and <math>c</math> modulo <math>p</math>, <math>ab \equiv ac \pmod{p}</math>, so that <math>a(b-c)</math> is a multiple of <math>p</math>, when <math>p</math> does not divide <math>a</math> or <math>b-c</math>—a contradiction.) This inverse is unique, and each number is the inverse of its inverse. If one integer <math>a</math> is its own inverse, then | ||
+ | <cmath> 0 \equiv a^2 - 1 \equiv (a-1)(a+1) \pmod{p} , </cmath> | ||
+ | so that <math>a \equiv 1</math> or <math>a \equiv p-1</math>. Thus we can partition the set <math>\{ 2 ,\dotsc, p-2\}</math> into pairs <math>\{a,b\}</math> such that <math>ab \equiv 1 \pmod{p}</math>. It follows that <math>(p-1)</math> is the product of these pairs times <math>1 \cdot (-1)</math>. Since the product of each pair is conguent to 1 modulo <math>p</math>, we have | ||
+ | <cmath> (p-1)! \equiv 1\cdot 1 \cdot (-1) \equiv -1 \pmod{p}, </cmath> | ||
+ | as desired. <math>\blacksquare</math> | ||
+ | |||
+ | === Algebraic proof === | ||
+ | |||
+ | Let <math>p</math> be a prime. Consider the [[field]] of integers modulo <math>p</math>. By [[Fermat's Little Theorem]], every nonzero element of this field is a root | ||
+ | of the polynomial | ||
+ | <cmath> P(x) = x^p - 1 . </cmath> | ||
+ | Since this field has only <math>p-1</math> nonzero elements, it follows that | ||
+ | <cmath> x^p - 1 = \prod_{r=1}^{p-1}(x-r) . </cmath> | ||
+ | Now, either <math>p=2</math>, in which case <math>a \equiv -a \pmod 2</math> for any integer <math>a</math>, | ||
+ | or <math>p-1</math> is even. In either case, <math>(-1)^{p-1} \equiv 1 \pmod{p}</math>, so that | ||
+ | <cmath> x^p - 1 = \prod_{r=1}^{p-1}(x-r) = \prod_{r=1}^{p-1}(-x + r) . </cmath> | ||
+ | If we set <math>x</math> equal to 0, the theorem follows. <math>\blacksquare</math> | ||
== Problems == | == Problems == | ||
Line 17: | Line 32: | ||
=== Advanced === | === Advanced === | ||
− | * If <math>{p}</math> is a prime greater than 2, define <math>p=2q+1</math>. Prove that <math>(q!)^2 + (-1)^q</math> is divisible by <math>{p}</math>. | + | * If <math>{p}</math> is a prime greater than 2, define <math>p=2q+1</math>. Prove that <math>(q!)^2 + (-1)^q</math> is divisible by <math>{p}</math>. <url>Forum/viewtopic.php?&t=21733 Solution</url> |
* Let <math>{p}</math> be a prime number such that dividing <math>{p}</math> by 4 leaves the remainder 1. Show that there is an integer <math>{n}</math> such that <math>n^2 + 1</math> is divisible by <math>{p}</math>. | * Let <math>{p}</math> be a prime number such that dividing <math>{p}</math> by 4 leaves the remainder 1. Show that there is an integer <math>{n}</math> such that <math>n^2 + 1</math> is divisible by <math>{p}</math>. | ||
== See also == | == See also == | ||
+ | |||
* [[Number theory]] | * [[Number theory]] | ||
* [[Modular arithmetic]] | * [[Modular arithmetic]] | ||
+ | * [[Fermat's Little Theorem]] | ||
* [[Factorial]] | * [[Factorial]] | ||
+ | |||
+ | [[Category:Number theory]] |
Revision as of 13:29, 28 March 2009
Wilson's Theorem is a result in elementary number theory. It states that if is in integer, then
is a multiple of
if and only if
is a prime.
Contents
Proofs
Suppose first that is composite. Then
has a factor
that is less than or equal to
. Then
divides
, so
does not divide
. Therefore
does not divide
.
The converse of this statement is more interesting. We provide two proofs: an elementary one that rests close to basic principles of modular arithmetic, and an elegant method that relies on more powerful algebraic tools.
Elementary proof
Suppose is a prime. Then each of the integers
has an inverse modulo
. (Indeed, if one such integer
does not have an inverse, then for some distinct
and
modulo
,
, so that
is a multiple of
, when
does not divide
or
—a contradiction.) This inverse is unique, and each number is the inverse of its inverse. If one integer
is its own inverse, then
so that
or
. Thus we can partition the set
into pairs
such that
. It follows that
is the product of these pairs times
. Since the product of each pair is conguent to 1 modulo
, we have
as desired.
Algebraic proof
Let be a prime. Consider the field of integers modulo
. By Fermat's Little Theorem, every nonzero element of this field is a root
of the polynomial
Since this field has only
nonzero elements, it follows that
Now, either
, in which case
for any integer
,
or
is even. In either case,
, so that
If we set
equal to 0, the theorem follows.
Problems
Introductory
- Let
be an integer such that
. Find the remainder when
is divided by
.
Advanced
- If
is a prime greater than 2, define
. Prove that
is divisible by
. <url>Forum/viewtopic.php?&t=21733 Solution</url>
- 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
.