# Can I write $\gcd(n , m)$ as $r n - s m$, with $r , s \in \mathbb{N}$, if $n , m \in \mathbb{N}$?

Let $n$ and $m$ be natural numbers (positive and integers). I know (even if they are not positive) that there exist $r , s \in \mathbb{Z}$ such that $d = \gcd(n , m) = r n - s m$. But they are natural numbers. Can I take $r$ and $s$ as natural numbers?

• The problem then is that $rm+sn$ would be larger than $m$ and $n$. But usually $d$ is smaller than $m$ and $n$. We expect $r$ and $s$ to have different signs. – Lord Shark the Unknown Aug 21 '18 at 18:24
• Thank you by your observation. I am going to rewrite my question. – joseabp91 Aug 21 '18 at 18:26
• The answer is still no, by the same argument. – Lord Shark the Unknown Aug 21 '18 at 18:29
• Still, no. If $r,s\in\Bbb N$, then $\min\{r,s\}\geq1$. This means $rn+sm>\min\{m,n\}$ which isn't possible. – Clayton Aug 21 '18 at 18:29
• Okay I understand the mistake. I have rewritten the question again. – joseabp91 Aug 21 '18 at 18:40

Suppose that $m\nmid n$ and $n\nmid m$. Then $g=\gcd(m,n)$ satisfies $g<m$ and $g<n$. There are integers $r$ and $s$ with $g=rm+sn$. Neither $r$ nor $s$ can be zero

We can't have $r$, $s>0$ since $rm+sn>m>g$.

We can't have $r$, $s<0$ since $rm+sn<0<g$.

What if $r<0$ and $s>0$? We can replace $r$ and $s$ by $r'=tn+r$ and $s'=-tm+s$ for any integer $t$. We can thus make $r'>0$, and then we must get $s'<0$.

To conclude, we can always get $r>0>s$.

Then the answer is Yes, see that if $r,s\in \mathbb{N}$, then, $r\cdot m+s\cdot n\ge m+n>\text{max}\{m,n\}$. On the other hand, $\text{gcd}(m,n)|m$ and $n$, $\text{gcd}(m,n)\le\text{min}\{m,n\}<\text{max}\{m,n\}.$ Considering the condition you have mentioned($m\nmid n$ or, $n\nmid m$). If $r<0$ and $s>0$, then also we will have same issue. Hence, your claim is true.

• I have rewritten my question now – joseabp91 Aug 21 '18 at 18:44