MATH 115: ELEMENTARY NUMBER THEORY HOMEWORK #6 WORKSHEET

JOHN VOIGHT

First, break up into the assigned groups, introduce yourselves, and then please write the names of all of your group members on the board. Then write up the assigned problem and a nice solution on the board. At the end of class, any member of your group may be called upon to explain your solution, so make sure everyone understands! (If your group finishes early, start thinking about one of the other problems.)

(1) Show that if a has order h modulo n and b has order k modulo n, and gcd(h, k) = 1, then ab has order hk modulo n.

(2) Let r be a primitive root of the odd prime p. Show that −r is a primitive root, or not, according as p ≡ 1 (mod 4) or p ≡ 3 (mod 4).

(3) Suppose that gcd(10a, b) = 1, and that k is the order of 10 modulo b. Show that the decimal expansion of the rational number a/b is periodic with least period k.

(4) Show that if r and s are primitive roots modulo a positive integer n, then rs is not a primitive root modulo n.

(5) Let r_{1}, r_{2}, …, r_{ϕ(n)} be a reduced residue system modulo n. Show that the numbers r_{1}^{k}, r_{2}^{k}, …, r_{ϕ(n)}^{k} form a reduced residue system modulo n if and only if gcd(k, ϕ(n)) = 1.

Date: July 27, 2004.