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

Question

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?

Answer 1

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$.

Answer 2

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.