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, 2015 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, 2015 at 15:43

1 Answer 1


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$ Mar 6, 2015 at 16:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .