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(abac), so na(bc). Since (a,n)=1 (relatively prime), we get n(bc). 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 abac of the products, but if a factor of n is also factor of a, then n need not divide bc.

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  Find all numbers $r$ for which the system of congruences: x == r mod 6 x...
 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...
More Related Questions