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

 

[Galileo]

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]

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?

 

[AKG]

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]

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 basically 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]

Hello Hall and thank You for your answer,

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

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?