# Greatest commen divisor question

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 devide a,b then
gcd(a,b) = ax +by ??

/Bob

Related Introductory Physics Homework Help News on Phys.org
Galileo
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?

HallsofIvy
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 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?

AKG
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?

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 devide 'a' and 'b'. Then this proofs that there the gcd(a,b) equals the linear combinations "ax+by" ?

/Bob

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 refering 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 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?