# Show that if $\gcd(r,s_1) =\gcd(r,s_2) = 1$, then $\gcd(r,s_1s_2) = 1$

Never mind the question. I want to try to solve that on my own. What I want to understand is how this: "Hint. $1 = ar + bs_1,\ 1 = ar + bs_2$" relates to solving it.

I'm a little confused by this statement, especially since it applies to integers.

If we say ar + bs = 1, that says to me that you have different multiples of r and s. And when you add those multiples you get 1. How can this happen unless you are adding fraction together or something, or one expression equals 1 while the other equals 0?

• do you know $\gcd (r,s)=1 \iff 1 = ar + bs$ for some a and b integers? – user 1 Mar 24 '15 at 17:21
• @user1, Isn't that Bezout's Lemma? – Prasun Biswas Mar 24 '15 at 17:23
• yeah, I know, that's what I keep hearing, but I don't understand why that is the case – user226106 Mar 24 '15 at 17:23
• Yes, sometimes called Bezout's identity, although it isn't an identity. – Thomas Andrews Mar 24 '15 at 17:24
• And there isn't a proof in your book/course material/whatever you are studying that gave you this problem? @user226106 – Thomas Andrews Mar 24 '15 at 17:24

Integers can be negative, too. You can have $2 \times 5 + ( -3) \times 3= 1$ for example.

if d = gcd(r,s) then we can write d as a linear combination of r and s. This comes out of Euclid's algorithm for finding the gcd of two integers, or alternatively you can prove that the gcd of r and s is the smallest positive integer of the set of all linear combinations {ar + bs : a,b integers}. Given this fact, if we have:

1 = a*r + b*s and 1= a*r+b*s for some a[k], b[k] (here I think the a's and b's are not necessarily the same in both equations)

Then multiplying both equations together we have:

1 = a*a*r^2+(a*b*s+a*b*s)*r+b*b*s*s

Hence anything that divides r and s and s divides 1 which proves the claim.

Does that help? The key thing is that you can always write the gcd of 2 integers as a linear combo of them both, eg: 1 = 7 x 7 - 4 x 12 where gcd(7,12) = 1

All books on elementary number theory will demonstrate this, a classic is:

http://www.amazon.co.uk/The-Higher-Arithmetic-Introduction-Numbers/dp/0521722365

cheers