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.

Suppose p is prime and g is a primitive element of Z_p . Show that dlog_gaⁿ = n dlog_ga (mod p 1)