Results 1 to 3 of 3

Math Help - help with a proof on orders

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    55

    help with a proof on orders

    stuck on a proof..any help would be great!

    show, for any integer k>=0:

    en(a^k)= en(a) / gcd( en(a), k)

    where en(a) is the order of a modulo n, also (a,n) = 1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by minivan15 View Post
    stuck on a proof..any help would be great!

    show, for any integer k>=0:

    en(a^k)= en(a) / gcd( en(a), k)

    where en(a) is the order of a modulo n, also (a,n) = 1
    Let en(a^k) = i and en(a) = j. Thus, (a^k)^i\equiv 1(\bmod p) and it is the least positive exponent. We therefore want, a^{ki}\equiv 1(\bmod p), this happens if and only if j|ki. Let d = \gcd(j,k). Therefore, \tfrac{ki}{j} = \tfrac{(k/d)i}{(j/d)}. But \gcd(k/d,j/d)=1 so for this fraction to be a whole number we require (j/d) to divide i. The smallest such i is therefore, j/d. Which is what you wanted to prove.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    I had another proof using group theory. Consider the cyclic subgroups \left<a\right> and \left<a^k\right>.

    Define f:\left< a \right>\to\left< a^k \right> by f(a^r)=a^{rk}. This is well defined for if a^{r_1}=a^{r_2} then \mathrm{en}(a)\mid r_1-r_2; \therefore\ \mathrm{en}(a)\mid (r_1-r_2)k \Rightarrow a^{r_1k}=a^{r_2k}.

    f is surjective as i=\mathrm{en}(a^k)\leqslant\mathrm{en}(a)=j. Clearly it is also a homomorphism.

    Let j=h\gcd(j,k) and k=l\gcd(j,k).

    a^{rk}=1 \Rightarrow rk=mj for some m

    _______ \Rightarrow rl\gcd(j,k)=mh\gcd(j,k)

    _______ \Rightarrow rl=mh

    Now there are integers s,t such that sh+tl=1.

    \therefore\ a^{r}=a^{r(sh+tl)}=a^{(rs+tm)h}\in\left<a^h\right>

    Conversely, if a^{rh}\in\left<a^h\right> then f(a^{rh}) = a^{rhk} = a^{rhl\gcd(j,k)} = a^{rlj} = 1.

    Hence the kernel of f is \left<a^h\right>. \therefore\ \left<a\right>/\left<a^h\right>\cong\left<a^k\right> and the result follows (note that \left<a^h\right> has \gcd(j,k) elements).
    Last edited by JaneBennet; April 2nd 2009 at 10:32 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modulo orders
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: October 6th 2011, 10:05 AM
  2. Isomporhisms preserve orders - help with proof
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: April 3rd 2011, 02:56 AM
  3. Partial Orders
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 6th 2010, 10:33 AM
  4. Partial orders
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: January 19th 2009, 11:58 AM
  5. Orders of elements
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: January 9th 2009, 12:15 PM

Search Tags


/mathhelpforum @mathhelpforum