- #1

- 71

- 0

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

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Bob19
- Start date

- #1

- 71

- 0

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

- #2

Galileo

Science Advisor

Homework Helper

- 1,991

- 6

I`m sure the question is: Prove that there

Whar do you know about the gcd?

- #3

HallsofIvy

Science Advisor

Homework Helper

- 41,847

- 967

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?

- #4

AKG

Science Advisor

Homework Helper

- 2,565

- 4

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

- #5

- 71

- 0

AKG said:

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 disthe 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

- #6

- 71

- 0

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:

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?

Share: