# elem.num.theo - GCD

• Oct 9th 2008, 12:56 PM
cassiopeia1289
elem.num.theo - GCD
OK: Given: There exists an x and y such that ax+by=2. Can you conclude that gcd(a,b)=2? If yes, why? If no, what can you say about the gcd(a,b)?

So I know you can do it the other way around, so gcd(a,b)=2 does equal ax+by=2 - but I wasn't sure you could switch it. Even then, I would need more proof that it doesn't work. Some kind of guidance would be lovely.
• Oct 9th 2008, 01:00 PM
Jhevon
Quote:

Originally Posted by cassiopeia1289
OK: Given: There exists an x and y such that ax+by=2. Can you conclude that gcd(a,b)=2? If yes, why? If no, what can you say about the gcd(a,b)?

no.

example, take two numbers a and b where you know the gcd is 1. so we have ma + nb = 1 for some integers m and n. now multiply that equation by 2, we get

(2m)a + (2n)b = 2, write 2m as x and 2n as y, we have xa + yb = 2

but we know the gcd is 1! what can you say therefore?

Quote:

So I know you can do it the other way around, so gcd(a,b)=2 does equal ax+by=2 - but I wasn't sure you could switch it. Even then, I would need more proof that it doesn't work. Some kind of guidance would be lovely.
yes, if gcd(a,b) = 2, then you can write a linear combination of a and b equaling 2
• Oct 9th 2008, 01:06 PM
Moo
Hello,

Please remember that :
au+bv=n <=> gcd(a,b) divides n
gcd(a,b)=n => there exist u,v such that au+bv=n

au+bv=1 <=> gcd(a,b)=1
• Oct 9th 2008, 01:16 PM
cassiopeia1289
Quote:

Originally Posted by Moo
au+bv=1 <=> gcd(a,b)=1

but didn't Jhevon just prove that wasn't the case?
I didn't think it was an if and only if case
• Oct 9th 2008, 01:17 PM
Moo
Quote:

Originally Posted by cassiopeia1289
but didn't Jhevon just prove that wasn't the case?
I didn't think it was an if and only if case

It is "if and only if", if and only if (Rofl) it's 1.
• Oct 9th 2008, 01:18 PM
Jhevon
Quote:

Originally Posted by cassiopeia1289
but didn't Jhevon just prove that wasn't the case?
I didn't think it was an if and only if case

haha, no i didn't. i was addressing the linear combination = 2, not 1

as Moo said, a linear combination just yields a multiple of the gcd
• Oct 9th 2008, 01:21 PM
cassiopeia1289
*ok, officially more confused than I started out*

so it is true!
since ax+by=2 <=> gcd(a,b)=2

or does that case only work with 1 and not 2?
• Oct 9th 2008, 01:23 PM
Jhevon
Quote:

Originally Posted by cassiopeia1289
*ok, officially more confused than I started out*

so it is true!
since ax+by=2 <=> gcd(a,b)=2

no. i started out with the gcd = 1 and showed that i could still write it as a linear combination as 2, or 3 or anything. so the linear combination yielding 2 did not imply the gcd was 2 (because we knew it was 1 in the first place). i just provided a counter-example

Quote:

or does that case only work with 1 and not 2?
it only works for 1, nothing else