Results 1 to 3 of 3

Thread: 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, $\displaystyle (a^k)^i\equiv 1(\bmod p)$ and it is the least positive exponent. We therefore want, $\displaystyle a^{ki}\equiv 1(\bmod p)$, this happens if and only if $\displaystyle j|ki$. Let $\displaystyle d = \gcd(j,k)$. Therefore, $\displaystyle \tfrac{ki}{j} = \tfrac{(k/d)i}{(j/d)}$. But $\displaystyle \gcd(k/d,j/d)=1$ so for this fraction to be a whole number we require $\displaystyle (j/d)$ to divide $\displaystyle i$. The smallest such $\displaystyle i$ is therefore, $\displaystyle 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 $\displaystyle \left<a\right>$ and $\displaystyle \left<a^k\right>$.

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

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

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

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

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

    _______$\displaystyle \Rightarrow$ $\displaystyle rl=mh$

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

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

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

    Hence the kernel of $\displaystyle f$ is $\displaystyle \left<a^h\right>.$ $\displaystyle \therefore\ \left<a\right>/\left<a^h\right>\cong\left<a^k\right>$ and the result follows (note that $\displaystyle \left<a^h\right>$ has $\displaystyle \gcd(j,k)$ elements).
    Last edited by JaneBennet; Apr 2nd 2009 at 09: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: Oct 6th 2011, 09:05 AM
  2. Isomporhisms preserve orders - help with proof
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: Apr 3rd 2011, 01:56 AM
  3. Partial Orders
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Sep 6th 2010, 09:33 AM
  4. Partial orders
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jan 19th 2009, 10:58 AM
  5. Orders of elements
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Jan 9th 2009, 11:15 AM

Search Tags


/mathhelpforum @mathhelpforum