Thread: help with a proof on orders

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

2. 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, $(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.

3. I had another proof using group theory. Consider the cyclic subgroups $\left$ and $\left$.

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$

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

Hence the kernel of $f$ is $\left.$ $\therefore\ \left/\left\cong\left$ and the result follows (note that $\left$ has $\gcd(j,k)$ elements).