Difference between revisions of "Wilson's Theorem"
Heptadecagon (talk | contribs) (→Algebraic proof: Fermat's little theorem says x^{p-1} \cong 1 (p), not x^p.) |
m (→See also) |
||
(11 intermediate revisions by 4 users not shown) | |||
Line 7: | Line 7: | ||
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. | 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 == | + | ===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 | 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> | <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>. | + | 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> | <cmath> (p-1)! \equiv 1\cdot 1 \cdot (-1) \equiv -1 \pmod{p}, </cmath> | ||
as desired. <math>\blacksquare</math> | as desired. <math>\blacksquare</math> | ||
Line 28: | Line 28: | ||
== Problems == | == Problems == | ||
=== Introductory === | === Introductory === | ||
− | * 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>. | + | * (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 === | === 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>. [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>. | * 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>. | ||
Line 43: | Line 50: | ||
* [[Wilson Prime]] | * [[Wilson Prime]] | ||
− | Category: | + | [[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
.