Here's the question you clicked on:
amistre64
Show that if a,b,c are integers; c>0; and a [congruent] b(mod m), then gcd(a,c) = gcd(b,c)
Heres what I was thinking ...
and its a = b (mod c) .. typoed it
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)
If a = b mod c then b = a + ck then gcd(b,c) = gcd(a+ck,c) = gcd(a,c) (I think)
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.
Oh, those arrows go both ways. It's an equality. Woops.
(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
Oh, I had it backwards. It works the same way, though.
I was relying on a theorem (or an extension of one, at least I think I was).
In fact this is an extension of gcd(m,n) = gcd(n,m%n)
id have to see a more detailed version of this: gcd(b,c) = gcd(a+ck,c)
k, a-b = ck like u have...
your just subing in b with a+ck ....
takes me a few times to read it right :)
Yes, relying on the theorem above....(so I guess what you want is a proof of that, in effect...
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)
Hope that's right (lots of letters to keep track of).
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)
Found a prettier version of the whole thing.....