I found this problem in a problem set on primitive roots (it is later used to prove other statements) and after trying for some time I couldn't solve it.

Let $r,s \in \mathbb{N}$ prove that there exists $a,b$ coprime integers such that $a | r$, $b|s$ and $lcm(r,s) = ab$

I've tried something like: $$a | r \, , \, r|lcm(r,s) \,\Rightarrow a|lcm(r,s)$$ $$b | s \, , \, s|lcm(r,s) \,\Rightarrow b|lcm(r,s)$$ As $gcd(a,b) = 1$ then: $$ab|lcm(r,s)$$

I was trying to prove the opposite but I can't find the way.


Let $d=\gcd(r,s)$ with factorization $\prod p_i^{a_i}$. Consider each prime factor $p_i$ of $d$ in turn in order to build two components $e,f$ with $ef=d$. If the multiplicity of $p_i$ in $r$ is $a_i$, assign $p_i^{a_i}$ to $e$, otherwise assign it to $f$.

Now set $a=r/e$ and $b=s/f$. This gives $ab = rs/d = \text{lcm}(r,s)$ and for each common prime factor of $r$ and $s$ eliminates that from one of the terms $a,b$, giving $\gcd(a,b) = 1$.

  • $\begingroup$ Thanks! I was trying to avoid prime decompositon, though. $\endgroup$ – Cronenberg Feb 1 '17 at 4:38
  • $\begingroup$ @Cronenberg me too, but I think it is essential. $\endgroup$ – Joffan Feb 1 '17 at 4:46

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.