Proving Algebraic Equivalence: GCDs & Modular Arithmetic

[guroten]

Homework Statement

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)

Homework Equations

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?

 

[Mark44]

That would be a good start -- using definitions.

 

[de_brook]

Homework Statement

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)

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