# help with a proof on orders

• Apr 1st 2009, 06:20 PM
minivan15
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
• Apr 2nd 2009, 08:11 PM
ThePerfectHacker
Quote:

Originally Posted by minivan15
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.
• Apr 2nd 2009, 09:14 PM
JaneBennet
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).