• Support PF! Buy your school textbooks, materials and every day products Here!

Greatest commen divisor question

  • Thread starter Bob19
  • Start date
  • #1
71
0
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
 

Answers and Replies

  • #2
Galileo
Science Advisor
Homework Helper
1,989
6
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?
 
  • #3
HallsofIvy
Science Advisor
Homework Helper
41,770
911
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?
 
  • #4
AKG
Science Advisor
Homework Helper
2,565
3
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?
 
  • #5
71
0
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
 
  • #6
71
0
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 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?
 

Related Threads for: Greatest commen divisor question

  • Last Post
Replies
7
Views
9K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
4
Views
7K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
1
Views
6K
Replies
8
Views
2K
  • Last Post
Replies
2
Views
2K
Top