Difference between revisions of "Wilson's Theorem"

(Solution)
(Solution)
Line 37: Line 37:
 
<cmath>\begin{align*}
 
<cmath>\begin{align*}
 
a&\equiv \frac{23!}{13}(\mod13)
 
a&\equiv \frac{23!}{13}(\mod13)
&\equiv 12!14\cdot15\cdot16\cdot...\cdot13 (\mod13)</cmath>
+
&\equiv 12!14\cdot15\cdot16\cdot...\cdot13 (\mod13)
 +
\end{align*}</cmath>
  
 
=== Advanced ===
 
=== Advanced ===

Revision as of 22:37, 9 January 2020

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 conguent to 1 modulo $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 \begin{align*} a&\equiv \frac{23!}{13}(\mod13) &\equiv 12!14\cdot15\cdot16\cdot...\cdot13 (\mod13) \end{align*}

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

Category: Number Theory