# 2 short proofs

1. Mar 22, 2009

### guroten

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. Mar 22, 2009

### Staff: Mentor

That would be a good start -- using definitions.

3. Mar 23, 2009

### de_brook

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