1
$\begingroup$

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?

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

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).$$

$\endgroup$
3
  • $\begingroup$ 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:) $\endgroup$
    – AgentS
    Sep 2 '19 at 5:44
  • 4
    $\begingroup$ 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. $\endgroup$
    – heropup
    Sep 2 '19 at 5:58
  • $\begingroup$ 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 ! $\endgroup$
    – AgentS
    Sep 2 '19 at 5:59

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.