# Difference between revisions of "Wilson's Theorem"

(→Introductory) |
(→Solution) |
||

(2 intermediate revisions by the same user not shown) | |||

Line 35: | Line 35: | ||

<cmath>\frac{23!}{1}+\frac{23!}{2}+...+\frac{23!}{23}=a</cmath> | <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 | 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! | + | <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 === |

## Latest revision as of 22:48, 9 January 2020

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 conguent to 1 modulo , 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 .

## See also

Category: Number Theory