Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

amistre64 Group Title

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

  • 2 years ago
  • 2 years ago

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

    Heres what I was thinking ...

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

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

    • 2 years ago
  3. amistre64 Group Title
    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)

    • 2 years ago
  4. estudier Group Title
    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)

    • 2 years ago
  5. DanielxAK Group Title
    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.

    • 2 years ago
  6. DanielxAK Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  7. amistre64 Group Title
    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

    • 2 years ago
  8. DanielxAK Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  9. estudier Group Title
    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).

    • 2 years ago
  10. estudier Group Title
    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)

    • 2 years ago
  11. amistre64 Group Title
    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)

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

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

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

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

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

    takes me a few times to read it right :)

    • 2 years ago
  15. estudier Group Title
    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...

    • 2 years ago
  16. estudier Group Title
    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)

    • 2 years ago
  17. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

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

    • 2 years ago
  18. estudier Group Title
    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)

    • 2 years ago
  19. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

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

    • 2 years ago
    1 Attachment
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.