Thread: Primitive root - proof

If m is a primitive root mod n, prove that { }
runs through all numbers nod n that are relatively prime to n.

I assume it has something to do with numbers relatively prime to n
and the fact that it's a prim root it runs through all the numbers but not sure how to succinctly prove it.

What is the definition of "primitive root modulo n"?

by definition, a primitive root modulo n is an integer 1 ≤ m < n such that:

if 1 ≤ k < n with gcd(k,n) = 1, then k = m^s (mod n), for some positive integer s.

so we know that of the set {m,m²,m³,......}, which is infinite, we have some finite subset:

{m^r₁,...,m^r_φ(n)} consisting of all the 1 ≤ k < n with gcd(k,n) = 1.

now we know that gcd(1,n) = 1, so let u be the smallest positive power of m for which m^u = 1 (mod n).

i claim that if 1 < k < n with gcd(k,n) = 1, we can find 1 ≤ r < u with m^r = k (mod n).

for suppose m^t = k (mod n), but t > u. then t = qu + r, where 0 ≤ r < u, by the division algorithm for positive integers.

now if r = 0, then t = qu, thus m^t = m^qu = (m^u)^q = 1^q = 1 (mod n).

but k > 1, so r ≠ 0, hence 1 ≤ r < u. finally:

m^t = m^qu+r = (m^u)^q(m^r) = 1^qm^r = m^r (mod n)

thus every element of our finite set of powers of m is of the form: m^r, where 1 ≤ r ≤ u.

if we can prove u = φ(n), we are done, since we have only φ(n) integers 1 ≤ r ≤ φ(n).

i claim that if we have 1 ≤ k < n with gcd(k,n) = 1, that gcd(km,n) = 1, and thus if [km] is the remainder of km upon division by n, that gcd([km],n) = 1.

we know that gcd(m,n) = 1 (since m = m¹, and 1 is a positive integer), so there are integers u,v with: mu + nv = 1.

and we know that there are integers w,x with kw + nx = 1, since gcd(k,n) = 1.

therefore: (mu + nv)(kw + nx) = 1, that is: km(uw) + n(kvw + mux + nvx) = 1, so gcd(km,n) = 1.

since km = yn + [km], [km](uw) + n(uwy + kvw + mux + nvx) = 1, so that gcd([km],1) = 1, as well.

since m is in our set of powers of m, the above shows that either m = 1, or m² is also in this set.

and then either m² = 1, or m³ is also in the set, et cetera.

that is, the powers of m we have in our finite set of powers of m must be u consecutive powers of m.

but we also know we have exactly φ(n) such powers (one for each 1 ≤ k < n with gcd(k,n) = 1), hence u = φ(n).

*******

note: i apologize for being so long-winded. the essence of this post is what is known as "the euler-fermat theorem" or "euler's totient theorem." using group theory, it is trivial to show this as an easy consequence of lagrange's theorem. but i do not know what definitions you have been taught, and that i could take as "given". so i deliberately avoided using group-theoretic terms, such as "order", "inverse", or even the ring-theoretic term "unit". instead, i have striven to put things in "elementary terms", which perhaps makes the exposition more complicated. the only facts i have used are facts about integers, and integers modulo n.

Thanks, this is very helpful. I have studied some group theory, is it possible for you to show me the proof also using the group theory terms to see if it's easier to remember?

sure.

by lagrange, we have for any finite group G, and any subgroup H, that |H| divides |G|. in particular, if g is any element of G, then <g> is a subgroup of G, when |<g>| divides |G|.

since |g| = |<g>|, we have that |g| divides |G|, so |G| = k|g|.

thus g^|G| = g^k|g| = (g^|g|)^k = e^k = e.

that is, for any element g in G, g raised to the order of G is the identity.

now the elements k in Z_n, such that gcd(k,n) = 1 form a group, called the multiplicative group of units of Z_n.

the order of this group is φ(n), so for any unit k, k^φ(n) = 1 (mod n).

if there is a unit m such that every unit k = m^s (mod n), for some integer s, then m generates the group of units.

hence the group of units = <m> = {m,m²,...,m^φ(n) = 1} (if an element g generates a group G, then G is cyclic, whence |G| = |g|).

(in group-theoretic terms, a primitive element is a generator of the group of units).

this shows that if a primitive element exists (and it doesn't always, there is no primitive element for n = 8),

the group of units mod n is cyclic. for example, this is ALWAYS the case when n = p, a prime.

Thanks, that's much easier to rememeber.