Posted by **Michael** on Thursday, February 14, 2013 at 3:48am.

Prove that if ab = ac (mod n) and a is relatively prime to n, then b = c (mod n).

Proof: a and n are relatively prime and from ab = ac(mod n), we have n|(ab-ac), so n|a(b-c). Since (a,n)=1 (relatively prime), we get n(b-c). hence b=c(mod n).

But what if a and n are not relatively prime, can you still prove ab = ac (mod n)? Can you show a counterexample if I cannot be done? Thank you.

- Math (Proof) -
**Steve**, Thursday, February 14, 2013 at 4:24am
if not relatively prime, no proof.

2*3 (mod 8) = 2*7 (mod 8)

but not 3 = 7 (mod 8)

The primeness is vital. n can divide ab-ac of the products, but if a factor of n is also factor of a, then n need not divide b-c.

- Math (Proof) -
**Michael**, Thursday, February 14, 2013 at 5:32am
Thank you!

## Answer this Question

## Related Questions

- math - Which two is true as i'm confused A) 3+7 10 mod 15 17 + 9 4 mod 21 ...
- Math - Which Statements of congruence are true and which are false and why? 177 ...
- math - Which Statements of congruence are true and which are false and why? 177 ...
- Math - Which Statements of congruence are true and which are false and why? 177 ...
- Proofs and numbers - Prove the following theorem: Suppose p is a prime number, r...
- math - how do we find the least residue of 1789 (mod 4), (mod 10), (mod 101)
- math - how do we find the least residue of 1789 (mod 4), (mod 10), (mod 101)
- Math - What are the 3 solutions? I'm stuck! 6x=15(mod 21) a=6,m=21,b=15 d=gcd(6,...
- Discrete Math - Let a, b, c, and d be integers, and let n be a positive integer...
- probability - how do we find the least residue of 1789 (mod 4), (mod 10), (mod ...

More Related Questions