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

- 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,989

- 6

I`m sure the question is: Prove that there

Whar do you know about the gcd?

- #3

HallsofIvy

Science Advisor

Homework Helper

- 41,833

- 961

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

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

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?

- Last Post

- Replies
- 7

- Views
- 9K

- Last Post

- Replies
- 1

- Views
- 4K

- Last Post

- Replies
- 7

- Views
- 2K

- Last Post

- Replies
- 4

- Views
- 7K

- Last Post

- Replies
- 4

- Views
- 3K

- Last Post

- Replies
- 1

- Views
- 6K

- Last Post

- Replies
- 11

- Views
- 4K

- Last Post

- Replies
- 2

- Views
- 2K

- Replies
- 8

- Views
- 2K

- Last Post

- Replies
- 8

- Views
- 2K