3

Here's the question:

Let $a$ and $b$ be integers such that $\gcd(a,b) = 1$. Let $r$ and $s$ be integers such that

$$ar + bs =1.$$

Prove that $\gcd(a,s) = \gcd(r,b) = \gcd(r,s) = 1$.

I was stuck how to solve this problem. My first instinct is to do a proof by contradiction, that is, assume the $\gcd(a,s) > 1$ - therefore there exists a $d > 1$ such that $a = dn$ for an integer $n$ and $s = dm$ for an integer $m$. However, I don't know where to go from here (or even if this is the correct route).

I would really appreciate some help - thank you in advance for everything!

Thanks!

Martin Sleziak
  • 53,687
Billy Thorton
  • 769
  • This is special case of Bezout's identity. here – BigM Sep 10 '14 at 03:49
  • See also http://math.stackexchange.com/questions/671748/show-that-if-ar-bs-1-for-some-r-and-s-then-a-and-b-are-relatively and http://math.stackexchange.com/questions/1517862/prove-that-%E2%88%80a-b-u-v-%E2%88%88-z-%E2%88%92-0-ua-vb-1-%E2%86%92-gcda-b-1 – Martin Sleziak Jan 30 '16 at 13:38

3 Answers3

7

You actually only need to know that $ar+bs=1$, it then follows that $$\gcd(a,b)=\gcd(a,s)=\gcd(r,b)=\gcd(r,s)=1.$$

A proof is as follows: the $\gcd$ of $a,b$ divides the expression $ar+bs$, since it divides both $a$ and $b$. Therefore it divides 1, which means it must be equal to 1. You then perform similar arguments replacing the pair $(a,b)$ with $(a,s)$, $(r,b)$ or $(r,s)$.

Peter Huxford
  • 2,561
  • Why does the gcd(a,b) also divide the pair (a,s) or (r,b)? – Billy Thorton Sep 10 '14 at 03:57
  • When I say, "replacing the pair $(a,b)$ with $(a,s)$" for example, I mean it as follows: the $\gcd$ of $a,s$ must divide the expression $ar+bs$ because it divides $a$ and $s$. For the same reason as above, $\gcd(a,s)$ divides 1. – Peter Huxford Sep 10 '14 at 04:00
3

All the integers in the equation are on equal footing, we know that the gcd of two numbers divides every integral combination of the two, since only $1|1$ in natural numbers, if we pick our "special" integers to be $a,s$ then we note the corresponding integers in the Euclidean algorithm process are $r, b$ and so the first result follows. The exact same argument holds when we declare $r,b$ and $r,s$ to be special with corresponding pairing integers $a,s$ and $a,b$ respectively.

More explicitly, if you don't know that theorem on gcd dividing all the integer combinations, just let $d>0$ and $d|a, d|s$ then

$$\begin{cases} a=dk \\ s = dj\end{cases}$$

so $d(kr+jb)=1$ and $d|1\implies d=1$

Again, you clone the argument for the other choices. Successively writing $r=d\ell, b=dm$ and $r=dn, s=dp$ and each time concluding $d|1\implies d=1$.

Adam Hughes
  • 36,777
  • Thank you for your help! If it fails for one, does the whole thing fail (e.g. as part of the proof should you "check" the other choices as well or is one of the answers != 1 good enough)? – Billy Thorton Sep 10 '14 at 03:37
  • @BillyThorton Really one is good enough, since they are all symmetric, since $ar=ra$ they are on equal footing as far as which pairs you select, you can validly say "the proof is the same for the other pairs." – Adam Hughes Sep 10 '14 at 03:38
0

Let $d$ be the $gcd$ of $(a,s)$, that is, $d=gcd(a,s)$. We want to see that $d=1$.

By definition of gcd, $d|a$ and $d|s$, therefore $d|(ar+bs)$ but $ar+bs=1$, so $d|1$. Thus, the only possibility is $d=1$.

The same argument is valid for the other cases.

Hope that helps.

Gerard Gracia
  • 321