A community for students.
Here's the question you clicked on:
 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)
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

amistre64
 3 years ago
Best ResponseYou've already chosen the best response.0Heres what I was thinking ...

amistre64
 3 years ago
Best ResponseYou've already chosen the best response.0and its a = b (mod c) .. typoed it

amistre64
 3 years ago
Best ResponseYou've already chosen the best response.0since 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)

estudier
 3 years ago
Best ResponseYou've already chosen the best response.1If a = b mod c then b = a + ck then gcd(b,c) = gcd(a+ck,c) = gcd(a,c) (I think)

DanielxAK
 3 years ago
Best ResponseYou've already chosen the best response.0That's true. You might want to give more reasoning though: Let d = gcd(b,c). Then, gcd(b,c) => bd and cd. => a+ckd and cd. Since cd, ckd. And, since ckd, a+ckd => ad. And, then you're done. Easier to see this way, I think.

DanielxAK
 3 years ago
Best ResponseYou've already chosen the best response.0Oh, those arrows go both ways. It's an equality. Woops.

amistre64
 3 years ago
Best ResponseYou've already chosen the best response.0(b,c) = d therefore db and dc 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

DanielxAK
 3 years ago
Best ResponseYou've already chosen the best response.0Oh, I had it backwards. It works the same way, though.

estudier
 3 years ago
Best ResponseYou've already chosen the best response.1I was relying on a theorem (or an extension of one, at least I think I was).

estudier
 3 years ago
Best ResponseYou've already chosen the best response.1In fact this is an extension of gcd(m,n) = gcd(n,m%n)

amistre64
 3 years ago
Best ResponseYou've already chosen the best response.0id have to see a more detailed version of this: gcd(b,c) = gcd(a+ck,c)

estudier
 3 years ago
Best ResponseYou've already chosen the best response.1k, ab = ck like u have...

amistre64
 3 years ago
Best ResponseYou've already chosen the best response.0your just subing in b with a+ck ....

amistre64
 3 years ago
Best ResponseYou've already chosen the best response.0takes me a few times to read it right :)

estudier
 3 years ago
Best ResponseYou've already chosen the best response.1Yes, relying on the theorem above....(so I guess what you want is a proof of that, in effect...

estudier
 3 years ago
Best ResponseYou've already chosen the best response.1ab = ck like u have Let gcd(a,c) = n > n divdes a and c so a = nq and c = nr (some q and r)

estudier
 3 years ago
Best ResponseYou've already chosen the best response.1Hope that's right (lots of letters to keep track of).

estudier
 3 years ago
Best ResponseYou've already chosen the best response.1So ab = ck > nq  b = nrk > b = n(qrk) > n divides b Do same for other side and it should drop out (I hope)

estudier
 3 years ago
Best ResponseYou've already chosen the best response.1Found a prettier version of the whole thing.....
Ask your own question
Sign UpFind more explanations on OpenStudy
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
 Engagement 19 Mad Hatter
 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.