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.

  • $\begingroup$ Very useful! The part raising to the $f/f'$ power is the point I haven't done. Thank you! $\endgroup$ – kelvin hong 方 Mar 13 at 5:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.