## amistre64 3 years ago Show that if a,b,c are integers; c>0; and a [congruent] b(mod m), then gcd(a,c) = gcd(b,c)

1. amistre64

Heres what I was thinking ...

2. amistre64

and its a = b (mod c) .. typoed it

3. amistre64

since a = b (c); then a = b + ck, for some integer k a - b = ck ax1 + bx2 = ck ax1 + bx2 = c(y1+y2) ax1 + bx2 = cy1 + cy2 ax1 + cy1 = bx2 + cy2 ax1 + cy1 = g1, for some integer g g1 = bx2 + cy2 gcd(a,c) = gcd(b,c)

4. estudier

If a = b mod c then b = a + ck then gcd(b,c) = gcd(a+ck,c) = gcd(a,c) (I think)

5. DanielxAK

That's true. You might want to give more reasoning though: Let d = gcd(b,c). Then, gcd(b,c) => b|d and c|d. => a+ck|d and c|d. Since c|d, ck|d. And, since ck|d, a+ck|d => a|d. And, then you're done. Easier to see this way, I think.

6. DanielxAK

Oh, those arrows go both ways. It's an equality. Woops.

7. amistre64

(b,c) = d therefore d|b and d|c there is some thrm that states that the gcd of 2 numbers can be written as a linear combination of those numbers d = bx + cy

8. DanielxAK

Oh, I had it backwards. It works the same way, though.

9. estudier

I was relying on a theorem (or an extension of one, at least I think I was).

10. estudier

In fact this is an extension of gcd(m,n) = gcd(n,m%n)

11. amistre64

id have to see a more detailed version of this: gcd(b,c) = gcd(a+ck,c)

12. estudier

k, a-b = ck like u have...

13. amistre64

your just subing in b with a+ck ....

14. amistre64

takes me a few times to read it right :)

15. estudier

Yes, relying on the theorem above....(so I guess what you want is a proof of that, in effect...

16. estudier

a-b = ck like u have Let gcd(a,c) = n -> n divdes a and c so a = nq and c = nr (some q and r)

17. estudier

Hope that's right (lots of letters to keep track of).

18. estudier

So a-b = ck -> nq - b = nrk -> b = n(q-rk) -> n divides b Do same for other side and it should drop out (I hope)

19. estudier

Found a prettier version of the whole thing.....