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

Printable View

- Jan 2nd 2010, 11:10 AMkturfGCD and the Euclidean Algorithm
What can you conclude about gcd(a,b) if there are integers s,t with as+bt=6?

- Jan 2nd 2010, 11:29 AMShanks
we can conclude that gcd(a,b) is a divisor of 6.

- Jan 2nd 2010, 12:36 PMRoam
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.

- Jan 2nd 2010, 01:11 PMDrexel28
To expand upon

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

Unfortunately though,**Roam**'s observation is slightly wrong. If he considers $\displaystyle x+2y=6$ which has solution $\displaystyle x=3\cdot6,y=-2\cdot6$ (there is a reason why I didn't simplify). - Jan 2nd 2010, 06:57 PMRoam
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. - Jan 2nd 2010, 08:27 PMDrexel28
- Jan 3rd 2010, 03:20 AMShanks
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.