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

Printable View

- Jan 2nd 2010, 12:10 PMkturfGCD 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, 12:29 PMShanks
we can conclude that gcd(a,b) is a divisor of 6.

- Jan 2nd 2010, 01: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, 02:11 PMDrexel28
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). - Jan 2nd 2010, 07: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, 09:27 PMDrexel28
- Jan 3rd 2010, 04: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.