Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

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)

  • This Question is Closed
  1. amistre64
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Heres what I was thinking ...

  2. amistre64
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  3. amistre64
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  5. DanielxAK
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  7. amistre64
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    (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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  9. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  10. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  11. amistre64
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  12. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  13. amistre64
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  14. amistre64
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    takes me a few times to read it right :)

  15. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  16. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  18. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

    1 Attachment
  20. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy