Difference between revisions of "Wilson's Theorem"

Revision as of 15:05, 5 August 2013

Wilson's Theorem is a result in elementary number theory. It states that if $p > 1$ is in integer, then $(p-1)! + 1$ is a multiple of $p$ if and only if $p$ is a prime.

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$ .

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 $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 .$ Since this field has only $p-1$ nonzero elements, it follows that $x^p - 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 = \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

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$ .

Advanced

If ${p}$ is a prime greater than 2, define $p=2q+1$ . Prove that $(q!)^2 + (-1)^q$ is divisible by ${p}$ . <url>Forum/viewtopic.php?&t=21733 Solution</url>

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}$ .

@@ Line 7: / Line 7: @@
 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 ===
+==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>&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

Page

Toolbox

Search