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?
Asked
Active
Viewed 98 times
3
-
7The 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. – Angina Seng 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
-
2The answer is still no, by the same argument. – Angina Seng Aug 21 '18 at 18:29
-
1Still, 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
-
The question now is: can I take $r$ as positive and $s$ as negative? – joseabp91 Aug 21 '18 at 18:47
2 Answers
3
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$.
Angina Seng
- 158,341
0
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.
tarit goswami
- 3,009
- 1
- 12
- 27