Math 115B: Homework Assignment 3
Due Friday, 5/29
Assume a, b,...are integers, r, s, t ≥ 1, m > 2, p =prime> 2.
1. Write c = ϕ(m) and let q1, q2,...,qk be all the distinct prime factors of c. Suppose that
(a,m) = 1 and
ac/qj 6≡ 1(mod m), 1 ≤ j ≤ k.
Prove that a is a primitive root (mod m).
2. Prove that 2 is a primitive root (mod 11).
3. Find the indices of 3, 4 and 5(mod 11) to the base 2.
4. Supoose p is of the form p = 2n + 1, n > 1. Prove that 3 is a primitive root (mod p).
5. It is known that 3 is a primitive root (mod 17) by Problem 4. Find the indices of 3, 4
and 5(mod 17) to the base 3.
6. Let q be a prime> 2. Prove that for any a > 1, the greatest common divisor
(aq−1 + aq−2 + · · ·+ a + 1, a− 1)
is either 1 or q.
7. Let q be as in Problem 6. Prove that there are infinitely many primes p ≡ 1(mod 2q).
8. Suppose n ≥ 1 and
22
n ≡ −1(mod p).
Prove that
p ≡ 1(mod 2n+1).
9. Suppose n ≥ 1 and, for any p, write
S =
p−1∑
j=1
jn.
Prove that
S ≡ −1(mod p) if (p− 1)|n,
and
S ≡ 0(mod p) otherwise.
1