3
$\begingroup$

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?

$\endgroup$
  • 7
    $\begingroup$ 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. $\endgroup$ – Lord Shark the Unknown Aug 21 '18 at 18:24
  • $\begingroup$ Thank you by your observation. I am going to rewrite my question. $\endgroup$ – joseabp91 Aug 21 '18 at 18:26
  • 2
    $\begingroup$ The answer is still no, by the same argument. $\endgroup$ – Lord Shark the Unknown Aug 21 '18 at 18:29
  • 1
    $\begingroup$ Still, no. If $r,s\in\Bbb N$, then $\min\{r,s\}\geq1$. This means $rn+sm>\min\{m,n\}$ which isn't possible. $\endgroup$ – Clayton Aug 21 '18 at 18:29
  • $\begingroup$ Okay I understand the mistake. I have rewritten the question again. $\endgroup$ – joseabp91 Aug 21 '18 at 18:40
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I have rewritten my question now $\endgroup$ – joseabp91 Aug 21 '18 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.