# Thread: GCD and the Euclidean Algorithm

1. ## GCD and the Euclidean Algorithm

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

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

3. 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.

4. 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 $ax+by=c$ (a linear Diophantine equation) is solvable precisely when $c=m\cdot (a,b)$ for some $m\in\mathbb{Z}$. It follows that $\frac{6}{(a,b)}\in\mathbb{Z}\implies (a,b)\mid 6$.

Unfortunately though, Roam's observation is slightly wrong. If he considers $x+2y=6$ which has solution $x=3\cdot6,y=-2\cdot6$ (there is a reason why I didn't simplify).

5. Originally Posted by Drexel28
To expand upon Shanks's explanations it can be proven that the equation $ax+by=c$ (a linear Diophantine equation) is solvable precisely when $c=m\cdot (a,b)$ for some $m\in\mathbb{Z}$. It follows that $\frac{6}{(a,b)}\in\mathbb{Z}\implies (a,b)\mid 6$.

Unfortunately though, Roam's observation is slightly wrong. If he considers $x+2y=6$ which has solution $x=3\cdot6,y=-2\cdot6$ (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.

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!

7. 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).