Zn = { 0, . . . , n 1 } and Z_n = { a Z_n : gcd(a, n) = 1 }

Definition: g is a primitive element of Z_n if and only if (n) = min{ k Z⁺ : g^k = 1 (mod n) }.

When g is a primitive element of Z_n , we have Z_n = { g, g² mod n, g 3 mod n, . . . , g⁽ⁿ⁾ mod n }.

Suppose g is a primitive element of Z_n and let dlog_g(a) = min{ k > 0 : g^k = a (mod n) }. dlog_g(a) is called the discrete log of a with respect to g.

Let p is an odd prime and let g be a primitive element of Z_p. Show:

dlog_g (1) = dlog_g(p 1) = (p 1)/2.

Hint: Fermats Little Lemma