# A question regarding the greatest common divisor

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?

Thanks!

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

## 1 Answer

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.

• Thank you very much for your comprehensive answer, @BillDubuque! =) Mar 6, 2015 at 16:26