1. ## 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.

2. 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?

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

3. Hello,

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

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

5. 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 it's 1.

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

7. *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?

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

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