Question

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

Answer 1

Heres what I was thinking ...

Answer 2

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

Answer 3

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)

Answer 4

If a = b mod c then b = a + ck

then gcd(b,c) = gcd(a+ck,c) = gcd(a,c)

(I think)

Answer 5

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.

Answer 6

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

Answer 7

(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

Answer 8

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

Answer 9

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

Answer 10

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

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

takes me a few times to read it right :)

Answer 15

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

Answer 16

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)

Answer 17

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

Answer 18

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)

Answer 19

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