# Thread: Primitive root - proof

1. ## Primitive root - proof

If m is a primitive root mod n, prove that { $m,m^2,m^3,.......,m^\phi^(^n^)$}
runs through all numbers nod n that are relatively prime to n.

I assume it has something to do with $\phi(n) =$ 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.

2. ## Re: Primitive root - proof

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

3. ## Re: Primitive root - proof

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 = ms (mod n), for some positive integer s.

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

{mr1,...,mrφ(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 mu = 1 (mod n).

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

for suppose mt = 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 mt = mqu = (mu)q = 1q = 1 (mod n).

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

mt = mqu+r = (mu)q(mr) = 1qmr = mr (mod n)

thus every element of our finite set of powers of m is of the form: mr, 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 = m1, 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 m2 is also in this set.

and then either m2 = 1, or m3 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.

4. ## Re: Primitive root - proof

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?

5. ## Re: Primitive root - proof

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| = gk|g| = (g|g|)k = ek = e.

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

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

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 = ms (mod n), for some integer s, then m generates the group of units.

hence the group of units = <m> = {m,m2,...,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.

6. ## Re: Primitive root - proof

Thanks, that's much easier to rememeber.