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

Question

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?

Answer 1

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

Answer 2

if d = gcd(r,s[1]) then we can write d as a linear combination of r and s[1]. 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[1] is the smallest positive integer of the set of all linear combinations {ar + bs[1] : a,b integers}. Given this fact, if we have:

1 = a[1]*r + b[1]*s[1] and 1= a[2]*r+b[2]*s[2] 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[1]*a[2]*r^2+(a[1]*b[2]*s[2]+a[2]*b[1]*s[1])*r+b[1]*b[2]*s[1]*s[2]

Hence anything that divides r and s[1] and s[2] 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