Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Wilson's Theorem"

m (organization)
m (→‎See also)
 
(24 intermediate revisions by 13 users not shown)
Line 1: Line 1:
−
== Statement ==
+
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.
−
If and only if <math>{p}</math> is a [[prime]], then <math>(p-1)! + 1</math> is a multiple of <math>{p}</math>.  In other words <math>(p-1)! \equiv -1 \pmod{p}</math>.
 
  
−
== Proof ==
+
== Proofs ==
−
Wilson's theorem is easily verifiable for 2 and 3, so let's consider <math>p>3</math>.  If <math>{p}</math> is composite, then its positive factors are among
 
−
<center><math>1, 2, 3, \dots, p-1</math>.</center>  <br>
 
−
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,
+
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>.
−
<center><math>2\cdot3\cdot4\cdots(p-2) \equiv 1\pmod{p}</math></center>  <br>
 
  
−
Finally, multiply this equality by <math>p-1</math> to complete the proof.
+
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.
  
−
==Example==
+
===Elementary proof===
  
−
* 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>.
+
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>&mdash;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>
  
−
* If <math>\displaystyle{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>\displaystyle{p}</math>.
+
=== 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.]
  
−
[http://www.mathlinks.ro/Forum/viewtopic.php?&t=21733 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 ==
 
== See also ==
 +
 
* [[Number theory]]
 
* [[Number theory]]
 
* [[Modular arithmetic]]
 
* [[Modular arithmetic]]
 +
* [[Fermat's Little Theorem]]
 
* [[Factorial]]
 
* [[Factorial]]
 +
* [[Wilson Prime]]
 +
 +
[[Category:Number theory]]

Latest revision as of 00:53, 2 February 2023

In number theory, Wilson's Theorem states that if integer $p > 1$ , then $(p-1)! + 1$ is divisible by $p$ if and only if $p$ is prime. It was stated by John Wilson. The French mathematician Lagrange proved it in 1771.

Proofs

Suppose first that $p$ is composite. Then $p$ has a factor $d > 1$ that is less than or equal to $p-1$. Then $d$ divides $(p-1)!$, so $d$ does not divide $(p-1)! + 1$. Therefore $p$ does not divide $(p-1)! + 1$.

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 $p$ is a prime. Then each of the integers $1, \dotsc, p-1$ has an inverse modulo $p$. (Indeed, if one such integer $a$ does not have an inverse, then for some distinct $b$ and $c$ modulo $p$, $ab \equiv ac \pmod{p}$, so that $a(b-c)$ is a multiple of $p$, when $p$ does not divide $a$ or $b-c$—a contradiction.) This inverse is unique, and each number is the inverse of its inverse. If one integer $a$ is its own inverse, then \[0 \equiv a^2 - 1 \equiv (a-1)(a+1) \pmod{p} ,\] so that $a \equiv 1$ or $a \equiv p-1$. Thus we can partition the set $\{ 2 ,\dotsc, p-2\}$ into pairs $\{a,b\}$ such that $ab \equiv 1 \pmod{p}$. It follows that $(p-1)!$ is the product of these pairs times $1 \cdot (-1)$. Since the product of each pair is congruent to $1 \bmod p$, we have \[(p-1)! \equiv 1\cdot 1 \cdot (-1) \equiv -1 \pmod{p},\] as desired. $\blacksquare$

Algebraic proof

Let $p$ be a prime. Consider the field of integers modulo $p$. By Fermat's Little Theorem, every nonzero element of this field is a root of the polynomial \[P(x) = x^{p-1} - 1 .\] Since this field has only $p-1$ nonzero elements, it follows that \[x^{p-1} - 1 = \prod_{r=1}^{p-1}(x-r) .\] Now, either $p=2$, in which case $a \equiv -a \pmod 2$ for any integer $a$, or $p-1$ is even. In either case, $(-1)^{p-1} \equiv 1 \pmod{p}$, so that \[x^{p-1} - 1 = \prod_{r=1}^{p-1}(x-r) = \prod_{r=1}^{p-1}(-x + r) .\] If we set $x$ equal to 0, the theorem follows. $\blacksquare$

Problems

Introductory

  • (Source: ARML 2002) Let $a$ be an integer such that $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{23}=\frac{a}{23!}$. Find the remainder when $a$ is divided by $13$.

Solution

Multiplying both sides by $23!$ yields \[\frac{23!}{1}+\frac{23!}{2}+...+\frac{23!}{23}=a\] Note that $13\mid\frac{23!}{k}$ for all $k\neq13$. Thus we are left with \[a\equiv\frac{23!}{13}\equiv12!\cdot14\cdot15\cdot16\cdot...\cdot23\equiv(-1)(1)(2)(3)(...)(10)\equiv\boxed{7}\mod13\]

Advanced

  • If ${p}$ is a prime greater than 2, define $p=2q+1$. Prove that $(q!)^2 + (-1)^q$ is divisible by ${p}$. Solution.
  • Let ${p}$ be a prime number such that dividing ${p}$ by 4 leaves the remainder 1. Show that there is an integer ${n}$ such that $n^2 + 1$ is divisible by ${p}$.

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Wilson%27s_Theorem&oldid=188501"