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.

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

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

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

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.

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

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

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