- Q3 3 1 Let G M N Be Such That Ged G M 1 Show That G Is A Primitive Root Modulo M If And Only If Go M P 1 Mod 1 (45.1 KiB) Viewed 373 times
Q3 3.1 Let g, m € N be such that ged(g, m) = 1. Show that g is a primitive root modulo m if and only if go(m)/P #1 (mod m) for every prime divisor p of y(m). (Here v is the Euler y-function.) 3.2 Let a, me N and suppose that am-1 = 1 (mod m) and am-1)/P # 1 (mod m), for every prime divisor p of m - 1. Show that m is prime. (Hint: Adapt your proof of the previous part to show that ord(a) = m - 1 = 4(m).) 3.3 Let p be an odd prime. Show that any primitive root mod p is a quadratic non-residue (NR) and use this to find the number of NRs mod 83 that are not primitive roots mod 83.