about order of number

Question

prove that if $n\in N$，（ab，n)=1,$(ord_na,ord_nb)$=1,then $ord_n(ab)=ord_na\cdot ord_nb$

My attempt suppose $a’=ord_na$,$b’=ord_nb$ then $a^{a’}\equiv 1 \pmod n$. $b^{b’} \equiv 1 \pmod n$ Then I can get $(ab)^{a’b’} \equiv 1\pmod n$ The next I should proof a’b’=$ord_nab$,I think I may use (a’,b’)=1, I think if I proof for any h such that $(ab)^h\equiv 1\pmod n$ we have a’b’|h,then we finish .but I can’t figure it out

Answer 1

Hint $ $ If $\,(ab)^{\large k}\! = 1\,$ let $\,c = a^{\large k}\! = b^{\large -k}\,$ so $\,c^{\large a'}\!\!=1=c^{\large b'}\!$ $\Rightarrow {\rm ord}\, c = c'\mid a',b'$ coprimes, so $c' = 1$ hence $\,c = 1,\,$ therefore $\,a^k = 1 = b^k,\,$ so $\,a',b'\mid k\,$ so their lcm $\,a'b'\mid k$

Answer 2

Hint:

As you have shown $$(ab)^{a’b’}\equiv 1\pmod{n}.$$

Now, suppose the order of $ab$ is $a_1 b_1$, where $a_1$ is a divisor of $a’$ and $b_1$ is a divisor if $b’$. This means there are integers $a_2, b_2$ such that $$a_1 a_2=a’, \quad b_1b_2=b’.$$

Now $$a^{a_1b_1}b^{a_1b_1}\equiv1\pmod{n}.$$ Consider what happens when you raise this congruence to $a_2$ and use the fact that $a’$ and $b’$ are coprime to prove $b_1=b’$. Similarly for $a’$.

Edit:

Sorry, there were a few mistakes in my post, which I have cleared up. Since you are still stuck, more explicitly, raising to $a_2$ gives $$b^{a’b_1}\equiv1\pmod{n}$$ and so $b’$ must divide $a’b_1$. Clearly it cannot divide $a’$ and so must divide $b_1$. Since $b_1$ divides $b’$, this means $b_1=b’$. The same argument shows $a’=a_1$.

Edit 2:

Here is a proof for the existence of the integers $a_1$ and $b_1$:

First, let $x$ be any integer coprime to $n$, such that the order of $x$ is $m$. We will show that, if $$x^k\equiv1\pmod{n},$$ for some integer $k$, then $m$ divides $k$.

Assume, for contradiction, $m$ does not divide $k$, then $$k=mq +r,$$ where $1\leq r\lt m$. Thus $$x^k\equiv x^{mq+r}\equiv x^{mq}x^{r}\equiv x^r\equiv1\pmod{n},$$ which is a contradiction, since $m$ is the smallest integer power of $x$ congruent to $1$ modulo $n$.

It now follows that, if $m$ is the order of $ab$, then $m$ divides $a’b’$. Assume $m$ only divides $a’$, then $$mk=a’.$$ However, $$\left(a^mb^m\right)^k\equiv1\pmod{n}\\\implies b^{a’}\equiv1\pmod{n}$$ and the last congruence implies $b’$ divides $a’$, which is a contradiction. Thus, $$m=a_1 b_1$$ where $a_1$ is a factor of $a’$ and $b_1$ is a factor of $b’$.

Answer 3

First prove (Ia): If $x\in \Bbb Z^+$ and $a^x\equiv 1 \pmod n$ then $a'\,|x.$ Similarly, (Ib): If $y\in \Bbb Z^+$ and $b^y\equiv 1 \pmod n$ then $b'\,|y.$

Let $z=$ord$_n(ab).$

Then modulo $n$ we have $$1\equiv (ab)^{a'z}\equiv (a^{a'})^z \cdot b^{a'z}\equiv 1^z\cdot b^{a'z}\equiv b^{a'z}.$$ So $b'\,|a'z$ by (Ib). Now $(a',b')=1,$ so $b'\,|a'z\implies b'|z.$

Similarly, by (Ia) we have $1\equiv(ab)^{b'z}\equiv a^{b'z}\implies a'\,|b'z\implies a'\,|z.$

Now $a',b'$ are co-prime divisors of $z,$ so $a'b'\,|z.$

Therefore ord$_n(ab)= z\geq a'b'.$

And since $(ab)^{a'b'}\equiv 1$ we also have ord$_n(ab)\leq a'b'.$