4 The Theorems of Fermat and Wilson

Chapter 4
The Theorems of Fermat and Wilson

4.1 Fermat’s General Theorem

Let $m$ be any positive integer and let

a_{1}, a_{2}, \dots, a_{φ (m)}

(A)

be the set of $φ (m)$ positive integers not greater than $m$ and prime to $m$ . Let $a$ be any integer prime to $m$ and form the set of integers

a a_{1}, a a_{2}, \dots, a a_{φ (m)}

(B)

No number $a a_{i}$ of the set (B) is congruent to a number $a a_{j}$ , unless $j = i;$ for, from

a a_{i} \equiv a a_{j} mod m

we have $a_{i} \equiv a_{j} mod m$ ; whence $a_{i} = a_{j}$ since both $a_{i}$ and $a_{j}$ are positive and not greater than $m$ . Therefore $j = i$ . Furthermore, every number of the set (B) is congruent to some number of the set (A). Hence we have congruences of the form

\begin{array}{l} a a_{1} & \equiv a_{i_{1}} mod m, \\ a a_{2} & \equiv a_{i_{2}} mod m, \\ ⋮ \\ a a_{φ (m)} & \equiv a_{i_{φ (m)}} mod m . \end{array}

No two numbers in the second members are equal, since $a a_{i} ≢ a a_{j}$ unless $i = j$ . Hence the numbers $a_{i_{1}}, a_{i_{2}}, \dots, a_{i_{φ (m)}}$ are the numbers $a_{1}, a_{2}, \dots, a_{φ (m)}$ in some order. Therefore, if we multiply the above system of congruences together member by member and divide each member of the resulting congruence by $a_{1} \cdot a_{2} \dots a_{φ (m)}$ (which is prime to $m$ ), we have

a^{φ (m)} \equiv 1 mod m .

This result is known as Fermat’s general theorem. It may be stated as follows:

If $m$ is any positive integer and $a$ is any integer prime to $m$ , then

a^{φ (m)} \equiv 1 mod m .

COROLLARY 1. If $a$ is any integer not divisible by a prime number $p$ , then

a^{p - 1} \equiv 1 mod p .

COROLLARY 2. If $p$ is any prime number and $a$ is any integer, then

a^{p} \equiv a mod p .

4.2 Euler’s Proof of the Simple Fermat Theorem

The theorem of Cor. 1, § 4.1, is often spoken of as the simple Fermat theorem. It was ﬁrst announced by Fermat in 1679, but without proof. The ﬁrst proof of it was given by Euler in 1736. This proof may be stated as follows:

From the Binomial Theorem it follows readily that

\begin{matrix} {(a + 1)}^{p} \equiv a^{p} + 1 mod p \end{matrix}

since

\begin{matrix} \frac{p!}{r! (p - r)!}, 0 < r < p, \end{matrix}

is obviously divisible by $p$ . Subtracting $a + 1$ from each side of the foregoing congruence, we have

\begin{matrix} {(a + 1)}^{p} - (a + 1) \equiv a^{p} - a mod p . \end{matrix}

Hence if $a^{p} - a$ is divisible by $p$ , so is ${(a + 1)}^{p} - (a + 1)$ . But $1^{p} - 1$ is divisible by $p$ . Hence $2^{p} - 2$ is divisible by $p$ ; and then $3^{p} - 3$ ; and so on. Therefore, in general, we have

a^{p} \equiv a mod p .

If $a$ is prime to $p$ this gives $a^{p - 1} \equiv 1 mod p$ , as was to be proved.

If instead of the Binomial Theorem one employs the Polynomial Theorem, an even simpler proof is obtained. For, from the latter theorem, we have readily

\begin{matrix} {(α_{1} + α_{2} + \dots + α_{a})}^{p} \equiv α_{1}^{p} + α_{2}^{p} + \dots + α_{a}^{p} mod p . \end{matrix}

Putting $α_{1} = α_{2} = \dots = α_{a} = 1$ we have

\begin{matrix} a^{p} \equiv a mod p, \end{matrix}

from which the theorem follows as before.

4.3 Wilson’s Theorem

From the simple Fermat theorem it follows that the congruence

\begin{matrix} x^{p - 1} \equiv 1 mod p \end{matrix}

has the $p - 1$ solutions $1$ , $2$ , $3$ , $\dots$ , $p - 1$ . Hence from the discussion in §3.4 it follows that

\begin{matrix} x^{p - 1} \equiv (x - 1) (x - 2) \dots (x - \bar{p - 1}) mod p, \end{matrix}

this relation being satisﬁed for every value of $x$ . Putting $x = 0$ we have

\begin{matrix} (- 1) = {(- 1)}^{p - 1} \cdot 1 \cdot 2 \cdot 3 \dots \bar{p - 1} mod p . \end{matrix}

If $p$ is an odd prime this leads to the congruence

\begin{matrix} 1 \cdot 2 \cdot 3 \dots \bar{p - 1} + 1 = 0 mod p . \end{matrix}

Now for $p = 2$ this congruence is evidently satisﬁed. Hence we have the Wilson theorem:

Every prime number $p$ satisﬁes the relation

1 \cdot 2 \cdot 3 \dots \bar{p + 1} + 1 \equiv 0 mod p .

An interesting proof of this theorem on wholly diﬀerent principles may be given. Let $p$ points be distributed at equal intervals on the circumference of a circle. The whole number of $p$ -gons which can be formed by joining up these $p$ points in every possible order is evidently

\frac{1}{2 p} p (p - 1) (p - 2) \dots 3 \cdot 2 \cdot 1;

for the ﬁrst vertex can be chosen in $p$ ways, the second in $p - 1$ ways, $\dots$ , the ${(p - 1)}^{t h}$ in two ways, and the last in one way; and in counting up thus we have evidently counted each polygon $2 p$ times, once for each vertex and for each direction from the vertex around the polygon. Of the total number of polygons $\frac{1}{2} (p - 1)$ are regular (convex or stellated) so that a revolution through $\frac{36 0^{\circ}}{p}$ brings each of these into coincidence with its former position. The number of remaining $p$ -gons must be divisible by $p$ ; for with each such $p$ -gon we may associate the $p - 1$ $p$ -gons which can be obtained from it by rotating it through successive angles of $\frac{36 0^{\circ}}{p}$ . That is,

\begin{matrix} \frac{1}{2 p} p (p - 1) (p - 2) \dots 3 \cdot 2 \cdot 1 - \frac{1}{2} (p - 1) \equiv 0 mod p . \end{matrix}

Hence

\begin{matrix} (p - 1) (p - 2) \dots 3 \cdot 2 \cdot 1 - p + 1 \equiv 0 mod p; \end{matrix}

and from this it follows that

\begin{matrix} 1 \cdot 2 \dots \bar{p - 1} + 1 \equiv 0 mod p, \end{matrix}

as was to be proved.

4.4 The Converse of Wilson’s Theorem

Wilson’s theorem is noteworthy in that its converse is also true. The converse may be stated as follows:

Every integer $n$ such that the congruence

1 \cdot 2 \cdot 3 \dots \bar{n - 1} + 1 \equiv 0 mod n

is satisﬁed is a prime number.

For, if $n$ is not prime, there is some divisor $d$ of $n$ diﬀerent from $1$ and less than $n$ . For such a $d$ we have $1 \cdot 2 \cdot 3 \dots \bar{n - 1} \equiv 0 mod d$ ; so that $1 \cdot 2 \dots \bar{n - 1} + 1 ≢ 0 mod d$ ; and hence $1 \cdot 2 \dots \bar{n - 1} + 1 \equiv 0 mod n$ . Since this contradicts our hypothesis the truth of the theorem follows.

Wilson’s theorem and its converse may be combined into the following elegant theorem:

A necessary and suﬃcient condition that an integer $n$ is prime is that

1 \cdot 2 \cdot 3 \dots \bar{n - 1} + 1 \equiv 0 mod n .

Theoretically this furnishes a complete and elegant test as to whether a given number is prime. But, practically, the labor of applying it is so great that it is useless for verifying large primes.

4.5 Impossibility of $1 \cdot 2 \cdot 3 \dots \bar{n - 1} + 1 = n^{k}$ for $n > 5$ .

In this section we shall prove the following theorem:

There exists no integer $k$ for which the equation

1 \cdot 2 \cdot 3 \dots \bar{n - 1} + 1 = n^{k}

is true when $n$ is greater than $5$ .

If $n$ contains a divisor $d$ diﬀerent from $1$ and $n$ , the equation is obviously false; for the second member is divisible by $d$ while the ﬁrst is not. Hence we need to prove the theorem only for primes $n$ .

Transposing $1$ to the second member and dividing by $n - 1$ we have

1 \cdot 2 \cdot 3 \dots \bar{n - 2} = n^{k - 1} + n^{k - 2} + \dots + n + 1 .

If $n > 5$ the product on the left contains both the factor $2$ and the factor $\frac{1}{2} (n - 1)$ ; that is, the ﬁrst member contains the factor $n - 1$ . But the second member does not contain this factor, since for $n = 1$ the expression $n^{k - 1} + \dots n + 1$ is equal to $k \neq 0$ . Hence the theorem follows at once.

4.6 Extension of Fermat’s Theorem

The object of this section is to extend Fermat’s general theorem and incidentally to give a new proof of it. We shall base this proof on the simple Fermat theorem, of which we have already given a simple independent proof. This theorem asserts that for every prime $p$ and integer $a$ not divisible by $p$ , we have the congruence

a^{p - 1} \equiv 1 mod p .

Then let us write

a^{p - 1} = 1 + h p .

(1)

Raising each member of this equation to the $p^{th}$ power we may write the result in the form

a^{p (p - 1)} = 1 + h_{1} p^{2} .

(2)

where $h_{1}$ is an integer. Hence

a^{p (p - 1)} \equiv 1 mod p^{2} .

By raising each member of (2) to the $p^{th}$ power we can readily show that

a^{p^{2} (p - 1)} \equiv 1 mod p^{3} .

It is now easy to see that we shall have in general

a^{p^{α - 1} (p - 1)} \equiv 1 mod p^{α} .

where $α$ is a positive integer; that is,

a^{φ (p^{α})} \equiv 1 mod p^{α} .

For the special case when $p$ is 2 this result can be extended. For this case (1) becomes

a = 1 + 2 h .

Squaring we have

a^{2} = 1 + 4 h (h + 1) .

Hence,

a^{2} = 1 + 8 h_{1},

(3)

where $h_{1}$ is an integer. Therefore

a^{2} \equiv 1 mod 2^{3} .

Squaring (3) we have

a^{2^{2}} = 1 + 2^{4} h_{2};

a^{2^{2}} \equiv 1 mod 2^{4} .

It is now easy to see that we shall have in general

a^{2^{α - 2}} \equiv 1 mod 2^{α}

if $α > 2$ . That is,

a^{\frac{1}{2} φ (2^{α})} \equiv 1 mod 2^{α} if a > 2 .

(4.1)

Now in terms of the $φ$ -function let us deﬁne a new function $λ (m)$ as follows:

\begin{array}{l} λ (2^{α}) & = φ (2^{α}) if a = 0, 1, 2; \\ λ (2^{α}) & = \frac{1}{2} φ (2^{α}) if a > 2; \\ λ (p^{α}) & = φ (p^{α}) if p is an odd prime; \\ λ (2^{α} p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{n}^{α_{n}}) & = M, \end{array}

where $M$ is the least common multiple of

λ (2^{α}), λ (p_{1}^{α_{1}}), λ (p_{2}^{α_{2}}), \dots, λ (p_{n}^{α_{n}}),

$2, p_{1}, p_{2}, \dots, p_{n}$ being diﬀerent primes.

Denote by $m$ the number

m = 2^{α} p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{n}^{α_{n}} .

Let $a$ be any number prime to $m$ . From our preceding results we have

\begin{array}{l} a^{λ (2^{α})} & \equiv 1 mod 2^{α}, \\ a^{λ (p_{1}^{α_{1}})} & \equiv 1 mod p_{1}^{α_{1}}, \\ a^{λ (p_{2}^{α_{2}})} & \equiv 1 mod p_{2}^{α_{2}}, \\ \dots \\ a^{λ (p_{n}^{α_{n}})} & \equiv 1 mod p_{2}^{α_{n}} . \end{array}

Now any one of these congruences remains true if both of its members are raised to the same positive integral power, whatever that power may be. Then let us raise both members of the ﬁrst congruence to the power $\frac{λ (m)}{λ (2^{α})}$ ; both members of the second congruence to the power $\frac{λ (m)}{λ (p_{1}^{α_{1}})}$ ; $\dots$ ; both members of the last congruence to the power $\frac{λ (m)}{λ (p_{n}^{α_{n}})}$ . Then we have

\begin{array}{l} a^{λ (m)} & \equiv 1 mod 2^{α}, \\ a^{λ (m)} & \equiv 1 mod p_{1}^{α_{1}}, \\ \dots \dots \\ a^{λ (m)} & \equiv 1 mod p_{n}^{α_{n}} . \end{array}

From these congruences we have immediately

\begin{array}{l} a^{λ (m)} & \equiv 1 mod m . \end{array}

We may state this result in full in the following theorem:

If $a$ and $m$ are any two relatively prime positive integers, the congruence

a^{λ (m)} \equiv 1 mod m .

is satisﬁed.

As an excellent example to show the possible diﬀerence between the exponent $λ (m)$ in this theorem and the exponent $φ (m)$ in Fermat’s general theorem, let us take

\begin{matrix} m = 2^{6} \cdot 3^{3} \cdot 5 \cdot 7 \cdot 13 \cdot 17 \cdot 19 \cdot 37 \cdot 73 . \end{matrix}

Here

\begin{matrix} λ (m) = 2^{4} \cdot 3^{2}, φ (m) = 2^{31} \cdot 3^{10} . \end{matrix}

In a later chapter we shall show that there is no exponent $ν$ less than $λ (m)$ for which the congruence

a^{ν} = 1 mod m

is veriﬁed for every integer $a$ prime to $m$ .

From our theorem, as stated above, Fermat’s general theorem follows as a corollary, since $λ (m)$ is obviously a factor of $φ (m)$ ,

φ (m) = φ (2^{α}) φ (p_{1}^{α_{1}}) \dots φ (p_{n}^{α_{n}}) .

EXERCISES

1.

Show that

a^{16} \equiv 1 mod 16320

, for every

a

which is prime to

16320

2.

Show that

a^{12} \equiv 1 mod 65520

, for every

a

which is prime to

65520

3*.

Find one or more composite numbers

P

such that

a^{P - 1} \equiv 1 mod P

for every a prime to $P$ . (Compare this problem with the next section.)

4.7 On the Converse of Fermat’s Simple Theorem

The fact that the converse of Wilson’s theorem is a true proposition leads one naturally to inquire whether the converse of Fermat’s simple theorem is true. Thus, we may ask the question: Does the existence of the congruence $2^{n - 1} \equiv 1 mod n$ require that $n$ be a prime number? The Chinese answered this question in the aﬃrmative and the answer passed unchallenged among them for many years. An example is suﬃcient to show that the theorem is not true. We shall show that

2^{340} \equiv 1 mod 341

although $341 = 11 \cdot 31$ , is not a prime number. Now $2^{10} - 1 = 3 \cdot 11 \cdot 31$ . Hence $2^{10} \equiv 1 mod 341$ . Hence $2^{340} \equiv 1 mod 341$ . From this it follows that the direct converse of Fermat’s theorem is not true. The following theorem, however, which is a converse with an extended hypothesis, is readily proved.

If there exists an integer $a$ such that

a^{n - 1} \equiv 1 mod n

and if further there does not exist an integer $ν$ less than $n - 1$ such that

a^{ν} \equiv 1 mod n,

then the integer $n$ is a prime number.

For, if $n$ is not prime, $φ (n) < n - 1$ . Then for $ν = φ (n)$ we have $a^{ν} \equiv 1 mod n$ , contrary to the hypothesis of the theorem.

4.8 Application of Previous Results to Linear Congruences

The theorems of the present chapter aﬀord us a ready means of writing down a solution of the congruence

a x \equiv c mod m .

(1)

We shall consider only the case in which $a$ and $m$ are relatively prime, since the general case is easily reducible to this one, as we saw in the preceding chapter.

Since $a$ and $m$ are relatively prime we have the congruences

\begin{matrix} a^{λ (m)} \equiv 1, a^{φ (m)} \equiv 1 mod m . \end{matrix}

Hence either of the numbers $x$ ,

\begin{matrix} x = c a^{λ (m) - 1}, x = c a^{φ (m) - 1}, \end{matrix}

is a representative of the solution of (1). Hence the following theorem:

\begin{matrix} a x \equiv c mod m \end{matrix}

is any linear congruence in which $a$ and $m$ are relatively prime, then either of the numbers $x$ ,

\begin{matrix} x = c a^{λ (m) - 1}, x = c a^{φ (m) - 1}, \end{matrix}

is a representative of the solution of the congruence.

The former representative of the solution is the more convenient of the two, since the power of $a$ is in general much less in this case than in the other.

EXERCISE

: Find a solution of $7 x \equiv 1 mod 2^{6} \cdot 3 \cdot 5 \cdot 17 .$ Note the greater facility in applying the ﬁrst of the above representatives of the solution rather than the second.

4.9 Application of the Preceding Results to the Theory of Quadratic Residues

In this section we shall apply the preceding results of this chapter to the problem of ﬁnding the solutions of congruences of the form

α z^{2} + β z + γ \equiv 0 mod μ

where $α, β, γ, μ$ are integers. These are called quadratic congruences.

The problem of the solution of the quadratic congruence (1) can be reduced to that of the solution of a simpler form of congruence as follows: Congruence (1) is evidently equivalent to the congruence

4 α^{2} z^{2} + 4 α β z + 4 α γ \equiv 0 mod 4 α μ .

(1)

But this may be written in the form

{(2 α z + β)}^{2} \equiv β^{2} - 4 α γ mod 4 α μ .

Now if we put

2 α z + β \equiv x mod 4 α μ

(2)

and

β^{2} - 4 α γ = a, 4 α μ = m,

we have

x^{2} \equiv a mod m .

(3)

We have thus reduced the problem of solving the general congruence (1) to that of solving the binomial congruence (3) and the linear congruence (2). The solution of the latter may be eﬀected by means of the results of §4.8. We shall therefore conﬁne ourselves now to a study of congruence (3). We shall make a further limitation by assuming that $a$ and $m$ are relatively prime, since it is obvious that the more general case is readily reducible to this one.

The example

x^{2} \equiv 3 mod 5

shows at once that the congruence (3) does not always have a solution. First of all, then, it is necessary to ﬁnd out in what cases (3) has a solution. Before taking up the question it will be convenient to introduce some deﬁnitions.

DEFINITIONS. An integer $a$ is said to be a quadratic residue modulo $m$ or a quadratic non-residue modulo $m$ according as the congruence

x^{2} = a mod m

has or has not a solution. We shall conﬁne our attention to the case when $m > 2$ .

We shall now prove the following theorem:

I. If $a$ and $m$ are relatively prime integers, a necessary condition that $a$ is a quadratic residue modulo $m$ is that

a^{\frac{1}{2} λ (m)} \equiv 1 mod m .

Suppose that the congruence $x^{2} = a mod m$ has the solution $x = α$ . Then $a^{2} \equiv a mod m$ . Hence

a^{λ (m)} \equiv a^{\frac{1}{2} λ (m)} mod m .

Since $a$ is prime to $m$ it is clear from $α^{2} \equiv a mod m$ that $a$ is prime to $m$ . Hence $α^{λ (m)} \equiv 1 mod m$ . Therefore we have

1 \equiv a^{\frac{1}{2} λ (m)} mod m .

That is, this is a necessary condition in order that $a$ shall be a quadratic residue modulo $m$ .

In a similar way one may prove the following theorem:

II. If $a$ and $m$ are relatively prime integers, a necessary condition that $a$ is a quadratic residue modulo $m$ is that

a^{\frac{1}{2} φ (m)} \equiv 1 mod m .

When $m$ is a prime number $p$ each of the above results takes the following form: If $a$ is prime to $p$ and is a quadratic residue modulo $p$ , then

a^{\frac{1}{2} (p - 1)} \equiv 1 mod p .

We shall now prove the following more complete theorem, without the use of I or II.

III. If $p$ is an odd prime number and $a$ is an integer not divisible by $p$ , then $a$ is a quadratic residue or a quadratic non-residue modulo $p$ according as

a^{\frac{1}{2} (p - 1)} \equiv + 1 or a^{\frac{1}{2} (p - 1)} \equiv - 1 mod p .

This is called Euler’s criterion.

Given a number $a$ , not divisible by $p$ , we have to determine whether or not the congruence

x^{2} \equiv a mod p

has a solution. Let $r$ be any number of the set

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

(A)

and consider the congruence

r x \equiv a mod p .

(4.2)

This has always one and just one solution $x$ equal to a number $s$ of the set (A). Two cases can arise: either for every $r$ of the set (A) the corresponding $s$ is diﬀerent from $r$ or for some $r$ of the set (A) the corresponding $s$ is equal to $r$ . The former is the case when $a$ is a quadratic non-residue modulo $p$ ; the latter is the case when $a$ is a quadratic residue modulo $p$ . We consider the two cases separately.

In the ﬁrst case the numbers of the set (A) go in pairs such that the product of the numbers in the pair is congruent to a modulo $p$ . Hence, taking the product of all $\frac{1}{2} (p - 1)$ pairs, we have

\begin{array}{l} 1 \cdot 2 \cdot 3 \dots \bar{p - 1} & \equiv + a^{\frac{1}{2} (p - 1)} mod p . \end{array}

But

\begin{array}{l} 1 \cdot 2 \cdot 3 \dots \bar{p - 1} & = - 1 mod p . \end{array}

Hence

\begin{array}{l} a^{\frac{1}{2} (p - 1)} \equiv - 1 mod p, \end{array}

whence the truth of one part of the theorem.

In the other case, namely that in which some $r$ and corresponding $s$ are equal, we have for this $r$

\begin{matrix} r^{2} \equiv a mod p \end{matrix}

and

\begin{matrix} {(p - r)}^{2} \equiv a mod p . \end{matrix}

Since $x^{2} \equiv a mod p$ has at most two solutions it follows that all the integers in the set (A) except $r$ and $p - r$ fall in pairs such that the product of the numbers in each pair is congruent to a modulo $p$ . Hence, taking the product of all these pairs, which are $\frac{1}{2} (p - 1) - 1$ in number, and multiplying by $r (p - r)$ we have

\begin{array}{l} 1 \cdot 2 \cdot 3 \dots \bar{p - 1} & \equiv (p - r) r a^{\frac{1}{2} (p - 1) - 1} mod p \\ \equiv - r^{2} a^{\frac{1}{2} (p - 1) - 1} mod p \\ \equiv - a a^{\frac{1}{2} (p - 1) - 1} mod p \\ \equiv - a^{\frac{1}{2} (p - 1)} mod p . \end{array}

Since $1 \cdot 2 \cdot 3 \dots \bar{p - 1} \equiv mod p$ we have

\begin{array}{l} a^{\frac{1}{2} (p - 1)} & \equiv + 1 mod p \end{array}

whence the truth of another part of the theorem.

Thus the proof of the entire theorem is complete.

ptail

top

Chapter 4The Theorems of Fermat and Wilson