I'd like some help completing the following proof:

Let $p$ be a prime number and let $a$ be an integer such that $a\not\equiv 0 \mod p $. Let $a$ have order $r$ modulo $p$ and $b$ have order $s$ modulo $p$. Prove that if $r$ and $s$ are coprime, then $ab$ has order $rs$ modulo $p$.

My attempt: $(ab)^{rs}=a^{rs}b^{rs} =(a^r)^s (b^s)^r \equiv 1 \mod p $. So we now just need to show that there are no positive integers $k$ smaller $rs$ such that $(ab)^k \equiv 1 \mod p $. Take $k$ to be the order of $ab$ modulo $p$. Then we know (I have previously proved this) that $k \mid rs$.

This is as far as I have got. I realise that I haven't used the assumption about r and s being coprime yet but I can't work out how to apply it.


Let $k$ denote the order of $ab$ modulo $p$. Then we have that:

$$1 \equiv (ab)^{rk} \equiv a^{rk}b^{rk} \equiv b^{rk} \mod p$$

Then we have that $s \mid rk$, but as $\gcd(r,s) = 1$ we have that $s \mid k$. Similarly we prove that $r \mid k$ and hence $rs \mid k$. As you have already proven that $k \mid rs$ we conclude that $k=rs$.


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.