What is the definition of "primitive root modulo n"?
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.
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^{2},m^{3},......}, which is infinite, we have some finite subset:
{m^{r1},...,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^{q}m^{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^{1}, 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^{2} is also in this set.
and then either m^{2} = 1, or m^{3} 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.
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^{2},...,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.