Re: Primitive root - proof

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

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 = 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.

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?

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|} = 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.

Re: Primitive root - proof

Thanks, that's much easier to rememeber. :)