Difference between revisions of "Wilson's Theorem"

Revision as of 00:00, 20 November 2007

Statement

If and only if ${p}$ is a prime, then $(p-1)! + 1$ is a multiple of ${p}$ . In other words $(p-1)! \equiv -1 \pmod{p}$ .

Proof

Wilson's theorem is easily verifiable for 2 and 3, so let's consider $p>3$ . If ${p}$ is composite, then its positive factors are among

$1, 2, 3, \dots, p-1$ .

Hence, $\gcd( (p - 1)!, p) > 1$ , so $(p-1)! \neq -1 \pmod{p}$ .

However, if ${p}$ is prime, then each of the above integers are relatively prime to ${p}$ . So, for each of these integers a, there is another $b$ such that $ab \equiv 1 \pmod{p}$ . It is important to note that this $b$ is unique modulo ${p}$ , and that since ${p}$ is prime, $a = b$ if and only if ${a}$ is $1$ or $p-1$ . Now, if we omit 1 and $p-1$ , then the others can be grouped into pairs whose product is congruent to one,

$2\cdot3\cdot4\cdots(p-2) \equiv 1\pmod{p}$

Finally, multiply this equality by $p-1$ to complete the proof.

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

@@ Line 12: / Line 12: @@
 Finally, multiply this equality by <math>p-1</math> to complete the proof.
-==Example==
+== Problems ==
+=== 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>.
+=== 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>. [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>.
-* 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>.
-[http://www.mathlinks.ro/Forum/viewtopic.php?&t=21733 Solution]
 == See also ==

Page

Toolbox

Search