Results 1 to 6 of 6
Like Tree2Thanks
  • 1 Post By Deveno
  • 1 Post By Deveno

Math Help - Primitive root - proof

  1. #1
    Member
    Joined
    Sep 2010
    Posts
    151
    Thanks
    3

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,373
    Thanks
    1314

    Re: Primitive root - proof

    What is the definition of "primitive root modulo n"?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,311
    Thanks
    691

    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.
    Last edited by Deveno; May 31st 2012 at 05:17 AM.
    Thanks from linalg123
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2010
    Posts
    151
    Thanks
    3

    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,311
    Thanks
    691

    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.
    Thanks from linalg123
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Sep 2010
    Posts
    151
    Thanks
    3

    Re: Primitive root - proof

    Thanks, that's much easier to rememeber.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: February 27th 2011, 05:59 PM
  2. Primitive Root proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 25th 2010, 11:32 AM
  3. primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 8th 2010, 08:49 AM
  4. primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 10th 2009, 05:53 PM
  5. Primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 29th 2008, 07:47 PM

Search Tags


/mathhelpforum @mathhelpforum