Good day to everyone!

I just have a quick question regarding the greatest common divisor function.

Say I have $\gcd(m,n^2)=1$. Does it follow that $\gcd(m,n)=1$?

Here is my attempt at a proof:

Since $\gcd(m,n^2)=1$, there exist integers $r$ and $s$ such that

$$rm + sn^2 = 1.$$

It follows that there exist integers $r$ and $t=sn$ such that

$$rm + tn = 1.$$

Therefore, $\gcd(m,n)=1$.

But it can't be that easy! Is my proof correct?


  • 1
    $\begingroup$ Well, it is that easy. Your proof is fine, though you might want to outline that $t = sn$ is the appropriate choice. $\endgroup$ – AlexR Mar 6 '15 at 15:42
  • 1
    $\begingroup$ Alternatively, note that if $d$ divides both $m$ and $n$, then $d$ divides both $m$ and $n^2$. $\endgroup$ – Casteels Mar 6 '15 at 15:43

Yes, the proof is that easy if you are allowed to use the Bezout identity. Else, more generally

${\bf Lemma}\quad \begin{align}a\mid A\\ b\mid B\end{align}\,\Rightarrow\,(a,b)\mid (A,B)\ \ $

${\bf Proof}\ \ \ \begin{align}(a,b)\mid a\mid A\\ (a,b)\mid b\mid B\end{align}\,\Rightarrow\, (a,b)\mid A,B\,\Rightarrow\,(a,b)\mid (A,B)$

Corollary $\ $ If $\,A,B$ are coprime so too are any respective factors $\,a,b\,$ (i.e. $\,a\mid A,\,b\mid B)$

Remark $\ $ Unlike the proof using Bezout, the above proof works in any domain where gcds exist, e.g. non-PID UFDs like $\,\Bbb Z[x]\,$ and $\,F[x,y]\,$ where there is no Bezout identity for the gcd.

  • $\begingroup$ Thank you very much for your comprehensive answer, @BillDubuque! =) $\endgroup$ – Jose Arnaldo Bebita-Dris Mar 6 '15 at 16:26

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.