﻿ ﻿ELEMENTS OF NUMBER THEORY (OPTIONAL) - A Book of Abstract Algebra

## 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 aand b by n, then

a = nq1 + r and b = nq2 + r

where the remainder r is the same in both equations.

Subtracting these two equations, we see that

ab = (nq1 + r) − (nq2 + r) = n(q1q2)

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

ab (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,

ab (mod n) implies a + cb + c (mod n)

and

ab (mod n) implies acbc (mod n)

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

Recall that

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

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

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 xm = 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,

ap 1 ≡ 1 (mod p) for every a 0(mod p)

Corollary apa (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 Vn denote the set of all the invertible elements in n. Clearly, Vn is a group with respect to multiplication. (Reason: The product of two invertible elements is invertible, and, if 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 Vn is ϕ(n).

Thus, Vn 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 4x + 2y = 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 = cax iff axc (mod b)

Thus, any solution of axc (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 axb (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, 4x5 (mod 2) cannot have a solution, because 4x 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 axb (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 bJ 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 axb (mod n). By a solution modulo n of this congruence, we mean a congruence

xc (mod n)

such that any integer x satisfies xc (mod n) iff it satisfies axb (mod n). [That is, the solutions of axb (mod n) are all the integers congruent to c, modulo n.] Does every congruence axb (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 axb (mod n) has a solution modulo n.

PROOF: Indeed, by (3), axb (mod n) is equivalent to the equality in n. But by Condition (4), has a multiplicative inverse in n; hence from we get . Setting , we get in n, that is, xc (mod n). ■

Thus, if a and n are relatively prime, axb (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 axb (mod n) has a solution, then it has a solution modulo m, where This means that the solution of axb (mod n) is of the form xc (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 axb (mod n). ■

As an example, let us solve 6x ≡ 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 6x ≡ 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,

a1xb1 (mod n1), a2xb2 (mod n2),…, akx = bk (mod nk)

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

xc1 (mod m1), xc2(mod m2), …, xck (mod mk)

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 xa (mod n) and xb (mod m). There is an integer x satisfying both simultaneously iff ab (mod d), where d = gcd(m, n).

PROOF: If x is a simultaneous solution, then n | (xa) and m | (xb). Thus,

xa = nq1 and xb = mq2

Subtracting the first equation from the second gives

ab = mq2nq1

But d|m and d|n, so d|(ab); thus, ab (mod d).

Conversely, if ab (mod d), then d | (ab), so ab = dq. By Theorem 3 of Chapter 22, d = rn + tm for some integers r and t. Thus, ab = rqn + tqm. From this equation, we get

arqn = b + tqm

Set x = arqn = b + tqm; then xa = −rqn and xb = tqm; hence n|(xa) and m|(xb), so

xa (mod n) and xb (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 xa (mod n) and xb (mod m) has a simultaneous solution, then it has a simultaneous solution of the form

xc (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|(xc) and n|(xc) iff t|(xc)

hence

xc (mod m) and xc (mod n) iff xc (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 ca (mod n) and cb (mod m). Any other integer x is a simultaneous solution iff xc (mod n) and xc (mod m). But by Condition (7), this is true iff xc (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 xa (mod n) and xb (mod m) always has a solution. This solution is of the form xc (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 m1,m2,…,mk be pairwise relatively prime. Then the system of simultaneous linear congruences

xc1 (mod m1), xc2 (mod m2), …, x = ck (mod mk)

always has a solution, which is of the form xc (mod m1m2mk).

Use Theorem 4 to solve xc1 (mod m1) and xc2 (mod m2) simultaneously. The solution is of the form xd (mod m1m2). Solve the latter simultaneously with xc3 (mod m3), to get a solution mod m1m2m3. 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) 60x ≡ 12 (mod 24)

(b) 42x ≡ 24 (mod 30)

(c) 49x ≡ 30 (mod 25)

(d) 39x ≡ 14 (mod 52)

(e) 147x ≡ 47 (mod 98)

(f) 39x ≡ 26 (mod 52)

2 Solve the following linear congruences:

(a) 12x ≡ 7 (mod 25)

(b) 35x ≡ 8 (mod 12)

(c) 15x ≡ 9 (mod 6)

(d) 42x ≡ 12 (mod 30)

(e) 147x ≡ 49 (mod 98)

(f)39x ≡ 26 (mod 52)

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

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

(a) 6x2 ≡ 9 (mod 15)

(b) 60x2 ≡ 18 (mod 24)

(c) 30x2 ≡ 18 (mod 24)

(d) 4(x + 1)2 ≡ 14 (mod 10)

(e) 4x2 − 2x + 2 ≡ 0 (mod 6)

# (f) 3x2 − 6x + 6 ≡ 0 (mod 15)

5 Solve the following congruences:

(a) x4 ≡ 4 (mod 6)

(b) 2(x − 1)4 ≡ 0 (mod 8)

(c) x3 + 3x2 + 3x + 1 = 0 (mod 8)

(d) x4 + 2x2 + 1 ≡ 4 (mod 5)

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

(a) 14x + 15y = 11

(b) 4x + 5y = 1

(c) 21x + 10y = 9

# (d) 30x2 + 24y = 18

B. Solving Sets of Congruences

Example Solve the pair of simultaneous congruences x5 (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 ≡ 6q + 5. Introducing this into x ≡ 7 (mod 10) yields 6q + 5 ≡ 7 (mod 10). Thus, successively, 6q ≡ 2 (mod 10), 3q ≡ 1 (mod 5), q ≡ 2 (mod 5), q = 5r + 2. Introducing this into x = 6q + 5 gives x = 6(5r + 2) + 5 = 30r + 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) 10x ≡ 2 (mod 12); 6x ≡ 14 (mod 20)

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

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

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

x = c1 (mod m1), xc2(mod m2) …, xck (mod mk)

There is an x satisfying all k congruences simultaneously if for all i, j ∈ {1, …, k}, cicj (mod dij), where dij = gcd(mi, mj). Moreover, the simultaneous solution is of the form xc (mod t), where t = lcm (m1, m2, …, mk).

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); 10x ≡ 4 (mod 12); 3x ≡ 8 (mod 10)

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

5 Solve the following systems of simultaneous Diophantine equations:

# (a) 4x + 6y = 2; 9x + 12y = 3

(b) 3x + 4y = 2; 5x + 6y = 2; 3x + 10y = 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 ab (mod n) and bc (mod n), then ac (mod n).

2 If ab (mod n), then a + cb + c (mod n).

3 If ab (mod n), then acbc (mod n).

4 ab (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 a2b2 (mod p), where p is a prime, then a ≡ ±b (mod p).

7 If ab (mod m), then a + kmb (mod m), for any integer k. In particular, a + kma (mod m).

8 If acbc (mod n) and gcd(c, n) ≡ 1, then ab (mod n).

9 If ab (mod n), then ab (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 acbc (mod n), and gcd(c, n) ≡ d, then ab (mod n/d).

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

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

4 If ab (mod n), then ambm (mod n) for every positive integer m.

5 If ab (mod m) and ab (mod n) where gcd(m, n) = 1, then ab (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 a2 ≡ 1 (mod 2), then a2 ≡ 1 (mod 4).

8 If ab (mod n), then a2 + b2 ≡ 2ab (mod n2), 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 x2 + 1 ≡ 0 (mod p). [HINT: Raise both sides of x2 ≡ −1 (mod p) to the power (p − 1)/2, and use Fermat’s little theorem.]

# 4 Let p and q be distinct primes. Then pq 1 + qp 1 ≡ 1(mod pq).

5 Let p be a prime.

(a) If, (p − 1) | m, then am ≡ 1 (mod p) provided that p a.

(b) If, (p − 1)| m, then am + 1a(mod pq) for all integers a.

# 6 Let p and q be distinct primes.

(a) If (p − 1) | m and (q − 1) | m, then am ≡ 1 (mod pq) for any a such that p a and q a.

(b) If (p − 1) | m and (q − 1) | m, then am + 1a (mod pq) for integers a.

7 Generalize the result of part 6 to n distinct primes, p1…, pn. (State your result, but do not prove it.)

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

# (a) a19a (mod 133).

(b) a10 ≡ 1 (mod 66), provided a is not a multiple of 2, 3, or 11.

(c) a13a (mod 105).

(d) a49a (mod 1547). (HINT: 1547 = 7 × 13 × 17.)

9 Find the following integers x:

(a) x ≡ 838 (mod 210)

(b) x ≡ 757 (mod 133)

(c) x ≡ 573 (mod 66)

F. Consequences of Euler’s Theorem

Prove parts 1-6:

1 If gcd (a, n) = 1, the solution modulo n of axb (mod n) is xaϕ(n)-1b (mod n).

2 If gcd (a, n) = 1, then a(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, ϕ(pn) = pnpn 1 = pn 1(p − 1). (HINT: For any integer a, a and pn have a common divisor ≠ ±1 iff a is a multiple of p. There are exactly pn 1 multiples of p between 1 and pn.)

5 For every a 0 (mod p), apn(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 at ≡ 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) a12 ≡ 1 (mod 180) for every a such that gcd(a, 180) = 1.

(b) a42 ≡ 1 (mod 1764) if gcd (a, 1764) = 1. (REMARK: 1764 = 4 × 9 × 49.)

(c) a60 ≡ 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 x2 = 1, then x2 − 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 x2 + 1 ≡ 0 (mod p) has a solution if p ≡ 1 (mod 4).

9 For any prime p > 2, x2 ≡ −1 (mod p) has a solution iff p 3 (mod 4). (HINT: Use part 8 and Exercise E3.)

An integer a is called a quadratic residue modulo m if there is an integer x such that x2a (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 nonresiduemodulo 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 ab (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) x2 = 30 (mod 101)

(b) x2 ≡ 6 (mod 103)

(c) 2x2 ≡ 70 (mod 106)

NOTE: x2a (mod p) is solvable iff a is a quadratic residue modulo p iff I. Primitive Roots

Recall that Vn is the multiplicative group of all the invertible elements in n. If Vn happens to be cyclic, say Vn = ⟨m⟩, then any integer am (mod n) is called a primitive root of n.

1 Prove that a is a primitive root of n iff the order of ā in Vn 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 bak (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 xna (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 = 2m + 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.)

﻿