# Greatest commen divisor question

Bob19
Hi got basic question:

I'm suppose to prove that gcd(a,b) = ax+by,

What is the best way of proving this?

Is that by claiming if d = gcd(a,b) can be divide a,b then
gcd(a,b) = ax +by ??

/Bob

Homework Helper
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?

Homework Helper
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 divide 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?

Homework Helper
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?

Bob19
AKG said:
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?

Hi AKG,

No I haven't done any group theory yet! Please bear with me,
So basicly what You are saying is that if I need to show is that if one choose an 'x' and 'y' small enough and d can be divide 'a' and 'b'. Then this proofs that there the gcd(a,b) equals the linear combinations "ax+by" ?

/Bob

Bob19

The only integer theorem I know, is that "Every integer n > 1 is either a prime or a product of primes". Is that what You are referring too ?

/Bob

HallsofIvy said:
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 divide 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?