3
$\begingroup$

I have this math problem. The question is:

Suppose that $a$ and $b$ are positive integers, with $d = \gcd(a, b)$. Suppose that there exists integers $r$ and $s$ so that $ar + bs= d$. We want to show that $r$ and $s$ are relatively prime using the following procedures:

i) Let $k \in \mathbb{Z}$ such that $k \mid r$ and $k \mid s$. Use "If $A\mid C$ and $B\mid D$, then $AB\mid CD$" to show that $kd \mid d$.

ii) Use the result from part i to conclude that $ k \le 1$ and hence $\gcd(r, s) = 1$. This prove that $r$ and $s$ are relatively prime.

So far I have that we know that since $k\mid r$ then $k\mid ar$. We also know that since $k\mid s$, then $k\mid bs$. So, since $k\mid ar$ and $k\mid bs$ we know $k\mid (ar+bs)$. Therefore, $k\mid d$. However, I'm not sure where to go from here. Thanks

$\endgroup$
  • $\begingroup$ Show that k divides $a/d$ and $b/d$ and conclude that k divides 1. $\endgroup$ – Nitrogen Oct 8 '15 at 2:29
4
$\begingroup$

First Proof

Claim. $kd\mid d$.

Proof $d\mid a \land k\mid r \implies kd\mid ar$

$d\mid b \land k\mid s \implies kd\mid bs$

$\therefore kd\mid ar+bs\implies kd\mid d\implies ??$

Second Proof

But I think that the proof can be done in much simple way if you just notice that $r\left(\dfrac{a}{d}\right)+s\left(\dfrac{b}{d}\right)=1$. Then from Bezout's Identity you can easily conclude that $\gcd(r,s)=1$.

$\endgroup$
1
$\begingroup$

Do what they say. You have $k\mid r$ and $d\mid a$ so you have $kd\mid ar$. You have $k\mid s$ and $d\mid b$ so you have $kd\mid bs$ so you have $kd\mid ar + bs = d$. So you have $kd\mid d$.

Thus $k\leq 1$, which means $1$ is the largest number that divides both $r$ and $s$ so $\gcd(r,s) =1$.

$\endgroup$
  • $\begingroup$ So $k\le 1$ because $kd\le d$? $\endgroup$ – KFC Oct 8 '15 at 2:58
0
$\begingroup$

By the result with caps that they quote, from $k$ divides $r$ and $d$ divides $a$ we conclude that $kd$ divides $ra$. Similarly, $kd$ divides $sb$. So $kd$ divides the sum $ra+sb$, and therefore $kd$ divides $d$. For positive $k$ this is only possible if $k=1$.

$\endgroup$
0
$\begingroup$

Use the technique of incorporating new information into a given equation: Let $a=da'$ and $b=db'$ where $a',b'$ are integers. The main equation is then $$d=ar+bs=da'r+db's=d(a'r+b's).$$

We can divide through by $d$ to get $a'r+b's=1.$ Now if $e$ is any common divisor of $r$ and $s,$ we have $$(e|r\land e|s)\implies (e|a'r\land e|b's)\implies e|(a'r+b's)=1\implies e=\pm 1.$$

Footnote: $\gcd (a,b)$ is not $0$ if $a$ and are not both $0,$ and $\gcd(0,0)$ does not exist. The hypothesis $d=ar+bs\in \Bbb Z$ implies that $d$ exists, implying $d\ne 0.$ So we $can$ divide by $d.$

$\endgroup$

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.