1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 2 short proofs

  1. Mar 22, 2009 #1
    1. The problem statement, all variables and given/known data
    1. Prove that if ca=cb (mod m) and gcd(c,m)=1, then a=b (mod m)
    2. Prove that if a=b (mod m), then gcd(a,m)=gcd(b,m)

    2. Relevant equations

    3. The attempt at a solution

    I can't figure out how to get started on these, especially the last one. Is it just a matter of expanding definitions?
    Last edited: Mar 22, 2009
  2. jcsd
  3. Mar 22, 2009 #2


    Staff: Mentor

    That would be a good start -- using definitions.
  4. Mar 23, 2009 #3
    ca=cb (mod m) means m divides (ca - cb), which implies that m divides c(a - b). If gcd(c,m) =1 then, m cannot divide c(because they are relatively prime to each other). logically, m will divide (a - b), i.e there an integer k such that mk = a - b, which iplies that a=b(mod m)

    2. If a=b(mod m), then there is an integer k such that a - b = km. suppose gcd(a, m) = n, then n divides a and n divides m. Thus a = ns and m = np, for some integers s and p.
    but a - b = km, implies ns - b = knp, implies b = n(s - kp) where s - kp is also an integer. This implies that n divides b. Similarly if gcd(b,m) = q, it is easy to show that q divides a. Thus logically, q = n since gcd(a,m) divides b and gcd(b,m) divides a, thus the gcd's must be the same
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook