## A Book of Abstract Algebra, Second Edition (1982)

### Chapter 23. ELEMENTS OF NUMBER THEORY (OPTIONAL)

Almost as soon as children are able to count, they learn to distinguish between even numbers and odd numbers. The distinction between even and odd is the most elemental of all concepts relating to numbers. It is also the starting point of the modern science of number theory.

From a sophisticated standpoint, a number is even if the remainder, after dividing the number by 2, is 0. The number is odd if that remainder is 1.

This notion may be generalized in an obvious way. Let *n* be any positive integer: a number is said to be *congruent to* 0, *modulo n* if the remainder, when the number is divided by ft, is 0. The number is said to be *congruent to* 1, *modulo n* if the remainder, when the number is divided by is 1. Similarly, the number is *congruent to* 2, *modulo n* if the remainder after division by ft is 2; and so on. This is the natural way of generalizing the distinction between odd and even.

Note that “even” is the same as “congruent to 0, modulo 2”; and “odd” is the same as “congruent to 1, modulo 2.”

In short, the distinction between odd and even is only one special case of a more general notion. We shall now define this notion formally:

Let *n* be any positive integer. If *a* and *b* are any two integers, we shall say that *a is congruent to b, modulo n if a* and *b*, when they are divided by *n*, leave the same remainder *r*. That is, if we use the division algorithm to divide *a*and *b* by *n*, then

*a* = *nq*_{1} + *r* and *b* = *nq*_{2} + *r*

where the remainder *r* is the same in both equations.

Subtracting these two equations, we see that

*a* − *b* = (*nq*_{1} + *r*) − (*nq*_{2} + *r*) = *n*(*q*_{1} − *q*_{2})

Therefore we get the following important fact:

*a is congruent to b, modulo n iff n divides a − b* (1)

If *a* is congruent to *b*, modulo *n*, we express this fact in symbols by writing

*a* ≡ *b* (mod *n*)

which should be read “a is congruent to *b*, modulo *n*.” We refer to this relation as *congruence modulo n*.

By using Condition (1), it is easily verified that congruence modulo *n* is a reflexive, symmetric, and transitive relation on . It is also easy to check that for any *n* > 0 and any integers *a, b*, and *c*,

*a* ≡ *b* (mod *n*) implies *a* + *c* ≡ *b* + *c* (mod *n*)

and

*a* ≡ *b* (mod *n*) implies *ac* ≡ *bc* (mod *n*)

(The proofs, which are exceedingly easy, are assigned as __Exercise C__ at the end of this chapter.)

Recall that

⟨*n*⟩ = {…, −3*n*, −2*n*, −*n*, 0, *n*, 2*n*, 3*n*,…}

is the ideal of which consists of all the multiples of *n*. The quotient ring /⟨*n*⟩ is usually denoted by * _{n}*, and its elements are denoted by . These elements are cosets:

and so on. It is clear by inspection that different integers are in the same coset iff they differ from each other by a multiple of *n*. That is,

If *a* is any integer, the coset (in * _{n}*) which contains

*a*will be denoted by . For example, in

_{6},

In particular, means that *a* and *b* are in the same coset. It follows by Condition (2) that

On account of this fundamental connection between congruence modulo *n* and equality in * _{n}*, most facts about congruence can be discovered by examining the rings

*. These rings have very simple properties, which are presented next. From these properties we will then be able to deduce all we need to know about congruences.*

_{n}Let *n* be a positive integer. It is an important fact that for any integer *a*,

Indeed, if *a* and *n* are relatively prime, their *gcd* is equal to 1. Therefore, by __Theorem 3__ of __Chapter 22__, there are integers *s* and *t* such that *sa* + *tn* = 1. It follows that

1 − *sa* = *tn* ∈ ⟨*n*⟩

so by Condition (2) of __Chapter 19__,1 and *sa* belong to the same coset in /⟨*n*⟩. This is the same as saying that ; hence is the multiplicative inverse of in * _{n}*. The converse is proved by reversing the steps of this argument.

It follows from Condition (4) above, that if *n* is a prime number, every nonzero element of * _{n}* is invertible! Thus,

* _{p} is a field for every prime number p*. (5)

In any field, the set of all the nonzero elements, with multiplication as the only operation (ignore addition), is a group. Indeed, the product of any two nonzero elements is nonzero, and the multiplicative inverse of any nonzero element is nonzero. Thus, in * _{p}*, the set

with multiplication as its only operation, *is a group of order p* − 1.

Remember that if *G* is a group whose order is, let us say, *m*, then *x ^{m}* =

*e*for every

*x*in

*G*. (This is true by

__Theorem 5__of

__Chapter 13__.) Now, has order

*p*− 1 and its identity element is , so for every . If we use Condition (3) to translate this equality into a congruence, we get a classical result of number theory:

**Little theorem of Fermat** *Let p be a prime. Then*,

*a ^{p}*

^{ }

^{−}

^{ 1}≡ 1 (mod

*p*)

*for every*

*a*0(mod

*p*)

**Corollary** *a ^{p}* ≡

*a*(mod

*p*)

*for every integer a*.

Actually, a version of this theorem is true in * _{n}* even where

*n*is

*not*a prime number. In this case, let

*V*denote the

_{n}*set of all the invertible elements*in

*. Clearly,*

_{n}*V*is a group with respect to multiplication. (Reason: The product of two invertible elements is invertible, and, if

_{n}*a*is invertible, so is its inverse.) For any positive integer

*n*, let

*ϕ*(

*n*) denote

*the number of positive integers, less than n, which are relatively prime to n*. For example, 1, 3, 5, and 7 are relatively prime to 8; hence

*ϕ*(8) = 4.

*ϕ*is called

*Eulef’s phi−function*.

It follows immediately from Condition (4) that the number of elements in *V _{n}* is

*ϕ*(

*n*).

Thus, *V _{n}* is a group of order

*ϕ*(

*n*), and its identity element is . Consequently, for any in . If we use Condition (3) to translate this equation into a congruence, we get:

**Euler’s theorem** *If a and n are relatively prime, α ^{ϕ}*

^{(n)}≡ 1 (mod

*n*).

**FURTHER TOPICS IN NUMBER THEORY**

Congruences are more important in number theory than we might expect. This is because a vast range of problems in number theory—problems which have nothing to do with congruences at first sight—can be transformed into problems involving congruences, and are most easily solved in that form. An example is given next:

A *Diophantine equation* is any polynomial equation (in one or more unknowns) whose coefficients are integers. To solve a Diophantine equation is to find *integer values* of the unknowns which satisfy the equation. We might be inclined to think that the restriction to integer values makes it easier to solve equations; in fact, the very opposite is true. For instance, even in the case of an equation as simple as 4*x* + 2*y* = 5, it is not obvious whether we can find an integer solution consisting of *x* and *y* in . (As a matter of fact, there is *no* integer solution; try to explain why not.)

Solving Diophantine equations is one of the oldest and most important problems in number theory. Even the problem of solving Diophantine *linear* equations is difficult and has many applications. Therefore, it is a very important fact that *solving linear Diophantine equations is equivalent to solving linear congruences*. Indeed,

*ax* + *by* = *c* iff *by* = *c* −*ax* iff *ax* ≡ *c* (mod *b*)

Thus, any solution of *ax* ≡ *c* (mod *b*) yields a solution in integers of *ax* + *by* = *c*.

Finding solutions of linear congruences is therefore an important matter, and we will turn our attention to it now.

A congruence such as *ax* ≡ *b* (mod *n*) may look very easy to solve, but appearances can be deceptive. In fact, many such congruences have no solutions at all! For example, 4*x* ≡ *5* (mod 2) cannot have a solution, because 4*x* is always even [hence, congruent to 0 (mod 2)], whereas 5 is odd [hence congruent to 1 (mod 2)]. Our first item of business, therefore, is to find a way of recognizing whether or not a linear congruence has a solution.

**Theorem 1** *The congruence ax* ≡ *b* (mod *n*) *has a solution iff* gcd(*a*, *n*) | *b*.

Indeed,

Next, by the proof of __Theorem 3__ in __Chapter 22__, if *J* is the ideal of all the linear combinations of *a* and *n*, then gcd(*a*, *n*) is the least positive integer in *J*. Furthermore, every integer in *J* is a multiple of gcd(*a*, *n*). Thus, *b* is a linear combination of *a* and *n* iff *b* ∈ *J* iff *b* is a multiple of gcd(*a*, *n*). This completes the proof of our theorem.

Now that we are able to recognize when a congruence *has* a solution, let us see what such a solution looks like.

Consider the congruence *ax* ≡ *b* (mod *n*). By a *solution modulo n* of this congruence, we mean a congruence

*x* ≡ *c* (*mod n*)

such that any integer *x* satisfies *x* ≡ *c* (mod *n*) iff it satisfies *ax* ≡ *b* (mod *n*). [That is, the solutions of *ax* ≡ *b* (mod *n*) are all the integers congruent to *c*, modulo *n*.] Does every congruence *ax* ≡ *b* (mod *n*) (supposing that it *has* a solution) have a solution modulo *n*? Unfortunately not! Nevertheless, as a starter, we have the following:

**Lemma** *If* gcd(*a*, *n*) = 1, *then ax* ≡ *b* (mod *n*) *has a solution modulo n*.

PROOF: Indeed, by (3), *ax* ≡ *b* (mod *n*) is equivalent to the equality in * _{n}*. But by Condition (4), has a multiplicative inverse in

*; hence from we get . Setting , we get in*

_{n}*, that is,*

_{n}*x*≡

*c*(mod

*n*). ■

Thus, if *a* and *n* are relatively prime, *ax* ≡ *b* (mod *n*) has a solution modulo *n*. If *a* and *n* are *not* relatively prime, we have no solution modulo *n*; nevertheless, we have a very nice result:

**Theorem 2** *If the congruence ax* ≡ *b* (mod *n*) *has a solution, then it has a solution modulo m, where*

This means that the solution of *ax* ≡ *b* (mod *n*) is of the form *x* ≡ *c* (mod *m*); it consists of all the integers which are congruent to *c*, modulo *m*.

PROOF. To prove this, let gcd(*a, n*) = *d*, and note the following:

But *a*/*d* and *n*/*d* are relatively prime (because we are dividing *a* and *n* by *d*, which is their gcd); hence by the lemma,

has a solution *x* mod *n*/*d*. By Condition (6), this is also a solution of *ax* ≡ *b* (mod *n*). ■

As an example, let us solve 6*x* ≡ 4 (mod 10). Gcd(6,10) = 2 and 2|4, so by Theorem 1, this congruence has a solution. By Condition (6), this solution is the same as the solution of

This is equivalent to the equation in _{5}, and its solution is . So finally, the solution of 6*x* ≡ 4 (mod 10) is *x* ≡ 4 (mod 5).

How do we go about solving several linear congruences simultaneously? Well, suppose we are given *k* congruences,

*a*_{1}*x* ≡ *b*_{1} (mod *n*_{1}), *a*_{2}*x* ≡ *b*_{2} (mod *n*_{2}),…, *a _{k}x* =

*b*(mod

_{k}*n*)

_{k}If each of these congruences has a solution, we solve each one individually by means of Theorem 2. This gives us

*x* ≡ *c*_{1} (mod *m*_{1}), *x* ≡ *c*_{2}(mod *m*_{2}), …, *x* ≡ *c _{k}* (mod

*m*)

_{k}We are left with the problem of solving this last set of congruences simultaneously.

Is there any integer *x* which satisfies all *k* of these congruences? The answer for *two* simultaneous congruences is as follows:

**Theorem 3** *Consider x* ≡ *a* (mod *n*) *and x* ≡ *b* (mod *m*). *There is an integer x satisfying both simultaneously iff a* ≡ *b* (mod *d*), *where d* = gcd(*m*, *n*).

PROOF: If *x* is a simultaneous solution, then *n* | (*x* − *a*) and *m* | (*x* − *b*). Thus,

*x* − *a* = *nq*_{1} and *x* − *b* = *mq*_{2}

Subtracting the first equation from the second gives

*a* − *b* = *mq*_{2} − *nq*_{1}

But *d*|*m* and *d*|*n*, so *d*|(*a* − *b*); thus, *a* ≡ *b* (mod *d*).

Conversely, if *a* ≡ *b* (mod *d*), then *d* | (*a* − *b*), so *a* − *b* = *dq*. By __Theorem 3__ of __Chapter 22__, *d* = *rn* + *tm* for some integers *r* and *t*. Thus, *a* − *b* = *rqn* + *tqm*. From this equation, we get

*a* − *rqn* = *b* + tqm

Set *x* = *a* − *rqn* = *b* + *tqm*; then *x* − *a* = −*rqn* and *x* − *b* = *tqm;* hence *n*|(*x* − *a*) and *m*|(*x* − *b*), so

*x* ≡ *a* (mod *n*) and *x* ≡ *b* (mod *m*) ■

Now that we are able to determine whether or not a pair of congruences *has* a simultaneous solution, let us see what such a solution looks like.

**Theorem 4** *If a pair of congruences x* ≡ *a* (mod *n*) *and x* ≡ *b* (mod *m*) *has a simultaneous solution, then it has a simultaneous solution of the form*

*x* ≡ *c* (mod *t*)

*where t is the least common multiple of m and n*.

Before proving the theorem, let us observe that the least common multiple (1cm) of any two integers ra and *n* has the following property: let *t* be the least common multiple of m and *n. Every common multiple of m and n is a multiple of t, and conversely*. That is, for all integers *x*,

*m*|*x* and *n*|*x* iff *t*|*x*

(See __Exercise F__ at the end of __Chapter 22__.) In particular,

*m*|(*x* − *c*) and *n*|(*x* − *c*) iff *t*|(*x* − *c*)

hence

*x* ≡ *c* (mod *m*) and *x* ≡ *c* (mod *n*) iff *x* ≡ *c* (mod *t*) (7)

Returning to our theorem, let *c* be any solution of the given pair of congruences (remember, we are assuming there *is* a simultaneous solution). Then *c* ≡ *a* (mod *n*) and *c* ≡ *b* (mod *m*). Any other integer *x* is a simultaneous solution iff *x* ≡ *c* (mod *n*) and *x* ≡ *c* (mod *m*). But by Condition (7), this is true iff *x* ≡ *c* (mod *t*). The proof is complete.

A special case of Theorems 3 and 4 is very important in practice: it is the case where *m* and *n* are relatively prime. Note that, in this case, gcd(*m*, *n*) = 1 and lcm(*m*, *n*) = *mn*. Thus, by Theorems 3 and 4,

*If m and n are relatively prime, the pair of congruences x* ≡ *a* (mod *n*) *and x* ≡ *b* (mod *m*) *always* *has a solution. This solution is of the form x* ≡ *c* (mod *mn*).

This statement can easily be extended to the case of more than two linear congruences. The result is known as the

**Chinese remainder theorem** *Let m*_{1},*m*_{2},…,*m _{k} be pairwise relatively prime. Then the system of simultaneous linear congruences*

*x* ≡ *c*_{1} (mod *m*_{1}), *x* ≡ *c*_{2} (mod *m*_{2}), …, *x* = *c _{k}* (mod

*m*)

_{k}*always has a solution, which is of the form x* ≡ *c* (mod *m*_{1}*m*_{2} … *m _{k}*).

Use Theorem 4 to solve *x* ≡ *c*_{1} (mod *m*_{1}) and *x* ≡ *c*_{2} (mod *m*_{2}) simultaneously. The solution is of the form *x* ≡ *d* (mod *m*_{1}*m*_{2}). Solve the latter simultaneously with *x* ≡ *c*_{3} (mod *m*_{3}), to get a solution mod *m*_{1}*m*_{2}*m*_{3}. Repeat this process *k* − 1 times.

**EXERCISES**

**A. Solving Single Congruences**

**1** For each of the following congruences, find *m* such that the congruence has a unique solution modulo *m*. If there is no solution, write “none.”

(*a*) 60*x* ≡ 12 (mod 24)

(*b*) 42*x* ≡ 24 (mod 30)

(*c*) 49*x* ≡ 30 (mod 25)

(*d*) 39*x* ≡ 14 (mod 52)

(*e*) 147*x* ≡ 47 (mod 98)

(*f*) 39*x* ≡ 26 (mod 52)

**2** Solve the following linear congruences:

(*a*) 12*x* ≡ 7 (mod 25)

(*b*) 35*x* ≡ 8 (mod 12)

(*c*) 15*x* ≡ 9 (mod 6)

(*d*) 42*x* ≡ 12 (mod 30)

(*e*) 147*x* ≡ 49 (mod 98)

(*f*)39*x* ≡ 26 (mod 52)

**3** (*a*) Explain why 2*x*^{2} ≡ 8 (mod 10) has the same solutions as *x*^{2} ≡ 4 (mod 5).(*b*) Explain why *x* ≡ 2 (mod 5) and *x* ≡ 3 (mod 5) are all the solutions4 of 2*x*^{2} ≡ 8 (mod 10).

**4** Solve the following quadratic congruences. (If there is no solution, write “none.”)

(*a*) 6*x*^{2} ≡ 9 (mod 15)

(*b*) 60*x*^{2} ≡ 18 (mod 24)

(*c*) 30*x*^{2} ≡ 18 (mod 24)

(*d*) 4(*x* + 1)^{2} ≡ 14 (mod 10)

(*e*) 4*x*^{2} − 2*x* + 2 ≡ 0 (mod 6)

# (* f*) 3

*x*

^{2}− 6

*x*+ 6 ≡ 0 (mod 15)

**5** Solve the following congruences:

(*a*) *x*^{4} ≡ 4 (mod 6)

(*b*) 2(*x* − 1)^{4} ≡ 0 (mod 8)

(*c*) *x*^{3} + 3*x*^{2} + 3*x* + 1 = 0 (mod 8)

(*d*) *x*^{4} + 2*x*^{2} + 1 ≡ 4 (mod 5)

**6** Solve the following Diophantine equations. (If there is no solution, write “none.”)

(*a*) 14*x* + 15*y* = 11

(*b*) 4*x* + 5*y* = 1

(*c*) 21*x* + 10*y* = 9

# (* d*) 30

*x*

^{2}+ 24

*y*= 18

**B. Solving Sets of Congruences**

**Example** *Solve the pair of simultaneous congruences x* ≡ *5* (mod 6), *x* ≡ 7 (mod 10).

By Theorems 3 and 4, this pair of congruences has a solution modulo 30. From *x* ≡ 5 (mod 6), we get *x* ≡ 6*q* + 5. Introducing this into *x* ≡ 7 (mod 10) yields 6*q* + 5 ≡ 7 (mod 10). Thus, successively, 6*q* ≡ 2 (mod 10), 3*q* ≡ 1 (mod 5), *q* ≡ 2 (mod 5), *q* = 5*r* + 2. Introducing this into *x* = 6*q* + 5 gives *x* = 6(5*r* + 2) + 5 = 30*r* + 17. Thus, *x* ≡ 17 (mod 30). This is our solution.

**1** Solve each of the following pairs of simultaneous congruences:

(*a*) *x* ≡ 7 (mod 8); *x* ≡ 11 (mod 12)

(*b*) *x* ≡ 12 (mod 18); *x* ≡ 30 (mod 45)

(*c*) *x* ≡ 8 (mod 15); *x* = 11 (mod 14)

**2** Solve each of the following pairs of simultaneous congruences:

(*a*) 10*x* ≡ 2 (mod 12); 6*x* ≡ 14 (mod 20)

(*b*)4*x* ≡ 2 (mod 6); 9*x* ≡ 3 (mod 12)

(*c*) 6*x* ≡ 2 (mod 8); 10*x* ≡ 2 (mod 12)

**# 3** Use Theorems 3 and 4 to prove the following: Suppose we are given

*k*congruences

*x* = *c*_{1} (mod *m*_{1}), *x* ≡ *c*_{2}(mod *m*_{2}) …, *x* ≡ *c _{k}* (mod

*m*)

_{k}There is an *x* satisfying all *k* congruences simultaneously if for all *i*, *j* ∈ {1, …, *k*}, *c _{i}* ≡

*c*(mod

_{j}*d*), where

_{ij}*d*= gcd(

_{ij}*m*,

_{i}*m*). Moreover, the simultaneous solution is of the form

_{j}*x*≡

*c*(mod

*t*), where

*t*= lcm (

*m*

_{1},

*m*

_{2}, …,

*m*).

_{k}**4** Solving each of the following systems of simultaneous linear congruences; if there is no solution, write “none.”

(*a*) *x* ≡ 2 (mod 3); *x* ≡ 3 (mod 4); *x* = 1 (mod 5); *x* ≡ 4 (mod 7)

(*b*) *6x* ≡ 4 (mod 8); 10*x* ≡ 4 (mod 12); 3*x* ≡ 8 (mod 10)

(*c*) 5*x* ≡ 3 (mod 6); 4*x* ≡ 2 (mod 6); 6*x* ≡ 6 (mod 8)

**5** Solve the following systems of simultaneous Diophantine equations:

*#* (* a*) 4

*x*+ 6

*y*= 2; 9

*x*+ 12

*y*= 3

(*b*) 3*x* + 4*y* = 2; 5*x* + 6*y* = 2; 3*x* + 10*y* = 8.

**C. Elementary Properties of Congruence**

Prove the following for all integers *a*, *b*, *c*, *d* and all positive integers *m* and *n:*

**1** If *a* ≡ *b* (mod *n*) and *b* ≡ *c* (mod *n*), then *a* ≡ *c* (mod *n*).

**2** If *a* ≡ *b* (mod *n*), then *a* + *c* ≡ *b* + *c* (mod *n*).

**3** If *a* ≡ *b* (mod *n*), then *ac* ≡ *bc* (mod *n*).

**4** *a* ≡ *b* (mod 1).

**5** If *ab* ≡ 0 (mod *p*), where *p* is a prime, then *a* ≡ 0 (mod *p*) or *b* ≡ 0 (mod *p*).

**6** If *a*^{2} ≡ *b*^{2} (mod *p*), where *p* is a prime, then *a* ≡ ±*b* (mod *p*).

**7** If *a* ≡ *b* (mod *m*), then *a* + *km* ≡ *b* (mod *m*), for any integer *k*. In particular, *a* + *km* ≡ *a* (mod *m*).

**8** If *ac* ≡ *bc* (mod *n*) and gcd(*c*, *n*) ≡ 1, then *a* ≡ *b* (mod *n*).

**9** If *a* ≡ *b* (mod *n*), then *a* ≡ *b* (mod *m*) for any *m* which is a factor of *n*.

**D. Further Properties of Congruence**

Prove the following for an integers *a*, *b*, *c* and all positive integers *m* and *n*:

**1** If *ac* ≡ *bc* (mod *n*), and gcd(*c*, *n*) ≡ *d*, then *a* ≡ *b* (mod *n*/*d*).

**2** If *a* ≡ *b* (mod *n*), then gcd(*a*, *n*) = gcd(*b*, *n*).

**3** If *a* ≡ *b* (mod *p*) for every prime *p*, then *a* = *b*.

**4** If *a* ≡ *b* (mod *n*), then *a ^{m}* ≡

*b*(mod

^{m}*n*) for every positive integer

*m*.

**5** If *a* ≡ *b* (mod *m*) and *a* ≡ *b* (mod *n*) where gcd(*m*, *n*) = 1, then *a* ≡ *b* (mod *mn*).

**# 6** If

*ab*≡ 1 (mod

*c*),

*ac*≡ 1 (mod

*b*) and

*bc*≡ 1 (mod

*a*), then

*ab*+

*bc*+

*ac*≡ 1 (mod

*abc*). (Assume

*a*,

*b*,

*c*> 0.)

**7** If *a*^{2} ≡ 1 (mod 2), then *a*^{2} ≡ 1 (mod 4).

**8** If *a* ≡ *b* (mod *n*), then *a*^{2} + *b*^{2} ≡ 2*ab* (mod *n*^{2}), and conversely.

**9** If *a* ≡ 1 (mod *m*), then *a* and *m* are relatively prime.

**E. Consequences of Fermat’s Theorem**

**1** If *p* is a prime, find *ϕ*(*p*). Use this to deduce Fermat’s theorem from Euler’s theorem.

Prove parts 2-6:

**2** If *p* > 2 is a prime and *a* 0 (mod *p*), then

*a*^{(p }^{−}^{ 1)/2} ≡ ±1(mod *p*)

**3**(*a*) Let *p* a prime > 2. If *p* ≡ 3 (mod 4), then (*p* − 1)/2 is odd.

(*b*) Let *p* > 2 be a prime such that *p* ≡ 3 (mod 4). Then there is *no* solution to the congruence *x*^{2} + 1 ≡ 0 (mod *p*). [H_{INT}: Raise both sides of *x*^{2} ≡ −1 (mod *p*) to the power (*p* − 1)/2, and use Fermat’s little theorem.]

**# 4** Let

*p*and

*q*be distinct primes. Then

*p*

^{q}^{ }

^{−}

^{ 1}+

*q*

^{p}^{ }

^{−}

^{ 1}≡ 1(mod

*pq*).

**5** Let *p* be a prime.

(*a*) If, (*p* − 1) | *m*, then *a ^{m}* ≡ 1 (mod

*p*) provided that

*p*

*a*.

(*b*) If, (*p* − 1)| *m*, then *a ^{m}*

^{ + 1}≡

*a*(mod

*pq*) for all integers

*a*.

**# 6** Let

*p*and

*q*be distinct primes.

(*a*) If (*p* − 1) | *m* and (*q* − 1) | *m*, then *a ^{m}* ≡ 1 (mod

*pq*) for any

*a*such that

*p*

*a*and

*q*

*a*.

(*b*) If (*p* − 1) | *m* and (*q* − 1) | *m*, then *a ^{m}*

^{ + 1}≡

*a*(mod

*pq*) for integers

*a*.

**7** Generalize the result of part 6 to *n* distinct primes, *p*_{1}…, *p _{n}*. (State your result, but do not prove it.)

**8** Use part 6 to explain why the following are true:

# (* a*)

*a*

^{19}≡

*a*(mod 133).

(*b*) *a*^{10} ≡ 1 (mod 66), provided *a* is not a multiple of 2, 3, or 11.

(*c*) *a*^{13} ≡ *a* (mod 105).

(*d*) *a*^{49} ≡ *a* (mod 1547). (HINT: 1547 = 7 × 13 × 17.)

**9** Find the following integers *x:*

(*a*) *x* ≡ 8^{38} (mod 210)

(*b*) *x* ≡ 7^{57} (mod 133)

(*c*) *x* ≡ 5^{73} (mod 66)

**F. Consequences of Euler’s Theorem**

Prove parts 1-6:

**1** If gcd (*a, n*) = 1, the solution modulo *n* of *ax* ≡ *b* (mod *n*) is *x* ≡ *a ^{ϕ}*

^{(n)-1}

*b*(mod

*n*).

**2** If gcd (*a*, *n*) = 1, then *a ^{mϕ}*

^{(n)}≡ 1 (mod

*n*) for all values of

*m*.

**3** If gcd (*m*, *n*) = gcd (*a, mn*) = 1, then *a ^{ϕ}*

^{(m)ϕ(n)}≡ 1 (mod

*mn*).

**4** If *p* is a prime, *ϕ*(*p ^{n}*) =

*p*−

^{n}*p*

^{n}^{ }

^{−}

^{ 1}=

*p*

^{n}^{ }

^{−}

^{ 1}(

*p*− 1). (HINT: For any integer

*a, a*and

*p*have a common divisor ≠ ±1 iff

^{n}*a*is a multiple of

*p*. There are exactly

*p*

^{n}^{ }

^{−}

^{ 1}multiples of

*p*between 1 and

*p*.)

^{n}**5** For every *a* 0 (mod *p*), *a ^{p}^{n}*

^{(p }

^{−}

^{ 1)}), where

*p*is a prime.

**6** Under the conditions of part 3, if *t* is a common multiple of *ϕ* (*m*) and *ϕ* (*n*), then *a ^{t}* ≡ 1 (mod

*mn*). Generalize to three integers

*l*,

*m*, and

*n*.

**7** Use parts 4 and 6 to explain why the following are true:

(*a*) *a*^{12} ≡ 1 (mod 180) for every *a* such that gcd(*a*, 180) = 1.

(*b*) *a*^{42} ≡ 1 (mod 1764) if gcd (*a*, 1764) = 1. (REMARK: 1764 = 4 × 9 × 49.)

(*c*) *a*^{60} ≡ 1 (mod 1800) if gcd (*a*, 1800) = 1.

**# 8** If gcd (

*m, n*) = l, prove that

*n*

^{ϕ}^{(m)}+

*m*

^{ϕ}^{(n)}≡ 1 (mod

*mn*).

**9** If *l*, *m*, *n* are relatively prime in pairs, prove that (*mn*)^{ϕ}^{(l)} + (*ln*)^{ϕ}^{(m)} + (*lm*)^{ϕ}^{(n)} ≡ 1 (mod *lmn*).

**G. Wilson’s Theorem, and Some Consequences**

In any integral domain, if *x*^{2} = 1, then *x*^{2} − 1 = (*x* + 1)(*x* − 1) = 0; hence *x* = ±1. Thus, an element *x* ≠ ±1 cannot be its own multiplicative inverse. As a consequence, in * _{p}* the integers may be arranged in pairs, each one being paired off with its multiplicative inverse.

Prove the following:

**1** In .

**2** (*p* − 2)! ≡ 1 (mod *p*) for any prime number *p*.

**3** (*p* − 1)! + 1 ≡ 0 (mod *p*) for any prime number *p* This is known as *Wilson’s theorem*.

**4** For any composite number *n* ≠ 4, (*n* − 1)! ≡ 0 (mod *n*). [HINT: If *p* is any prime factor of *n*, then *p* is a factor of (*n* − 1)! Why?]

Before going on to the remaining exercises, we make the following observations: Let *p* > 2 be a prime. Then

Consequently,

REASON: *p* − 1 ≡ −1 (mod *p*), *p* − 2 ≡ −2 (mod *p*),· · ·, (*p* + 1)/2 ≡ −(*p* − 1)/2 (mod *p*).

With this result, prove the following:

**5** [(*p* − l)/2]!^{2} ≡ (-1)^{(p + 1)/2} (mod *p*), for any prime *p* > 2. (HINT: Use Wilson’s theorem.)

**6** If *p* ≡ 1 (mod 4), then (*p* + 1)/2 is odd. (Why?) Conclude that

**7** If *p* ≡ 3 (mod 4), then (*p* + 1)/2 is even. (Why?) Conclude that

**8** When *p* > 2 is a prime, the congruence *x*^{2} + 1 ≡ 0 (mod *p*) has a solution if *p* ≡ 1 (mod 4).

**9** For any prime *p* > 2, *x*^{2} ≡ −1 (mod *p*) has a solution iff *p* 3 (mod 4). (HINT: Use part 8 and __Exercise E3__.)

**H. Quadratic Residues**

An integer *a* is called a *quadratic residue* modulo *m* if there is an integer *x* such that *x*^{2} ≡ *a* (mod *m*). This is the same as saying that *ā* is a square in * _{m}*. If

*a*is not a quadratic residue modulo

*m*, then

*a*is called a

*quadratic nonresidue*modulo

*m*. Quadratic residues are important for solving quadratic congruences, for studying sums of squares, etc. Here, we will examine quadratic residues modulo an arbitrary prime

*p*> 2.

Let *h* : be defined by .

**1** Prove *h* is a homomorphism. Its kernel is .

**# 2** The range of

*h*has (

*p*− 1)/2 elements. Prove: If ran

*h*=

*R, R*is a subgroup of having two cosets. One contains all the residues, the other all the nonresidues.

The *Legendre symbol* is defined as follows:

**3** Referring to part 2, let the two cosets of *R* be called 1 and -1. Then . Explain why

for every integer *α* which is not a multiple of *p*.

**# 4** Evaluate .

**5** Prove: if *a* ≡ *b* (mod *p*), then . In particular,

**6** Prove:

**7** (HINT: Use __Exercises G6__ and 7.)

The most important rule for computing

is the *law of quadratic reciprocity*, which asserts that for distinct primes *p*, *q* > 2,

(The proof may be found in any textbook on number theory, for example, *Fundamentals of Number Theory* by W. J. LeVeque.)

**8** Use parts 5 to 7 and the law of quadratic reciprocity to find:

Is 14 a quadratic residue, modulo 59?

**9** Which of the following congruences is solvable?

(*a*) *x*^{2} = 30 (mod 101)

(*b*) *x*^{2} ≡ 6 (mod 103)

(*c*) 2*x*^{2} ≡ 70 (mod 106)

NOTE: *x*^{2} ≡ *a* (mod *p*) is solvable iff *a* is a quadratic residue modulo *p* iff

**I. Primitive Roots**

Recall that *V _{n}* is the multiplicative group of all the invertible elements in

*. If*

_{n}*V*happens to be cyclic, say

_{n}*V*= ⟨

_{n}*m*⟩, then any integer

*a*≡

*m*(mod

*n*) is called a

*primitive root*of

*n*.

**1** Prove that *a* is a primitive root of *n* iff the order of *ā* in *V _{n}* is

*ϕ*(

*n*).

**2** Prove that every prime number *p* has a primitive root. (HINT: For every prime is a cyclic group. The simple proof of this fact is given as __Theorem 1__ in __Chapter 33__.)

**3** Find primitive roots of the following integers (if there are none, say so): 6, 10, 12, 14, 15.

**4** Suppose *a* is a primitive root of *m*. Prove: If *b* is any integer which is relatively prime to *m*, then *b* ≡ *a ^{k}* (mod

*m*) for some

*k*1.

**5** Suppose *m* has a primitive root, and let *n* be relatively prime to *ϕ* (*m*). (Suppose *n* > 0.) Prove that if *a* is relatively prime to *m*, then *x ^{n}* ≡

*a*(mod

*m*) has a solution.

**6** Let *p* > 2 be a prime. Prove that every primitive root of *p* is a quadratic nonresidue, modulo *p*. (HINT: Suppose a primitive root α is a residue; then every power of *a* is a residue.)

**7** A prime *p* of the form *p* = 2* ^{m}* + 1 is called a

*Fermat prime*. Let

*p*be a Fermât prime. Prove that every quadratic nonresidue mod

*p*is a primitive root of

*p*. (HINT: How many primitive roots are there? How many residues? Compare.)