FINAL EXAM

MATH 115: NUMBER THEORY

Answer each question completely, and give sufficient justification and proof. Write neatly and in complete sentences!

Name Student ID

Problem 1  /10
Problem 2  /10
Problem 3  /15
Problem 4  /15
Problem 5  /15
Problem 6  /10
Problem 7  /15
Problem 8 (Bonus)  /10
Total Score  /90

Date: August 12, 2004.

2 115 FINAL

Problem 1. Let p be an odd prime and k ∈ ℤ_{>0}. Show that the congruence

x^{2} ≡ 1 (mod p^{k})

has only the solutions x ≡ ±1 (mod p^{k}).

115 FINAL 3

Problem 2. For which primes p does the congruence

x^{2} + x + 1 ≡ 0 (mod p)

have a solution?

4 115 FINAL

Problem 3. The integer n = pq = 51809 (with p and q prime) is used in an RSA cryptosystem. Through espionage, you find out that

σ(n) = 52416.

Find p and q.

115 FINAL 5

Problem 4.

(a) Show that the arithmetic function f(n) = (−1)^{n−1} is multiplicative.

(b) Let g be the arithmetic function

g(n) = ∑_{d|n} μ(d)f(d).

Prove that g(n) = 0 if n is not a power of 2.

Problem 5. Let a be an odd prime, b ∈ ℤ_{>0}, and suppose that p = a^{2} + 5b^{2} is prime. Prove that a is a quadratic residue modulo p if and only if p ≡ 1 (mod 5).

Problem 6. Let n ∈ ℤ_{>1} be an integer with prime factorization

n = p_{1}^{e_{1}}p_{2}^{e_{2}} … p_{r}^{e_{r}},

with p_{i} prime and e_{i} ∈ ℤ_{>0}. Let

m = lcm(ϕ(p_{1}^{e_{1}}), ϕ(p_{2}^{e_{2}}), …, ϕ(p_{r}^{e_{r}})).

(a) Show that for every a ∈ ℤ such that gcd(a, n) = 1, the order of a modulo n divides m.

(b) Is it true that for every n ∈ ℤ_{>0}, there exists an element of order m modulo n?

8 115 FINAL

Problem 7. Let p, q be odd primes for which p = 2q + 1. Let a ∈ ℤ be an integer satisfying

a ≢ −1, 0, 1 (mod p).

Show that −a^{2} mod p is a primitive root modulo p.

115 FINAL 9

Problem 8 (Bonus). Let n ∈ ℤ be an integer with n > 6. Show that ϕ(n) > \sqrt{n}.