# If $(a,m)=(b,m)=1$ and if $(\exp_m(a),\exp_m(b))=1$, prove that $\exp_m(ab)=\exp_m(a)\exp_m(b).$

If $$(a,m)=(b,m)=1$$ and if $$(\exp_m(a),\exp_m(b))=1$$, prove that $$\exp_m(ab)=\exp_m(a)\exp_m(b).$$

The notation $$\exp_m(a)$$ is denote the smallest positive integer $$n$$ such that $$a^n\equiv 1\pmod m$$.

My proof: Let $$f=\exp_m(a)$$, $$h=\exp_m(b)$$, then let $$n=\exp_m(ab)$$, we have $$(ab)^n\equiv 1\pmod m$$ I want to argue that $$f|n, h|n$$ so $$n=fk$$, but I realize it is also possible that there is $$f'|f$$ and $$h'|h$$, although $$a^{f'}\not\equiv 1\pmod m$$, and $$b^{h'}\not\equiv 1\pmod m$$, but we can also have $$a^{f'}b^{h'}\equiv 1\pmod p$$, I cannot disprove this possibility, any suggestion?

Suppose, by way of contradiction, that it is possible that $$a^{f'}b^{h'}\equiv 1\pmod p.$$ Since $$f'\vert f$$, the ratio $$f/f'$$ is an integer. Raise the congruence to that power. Since $$a^f\equiv 1\pmod p$$, this reduces to $$b^{h'{f}/{f'}} \equiv 1 \pmod p.$$ Since $$h'$$ is a proper divisor of $$h$$ and $$f$$ is coprime to $$h$$, the exponent $$h'f/f'$$ is not a multiple of $$h$$. However, since $$h$$ is the smallest exponent for which $$b^h\equiv1\pmod p$$, every such exponent must be a multiple of $$h$$. So we have a contradiction.
• Very useful! The part raising to the $f/f'$ power is the point I haven't done. Thank you! – kelvin hong 方 Mar 13 at 5:44