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 = nq₁ + r and b = nq₂ + r

where the remainder r is the same in both equations.

Subtracting these two equations, we see that

a − b = (nq₁ + r) − (nq₂ + r) = n(q₁ − q₂)

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⟩ = {…, −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 ₆,

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 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_n denote the set of all the invertible elements in _n. Clearly, V_n 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 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 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 = 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, 4x ≡ 5 (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 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 _n; hence from we get . Setting , we get in _n, that is, 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 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 ₅, 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,

a₁x ≡ b₁ (mod n₁), a₂x ≡ b₂ (mod n₂),…, a_kx = b_k (mod 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₁ (mod m₁), x ≡ c₂(mod m₂), …, 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₁ and x − b = mq₂

Subtracting the first equation from the second gives

a − b = mq₂ − nq₁

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₁,m₂,…,m_k be pairwise relatively prime. Then the system of simultaneous linear congruences

x ≡ c₁ (mod m₁), x ≡ c₂ (mod m₂), …, x = c_k (mod m_k)

always has a solution, which is of the form x ≡ c (mod m₁m₂ … m_k).

Use Theorem 4 to solve x ≡ c₁ (mod m₁) and x ≡ c₂ (mod m₂) simultaneously. The solution is of the form x ≡ d (mod m₁m₂). Solve the latter simultaneously with x ≡ c₃ (mod m₃), to get a solution mod m₁m₂m₃. 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 2x² ≡ 8 (mod 10) has the same solutions as x² ≡ 4 (mod 5).(b) Explain why x ≡ 2 (mod 5) and x ≡ 3 (mod 5) are all the solutions4 of 2x² ≡ 8 (mod 10).

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

(a) 6x² ≡ 9 (mod 15)

(b) 60x² ≡ 18 (mod 24)

(c) 30x² ≡ 18 (mod 24)

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

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

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

5 Solve the following congruences:

(a) x⁴ ≡ 4 (mod 6)

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

(c) x³ + 3x² + 3x + 1 = 0 (mod 8)

(d) x⁴ + 2x² + 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) 30x² + 24y = 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 ≡ 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 = c₁ (mod m₁), x ≡ c₂(mod m₂) …, 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_j (mod d_ij), where d_ij = gcd(m_i, m_j). Moreover, the simultaneous solution is of the form x ≡ c (mod t), where t = lcm (m₁, m₂, …, 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); 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 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² ≡ b² (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^m (mod 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² ≡ 1 (mod 2), then a² ≡ 1 (mod 4).

8 If a ≡ b (mod n), then a² + b² ≡ 2ab (mod n²), 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² + 1 ≡ 0 (mod p). [H_INT: Raise both sides of x² ≡ −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₁…, p_n. (State your result, but do not prove it.)

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

# (a) a¹⁹ ≡ a (mod 133).

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

(c) a¹³ ≡ a (mod 105).

(d) a⁴⁹ ≡ a (mod 1547). (HINT: 1547 = 7 × 13 × 17.)

9 Find the following integers x:

(a) x ≡ 8³⁸ (mod 210)

(b) x ≡ 7⁵⁷ (mod 133)

(c) x ≡ 5⁷³ (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)-1b (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ⁿ) = pⁿ − p^{n − 1} = p^{n − 1}(p − 1). (HINT: For any integer a, a and pⁿ have a common divisor ≠ ±1 iff a is a multiple of p. There are exactly p^{n − 1} multiples of p between 1 and pⁿ.)

5 For every a 0 (mod p), a^{pn(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¹² ≡ 1 (mod 180) for every a such that gcd(a, 180) = 1.

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

(c) a⁶⁰ ≡ 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² = 1, then x² − 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]!² ≡ (-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² + 1 ≡ 0 (mod p) has a solution if p ≡ 1 (mod 4).

9 For any prime p > 2, x² ≡ −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² ≡ 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 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 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² = 30 (mod 101)

(b) x² ≡ 6 (mod 103)

(c) 2x² ≡ 70 (mod 106)

NOTE: x² ≡ 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 _n. If V_n happens to be cyclic, say 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ⁿ ≡ 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.)