Homework Help: Greatest commen divisor question

What's x and y then?

I`m sure the question is: Prove that there exist x and y, such that ax+by=gcd(a,b), for positive integers a,b.

Whar do you know about the gcd?

 

A really good way to begin any problem is by stating it clearly!

You are asked to prove that GCD(a,b)= ax+ by for SOME specific integer values of x and y.
(And typically one of x and y will be positive, the other negative.)

To answer your question- No, "claiming if d = gcd(a,b) can be devide a,b then
gcd(a,b) = ax +by " is not a good way to prove that same statement!

What theorems or properties of integers do you know that you can use?

 

What you have to prove is that there are integers x and y such that gcd(a,b) = ax + by. Well if d = gcd(a,b) then d | a and d | b, so we can say a = dm, b = dn. We then get for ANY x and y:

ax + by = dmx + dny = d(mx + ny), and d clearly divides this expression, so d divides ax + by. Since d | (ax + by) for any x and y, then choosing x and y so that (ax + by) is as small (but positive) as possible, you know that d divides it, so you have that d divides the smallest "linear combination" of a and b. What you want to end up proving is that d is the smallest linear combination of a and b, so you might want to proceed by showing that the smallest linear combination of a and b, whatever it may be, divides gcd(a,b). Have you done any group theory?