Problem 5. For a composite modulus n we say that g is a primitive root modulo n if the order of g modulo n is (n) (i.e. g k 1 (mod n) if and only if (n)|k). Let n, m N be co-prime. (1) Show that if g Z is a primitive root modulo mn then g is a primitive root modulo n (and modulo m). (2) Let h = lcm((n), (m)) and show that any a Z co-prime to nm satisfies that a h 1 (mod nm). (3) Let n = p1p2 be a product of odd primes. Can there be a primitive root modulo n?

Problem 5. For a composite modulus n we say that g is a primitive root modulo n if the order of g modulo n is o(n) (i.e. gk = 1 (mod n) if and only if (n)|k). Let n, m E N be co-prime. (1) Show that if g E Z is a primitive root modulo mn then g is a primitive root modulo n (and modulo m). (2) Let h = lcm(@(n), o(m)and show that any a E Z co-prime to nm satisfies that ah = 1 (mod nm). (3) Let n = P1p2 be a product of odd primes. Can there be a primitive root modulo n? Problem 5. For a composite modulus n we say that g is a primitive root modulo n if the order of g modulo n is o(n) (i.e. gk = 1 (mod n) if and only if (n)|k). Let n, m E N be co-prime. (1) Show that if g E Z is a primitive root modulo mn then g is a primitive root modulo n (and modulo m). (2) Let h = lcm(@(n), o(m)and show that any a E Z co-prime to nm satisfies that ah = 1 (mod nm). (3) Let n = P1p2 be a product of odd primes. Can there be a primitive root modulo n