Math 463 Final
Prof. Je
y Rosen
Spring 2021
Instructions: Answer all 8 questions and submit your answers in a single
PDF. This is an open book/open notes exam, but absolutely no internet sources!
You can assume the results for the Legendre symbols
(
a
p
)
for a = −1, 2, 3, 5, if
necessary.
1. (12 pts) Determine the primes p > 5 for which −5 is a quadratic residue
modp (see exercise XXXXXXXXXX)
2. (12 pts) Suppose p is an odd prime and assume that q = 4p + 1 is also
prime. Prove that 2 must be a primitive root modq as follows:
(a) What must the order of 2 be modq to be a primitive root?
(b) Use Fermat’s Theorem to explain why the possible orders of 2modq
must be one of 2, 4, p, 2p, 4p
(c) Use Euler’s Criterion to rule out 2, p, 2p
(d) Also rule out 4
(e) Make the conclusion
3. (12 pts) Consider the equation x4 ≡ 16mod17 Explain why this equation
must have four distinct solutions without using an explicit primitive root.
Use g for the primitive root (HINT: what is 16 congruent to mod17?)
4. (14 pts) Show all work in solving the following. No credit for guessing!
(a) Consider 4x2−12x+7 ≡ 0mod31. Does this equation have solutions
mod31? If so, explain and find them. If not, why?
(b) Consider 3x2 − 19y = 1. Does this equation have integer solutions?
If so, explain and find them. If not, why?
5. (10 pts) Let n > 1. Prove the sum of the positive integers less than n and
elatively prime to n equals 12nφ(n) as follows:
(a) Let a1 , a2, . . . , aφ(n) be the desired integers and set s = a1 + a2 +
· · ·+ aφ(n)
(b) Explain why gcd(n − ai , ai) = 1 for i = 1, 2, . . . , φ(n) and hence{
a1, a2, . . . , aφ(n)
}
=
{
n− a1, n− a2, . . . , n− aφ(n)
}
(c) Now write s in another way and equate
6. (12 pts) Answer parts (a) and (b)
(a) Explain why 26 must have a primitive root (just quote a theorem)
and find the smallest primitive root mod26. Then express all the
primitive roots mod26 in terms of this one.
1
(b) Prove 20 is a primitive root of 73 by considering ord732 and ord7310
7. (10 pts) Answer parts (a) and (b)
(a) Suppose p is an odd prime such that gcd(ab, p) = 1 (for natural
numbers a and b). Explain why at least one of the numbers a, b, o
ab must be a quadratic residue modp
(b) Prove: given a prime number p, there must exist a natural number n
such that p divides the product (n2 − 2)(n2 − 3)(n2 − 6) (first show
this is true if p = 2 or p = 3, then assume p > 3 and use part (a))
8. (18 pts) Evaluate the following Legendre or Jacobi symbols
(a)
(−125
113
)
(b)
(
111
301
)
(c)
(
210
229
)
2