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?

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




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.