FINAL EXAM REVIEW MATH 115: NUMBER THEORY

Problem 1.

(a) Show that if p is an odd prime of the form p = a^{2} + b^{2}, with a, b ∈ ℤ, then p ≡ 1 (mod 4).

(b) Let p be a prime of the form p = a^{2} + b^{2} with a, b ∈ ℤ and a an odd prime. Prove that

(\frac{a}{p}) = 1.

Problem 2. Evaluate the Legendre symbol

(\frac{103}{229}) .

2 115 FINAL REVIEW

Problem 3. Let p ∈ ℤ_{>0} be an odd prime and n = 3^{p} + 1. Let q be an odd prime divisor of n.

(a) What is the order of 3 modulo n?

(b) Show that q is of the form q = 2kp+1 for some integer k ∈ ℤ_{>0}.

115 FINAL REVIEW 3

Problem 4. Find all positive integers n such that ϕ(n) | 3n.

4 115 FINAL REVIEW

Problem 5.

(a) Use the fact that 3 is a primitive root modulo the prime 79 to

find all x ∈ ℤ/79ℤ satisfying x^{40} ≡ 2 (mod 79).

(b) Is 2 a primitive root modulo 79?

115 FINAL REVIEW 5

Problem 6. Let N be a perfect number. Show that

∏_{\begin{matrix}p|N \\ p prime \end{matrix}}(1 − \frac{1}{p}) < \frac{1}{2}.

Problem 7. A bank encodes a 3 digit PIN number using RSA encryption with key e = 835 and n = pq = 1411 = 17 · 83. If Alice’s PIN number is encoded as the ciphertext 002, what is her three-digit PIN number?

115 FINAL REVIEW 7

Problem 8. Let p be the prime

p = 131 = 2 · 5 · 13 + 1.

Use the fact that 53 has order 5 modulo p and that 39 has order 13 to find a primitive root r modulo p.

Problem 9. Let p be an odd prime with primitive root r.

(a) Let a be an integer with gcd(a, p) = 1. Show that a is a quadratic residue modulo p if and only if log_{r} a is even.

(b) Show that if a is a quadratic residue modulo p, then a is not a primitive root modulo p.

(c) Amongst the quadratic nonresidues modulo p, how many are primitive roots?

115 FINAL REVIEW 9

Problem 10. Let σ_{k} be the arithmetic function

σ_{k}(n) = ∑_{d|n} d^{k}.

(a) Simplify

∑_{d|n} μ(d)σ_{k}(n/d).

(b) Prove that the function

S_{k}(n) = ∑_{d|n} μ(d)σ_{k}(d)

is multiplicative.