Difference between revisions of "Wilson's Theorem"
(cleaned it up a little bit) |
m (→See also) |
||
(40 intermediate revisions by 21 users not shown) | |||
Line 1: | Line 1: | ||
− | + | In [[number theory]], '''Wilson's Theorem''' states that if [[integer ]]<math>p > 1</math> , then <math>(p-1)! + 1</math> is divisible by <math>p</math> if and only if <math>p</math> is prime. It was stated by John Wilson. The French mathematician Lagrange proved it in 1771. | |
− | |||
− | <math> | ||
− | == | + | == 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>. | |
− | + | Two proofs of the converse are provided: an elementary one that rests close to basic principles of [[modular arithmetic]], and an elegant method that relies on more powerful [[algebra]]ic 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 congruent to <math>1 \bmod 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} - 1 . </cmath> | ||
+ | Since this field has only <math>p-1</math> nonzero elements, it follows that | ||
+ | <cmath> x^{p-1} - 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} - 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 == | ||
+ | === Introductory === | ||
+ | * (Source: ARML 2002) Let <math>a</math> be an integer such that <math>\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{23}=\frac{a}{23!}</math>. Find the remainder when <math>a</math> is divided by <math>13</math>. | ||
+ | |||
+ | ==== Solution ==== | ||
+ | |||
+ | Multiplying both sides by <math>23!</math> yields | ||
+ | <cmath>\frac{23!}{1}+\frac{23!}{2}+...+\frac{23!}{23}=a</cmath> | ||
+ | Note that <math>13\mid\frac{23!}{k}</math> for all <math>k\neq13</math>. Thus we are left with | ||
+ | <cmath>a\equiv\frac{23!}{13}\equiv12!\cdot14\cdot15\cdot16\cdot...\cdot23\equiv(-1)(1)(2)(3)(...)(10)\equiv\boxed{7}\mod13</cmath> | ||
+ | |||
+ | === 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>. [https://artofproblemsolving.com/community/c6h21733 Solution.] | ||
+ | |||
+ | * 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 == | ||
+ | |||
+ | * [[Number theory]] | ||
+ | * [[Modular arithmetic]] | ||
+ | * [[Fermat's Little Theorem]] | ||
+ | * [[Factorial]] | ||
+ | * [[Wilson Prime]] | ||
+ | |||
+ | [[Category:Number theory]] |
Latest revision as of 01:53, 2 February 2023
In number theory, Wilson's Theorem states that if integer , then
is divisible by
if and only if
is prime. It was stated by John Wilson. The French mathematician Lagrange proved it in 1771.
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
.
Two proofs of the converse are provided: 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 congruent to
, 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
- (Source: ARML 2002) Let
be an integer such that
. Find the remainder when
is divided by
.
Solution
Multiplying both sides by yields
Note that
for all
. Thus we are left with
Advanced
- If
is a prime greater than 2, define
. Prove that
is divisible by
. Solution.
- 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
.