# If $\gcd(m,n)=1$, $m\mid (a^s-1)$ and $n\mid (a^t-1)$ then show that $mn \mid (a^{lcm(s,t)}-1)$

If $$\gcd(m,n)=1$$,
$$m\mid (a^s-1)$$ and $$n\mid (a^t-1)$$ then show that $$mn \mid (a^{lcm(s,t)}-1)$$

I've just stumbled on this as part of some other proof. To be honest I didn't give it my best shot but here is how I'm trying to proceed and seem to get stuck:

$$a^{st}-1 = \left(a^s\right)^t-1 = (a^s-1)(1+a^s+a^{2s}+\cdots+a^{s(t-1)}) =mK$$
$$a^{st}-1 = \left(a^t\right)^s-1 = (a^t-1)(1+a^t+a^{2t}+\cdots+a^{t(s-1)})=nL$$

That means $$m,n \mid (a^{st}-1)$$
I feel it helps to first show $$mn\mid (a^{st}-1)$$
Any help?

• Are you familiar with congruences? Sep 2 '19 at 5:06
• Not quite good but I can understand @DivyaPrakashSinha Sep 2 '19 at 5:08
• I am not comfortable with latex. May I send the photo solution? Sep 2 '19 at 5:16
• Aha sure that will definitely help thank you so much @DivyaPrakashSinha :) Sep 2 '19 at 5:17
• Size of the picture is large, so I have added the link. Sep 2 '19 at 5:38

Here is the solution.

Chinese's remainder theorem can also be used to solve the congruences.

Content of the photograph, with additional editorial changes:

Denote $$\operatorname{lcm}(s,t)$$ by $$[s,t]$$.

Since $$s \mid [s,t]$$ and $$t \mid [s,t]$$, and since we are given $$a^s \equiv 1 \pmod m \quad \text{and} \quad a^t \equiv 1 \pmod n,$$ it follows that $$a^{[s,t]} \equiv 1 \pmod m \quad \text{and} \quad a^{[s,t]} \equiv 1 \pmod n.$$ Hence $$a^{[s,t]} = mk+1$$ for some integer $$k$$; then $$mk + 1 \equiv 1 \pmod n,$$ or $$mk \equiv 0 \pmod n.$$ Thus $$n \mid mk$$, but since $$\gcd(m,n) = 1$$, it follows that $$n \mid k$$. So let $$k = nl$$ for some integer $$l$$, from which we finally obtain $$a^{[s,t]} = mnl + 1$$, or equivalently, $$mn \mid (a^{[s,t]} - 1).$$

• That's slick! Basically you've used CRT to solve the system $x\equiv 1 \pmod m$ and $x\equiv 1\pmod n$ where $x = a^{[s,t]}$. Thanks a lot:) Sep 2 '19 at 5:44
• I have edited your answer to include your proof using MathJax. You can see the MathJax code by right-clicking on the expression (control-click on some operating systems) and choosing from the drop-down menu "Show Math As..." then "TeX commands". Learning how to typeset mathematics with MathJax is an extremely useful and efficient way to communicate on this site and is highly recommended. Sep 2 '19 at 5:58
• Now that I think back, had I known $a^s \equiv 1 \implies a^{[s,t]}\equiv 1$, I would've managed to prove this on my own haha Thanks again @heropup and Prakash ! Sep 2 '19 at 5:59