3.3.5 Quadratic Residue
3.3.5 Quadratic Residue
3.3.5 Quadratic Residue
mod p
has a solution modulo every prime p, even though the equation 6x2 + 5x + 1 = 0 has no
solution in the integers.
Solution:
First observe that, for p = 2, the congruence 6x2 + 5x + 1 0 (mod 2) has a solution
x 1 (mod 2). Also, when p = 3, the congruence 6x2 + 5x + 1 0 (mod 3) has a solution
x 1 (mod 3).
Suppose therefore that p is a prime with p > 3. Then the congruence 6x2 + 5x + 1 0
(mod p) may be expressed as y 2 1 (mod p), where y 12x + 5 (mod p). The solution
y 1 (mod p) leads to the linear congruence 12x 4 (mod p). Since (12, p) = 1, this
congruence has a solution. It therefore follows that the congruence 6x2 +5x +1 0 (mod p)
also has a solution.
(2) Show that 3 is a quadratic residue modulo 23, but is a non-residue modulo 31.
Solution:
In the case of p = 23, Eulers criterion yields
3(231)/2 = 311
1
(mod 23),
(mod 31),
(mod p)
(1)(p1)/2 (a)(p1)/2
(1)(p1)/2
(mod p)
(mod p).
(p1)/2
(mod p)
a
(mod p)
1 a (mod p).
Hence x a(p+1)/4 (mod p) are the solutions of the congruence x2 a (mod p).
(4) If p = 2k + 1 is a prime, show that every quadratic non-residue modulo p is a primitive
root modulo p.
Solution:
Let a be a quadratic residue modulo the prime p, where p = 2k + 1 for some prime p > 1.
Then, by Eulers criterion,
a2
k1
= a(p1)/2
1
(mod p),
a2 1
(mod p).
This means that the order of a modulo p is a divisor of 2k . If the order of a modulo p were
k
2j , with j < k, the repeated squaring would lead to a2 1 (mod p), which would in turn
imply that 1 1 (mod p). This is imposible, and so it follows that the order of 2 modulo
p is 2k = p 1 = (p), i.e. 2 is a primitive root modulo p.
(5) Find the value of the following Legendre symbols:
(a) (19/23)
(b) (23/59)
(c) (72/131)
Solution:
(a) (19/23) = (4/23) = (4/23)(1/23) = 1 (1) = 1.
(b) (23/59) = (36/59) = 1.
(c) We have
(72/131) = (1/131)(36/131)(2/131)
(1) 1 265
1
(mod 131),
(mod 131)
and so (72/131) = 1.
(6) Use Gausss Lemma to compute each of the following Legendre symbols (i.e., in terms
of the notation that we used in class, find the integer n in Gausss Lemma for which (a/p) =
(1)n ).
(a) (8/11)
(b) (7/13)
(c) (5/19)
Solution:
(a) Using the notation established in class, S = {8, 16, 24, 32, 40}, or, modulo 11, S =
{8, 5, 2, 10, 7}. Hence n = 3, and so (8/11) = (1)3 = 1.
(b) Here S = {7, 14, 21, 28, 35, 42}, or, modulo 13, S = {7, 1, 8, 2, 9, 3}. Thus n = 3, and
(7/13) = (1)3 = 1.
(c) Here S = {5, 10, 15, 20, 25, 30, 35, 40, 45}, or, modulo 19, S = {5, 10, 15, 1, 6, 11, 16, 2, 7}.
Thus n = 4, and so (5/19) = (1)4 .
(7) (a) Let p be an odd prime, and suppose that a is an integer with (a, p) = 1. Show
that the Diophantine equation
x2 + py + a = 0
has an integral solution if and only if (a/p) = 1.
(b) Determine whether or not the Diophantine equation
x2 + 7y 2 = 0
has a solution in the integers.
Solution:
(a) The diophantine equation x2 + py + a = 0 is equivalent to the quadratic congruence
x2 a (mod p). This quadratic congruence has a solution if and only if (a/p) = 1.
(b) The equation x2 + 7y 2 = 0 will have solution if (2/7) = 1. This condition certainly
holds, and so the equation does have a solution.
(8) Prove that 2 is not a primitive root modulo any prime of the form p = 3 2n + 1, except
when p = 13.
Solution:
Consider primes of the form p = 3 2n + 1. When n = 1, we have p = 7; since (2/7) = 1, 2
is not a primitive root modulo 7. When n = 2, p = 13, and 2 is a primitive root modulo 13.
Assume that n 3. Then p = 8 3 2n1 + 1, and so p 1 (mod 8). This implies that
(2/p) = 1, i.e. 2 is a quadratic residue modulo p. Hence 2 is not a primitive root modulo p.
(9) For a prime p 7 (mod 8), show that p | (2(p1)/2 1).
Solution:
Since p 7 (mod 8), we have that (2/p) = 1. Hence (via Eulers criterion), 2(p1)/2 1
(mod p), and so p | (2(p1)/2 1).
(10) (a) Suppose that p is an odd prime, and that a and b are integers such that (ab, p) = 1.
Prove that at least one of a, b or ab is a quadratic residue modulo p.