Assignment # 5 – Number Theory

(1) Determine the order of the following elements:
(a) 5 (mod 31)
(b) 3 (mod 76)
(2) If p is a prime and g is a primitive root modulo p, is -g also a primitive root? Prove
it, or nd a counterexample.
(3) If p is a prime such that p = 1 (mod 4) and g is a primitive root modulo p, is -g
also a primitive root? Prove it, or find a counterexample.
(4) Solve 2^n + 3^n = 0 (mod 17).
(5) Suppose there is an integer a such that a^phi(n)/q not cong. 1 (mod n) for all prime divisors q
of phi(n). Show that a is a primitive root modulo n.
(6) Let p be a prime and suppose p 6 not divides a. Show that the equation x^2 = a (mod p) has a
solution if and only if a^(p-1)/2 = 1 (mod p).
(7) Bonus: Suppose p and q = 2p + 1 are both primes. If 2^p = -1 (mod q), show that 2
is a primitive root modulo q.

assignment 5 solution