Let n be a positive integer A number g is called a primitive

Let n be a positive integer. A number g is called a primitive root mod n if each b with gcd(b, n) = 1 is congruent to a power of g mod n. The first three problems determine which n have primitive roots. Let p be an odd prime and let g be a primitive root mod P. Show that p - 1 divides the order of g mod p2. Show that ord_p^2 (g) = p - 1 or p(p - 1). Show that ord_p^2(g) = p - 1 if and only if g^p = g (mod p^2). Show that if g^p = g (mod p^2), then (g + p)^p notequalto g + p (mod p^2). Show that either ord_p^2 (g) or ord_p^2(g + p) equals p(p- 1). Show that there exists b such that every c with gcd(c, p) = 1 is congruent to a power of b mod p^2.

Solution

Let p be a positive prime and g be a primitive root modulo p. 1. Let n be an integer. Then g n 1 (mod p) if and only if n 0 (mod p 1)

first , suppose g n 1 (mod p).

Then as we know g p1 1 (mod p), using the division algorithm to write n = (p 1)s + t with 0 t < p 1

we see that 1 g n g (p1)s g t g t (mod p) Suppose 0 < t < p 1. Then g can have at most t distinct powers: since g at+b (g t ) a g b (1)a g b g b

we can always reduce exponents of g modulo t, which implies that there can be at most one distinct power of g for each residue class modulo t.

Primitive roots, by definition, have p 1 distinct powers (all the units modulo p), and so this contradicts our assumption that g is a primitive root modulo p. Thus t = 0 and n 0 (mod p 1). Conversely, if n = (p 1)s then g n g p1 s 1 s 1 (mod p). For the second part, the first condition is equivalent to g jk 1 (mod p) by multiplying by g k . The second condition is equivalent to j k 0 (mod p 1). Thus the second part follows from the first

Since a n 1 (mod a n1) and no smaller exponent works (because a n is too small), ordan1(a) = n

Corollary:

Let ` = lcm(b, c) and z = ordmn(a). Then a ` 1 (mod m) and a ` 1 (mod n), so a ` 1 (mod mn), so z | `. Since a z 1 (mod mn), we have a z 1 (mod m), so b | z. Similarly, c | z, so ` | z.

b x b y (mod n) b xy 1 (mod n) ordn(b) | x y

Let p be prime and let a be an integer with a 6 0 (mod p). Then ordp(a) | p 1. (b) Let n be a positive integer and let a be an integer with gcd(a, n) = 1. Then ordn(a) | (n).

Also,Let n 2 and let p be a prime dividing Fn. Then p 1 (mod 2n+2).

This means that ordp(b) divides 2n+2 and does not divide 2n+1, so ordp(b) = 2n+2. Corollary 7.2 tells us that 2n+2 | p 1.