Problems for Number Theory October 19, 1998

Definition Let n > 1 and gcd(a, n) = 1. The order of a modulo n is the smallest positive integer k such that a^{k} ≡ 1 (mod n). For example, 3^{2} ≡ 9 (mod 11), 3^{3} ≡ 5 (mod 11), 3^{4} ≡ 4 (mod 11), 3^{5} ≡ 1 (mod 11), so the order of 3 modulo 11 is 5.

91. Prove that order modulo n is well-defined, i.e., for any pair of integers a, n, with gcd(a, n) = 1 there exists a smallest positive integer k such that a^{k} ≡ 1 (mod n).

92. Compute the orders modulo 13 of the integers 1–12, and the orders modulo 26 of the integers 1–25 (for which it exists).

93. Let the integer a have order k modulo n. Then a^{m} ≡ 1 (mod n) if and only if k|m. In fact, k|ϕ(n).

94. If a has order k modulo n, then a^{i} ≡ a^{j} (mod n) if and only if i ≡ j (mod k).

95. If a has order k modulo n, then the integers a, a^{2}, a^{3}, …, a^{k} are incongruent modulo n.

96. Suppose that a has order k modulo n, what is the order of a^{h}?

Definition If a has order ϕ(n) modulo n, then we say a is a primitive root of n.

97. Find primitive roots for n = 11, 15, 71, 191.

98. Prove that there always exists a primitive root for a prime modulus.

99. Suppose that a_{1}, a_{2}, … a_{ϕ(n)} are the positive integers less than n and relatively prime to it. If a is a primitive root of n, then a, a^{2} … a^{ϕ(n)} are congruent modulo n to a_{1}, a_{2}, … a_{ϕ(n)} in some order.

100. If n has a primitive root, then it has ϕ(ϕ(n)).

101. What can you say about ϕ(2^{n} − 1), n > 1?

102. The odd prime divisors of n^{2} + 1 are of the form 4k + 1.

103. OK, now prove that there are infinitely many primes of the form 4k + 1. (Hint: Use the above.)

104. Prove that 2^{k} never has a primitive root.

105. Suppose m > 2, n > 2 and gcd(m, n)=1, then the integer mn has no primitive roots. (These last two results allow one to completely characterize those composite numbers which have primitive roots.)

Quadratic Congruences–In light of the first problem below we will restrict our attention to congruences of the form x^{2} ≡ a (mod n). (To avoid trivialities, we will assume that a is not a multiple of p.)

107. Suppose p is an odd prime and gcd(a, p) = 1. Show that a solution to the quadratic congruence (2ax + b)^{2} ≡ (b^{2} − 4ac) (mod n) provides a solution to the congruence ax^{2} + bx + c ≡ 0 (mod n).

108. Solve 5x^{2} − 6x + 2 ≡ 0 (mod 13).

Definition Let p be an odd prime and gcd(a, p) = 1. If the congruence x^{2} ≡ a (mod p) has a solution, then we say that a is a quadratic residue of p. (Think, has a square root.) Otherwise, a is a quadratic nonresidue of p.

109. Which of the integers less than 13 are quadratic residues modulo 13?

110. (Euler’s Criterion) Let p be an odd prime and gcd(a, p) = 1. Then a is a quadratic residue (respectively, nonresidue) of p if and only if a^{(p−1)/2} ≡ 1 (mod p) (resp., a^{(p−1)/2} ≡ −1 (mod p).

111. If a is a quadratic residue of an odd prime p, then a is not a primitive root of p.

112. If a is a quadratic residue of an odd prime p, then p − a is a quadratic residue or nonresidue according as p ≡ 1 (mod 4) or p ≡ 3 (mod 4).

113. If p = 2^{k} + 1 is prime, then every quadratic nonresidue of p is a primitive root of p.

Definition Let p be an odd prime and gcd(a, p) = 1. The Legendre symbol (a/p) is the function that returns 1, if a is a quadratic residue of p, and -1, if a is a quadratic nonresidue of p.

114. Let p be an odd prime and a and b be relatively prime to p.

(a) If a ≡ b (mod n), then (a/p) = (b/p).

(b) (ab/p) = (a/p)(b/p).

(c) (ab^{2}/p) = (a/p).

(d) (1/p) = 1 and (−1/p) = (−1)^{(p−1)/2}.

115. If p is an odd prime, then

∑_{a=1}^{p−1}(a/p) = 0.

That is, there are (p − 1)/2 quadratic residues and quadratic nonresidues of p.

116. The quadratic residues of an odd prime p are congruent modulo p to the even powers of a primitive root r of p; the quadratic nonresidues are congruent to the odd powers of r.

117. (Gauss’ Lemma) Let p be an odd prime and gcd(a, p) = 1. If n denotes the number of

integers in the set

S = {a, 2a, 3a, …, (p − 1)/2 · a}

whose remainders upon division by p exceed p/2, then (a/p) = (−1)^{n}.

118. If p is an odd prime, then (2/p) is 1 if and only if p ≡ ±1 (mod 8).

119. If p ≡ 7 (mod 8), show that p|2^{(p−1)/2} − 1. Use this result to verify that 2^{n} − 1 is composite for n = 11, 23, 83, 131, 179, 181, 251.

120. Suppose that p and q are odd primes. Gather data and formulate a conjecture about the relationship between (p/q) and (q/p). Sums of squares (finally!).

121. If m and n are each the sum of two squares, then so is their product.

122. No prime of the form 4k + 3 is a sum of two squares.

123. Let p be a prime and gcd(a, p)=1. Then the congruence ax ≡ y (mod p) admits a solution x_{0}, y_{0} satisfying, 0 < |x_{0}| < \sqrt{p} and 0 < |y_{0}| < \sqrt{p}.

124. An odd prime is expressible as a sum of two squares if and only if it is of the form 4k +1. Moreover, any such representation is unique.

125. A number n is representable as the sum of two squares if and only if each of its prime factors of the form 4k + 3 occurs to an even power.