Thread: GCD and the Euclidean Algorithm

What can you conclude about gcd(a,b) if there are integers s,t with as+bt=6?

we can conclude that gcd(a,b) is a divisor of 6.

Also you can conclude that a and b are NOT relatively prime since their gcd is 6. Because two integers a and b are relatively prime if gcd(a,b)=1.

Originally Posted by kturf

What can you conclude about gcd(a,b) if there are integers s,t with as+bt=6?

To expand upon Shanks's explanations it can be proven that the equation (a linear Diophantine equation) is solvable precisely when for some . It follows that .

Unfortunately though, Roam's observation is slightly wrong. If he considers which has solution (there is a reason why I didn't simplify).

Originally Posted by Drexel28

To expand upon Shanks's explanations it can be proven that the equation (a linear Diophantine equation) is solvable precisely when for some . It follows that .

Unfortunately though, Roam's observation is slightly wrong. If he considers which has solution (there is a reason why I didn't simplify).

Thanks for spotting my mistake; I had that backwards. "as+bt=6" simply implies that gcd(a,b) divides 6. For instance if you take a=4, b =6, then gcd(a,b) = 2 but 0a+1b = 6.

On the other hand, if gcd(a,b)=6, then 6 divides them both so they have a common factor besides 1 (2,3,6 are all common factors). "gcd(a,b)=1" is a pretty common definition of integers being relatively prime.
And yes, if you wanted to use this argument to prove that a and b are not relatively prime, then that doesn't work. Consider for instance: a = 2, b= 3, which are definitely relatively prime as they are both prime, but 6b+(-6)a = 6.

Originally Posted by Roam

Thanks for spotting my mistake; I had that backwards. "as+bt=6" simply implies that gcd(a,b) divides 6. For instance if you take a=4, b =6, then gcd(a,b) = 2 but 0a+1b = 6.

On the other hand, if gcd(a,b)=6, then 6 divides them both so they have a common factor besides 1 (2,3,6 are all common factors). "gcd(a,b)=1" is a pretty common definition of integers being relatively prime.
And yes, if you wanted to use this argument to prove that a and b are not relatively prime, then that doesn't work. Consider for instance: a = 2, b= 3, which are definitely relatively prime as they are both prime, but 6b+(-6)a = 6.

If you look closely your last example is precisely the example I used!

In fact, gcd(a,b) is the smallest positive integer of the form as+bt,where s and t are integers.
further more, all numbers of the form as+bt is in the multiple table of gcd(a,b).

I hope this would help you.