Math (Proof)
posted by Michael .
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.
Respond to this Question
Similar Questions

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) 
Discrete Math
Let a, b, c, and d be integers, and let n be a positive integer. Prove that if a is congruent to c mod n and b is congruent to d mod n, then (ab) is congruent to (cd) mod n 
math
Which two is true as i'm confused A) 3+7 ß 10 mod 15 17 + 9 ß 4 mod 21 12 + 14 ß 0 mod 26 B) 4+11 ß 2 mod 13 9+7 ß 4 mod 12 13 + 13 ß 1 mod 25 C) 5+9 ß 4 mod 10 16 + 13 ß 3 mod 26 12 + 7 ß 6 mod 14 d)2+7 … 
Math
What are the 3 solutions? I'm stuck! 6x=15(mod 21) a=6,m=21,b=15 d=gcd(6,21)=3 solns. 6x=15(mod 21) 2x=5(mod 7) 21=6(3)+3 6+3(2)+0 0=66 6(216(3))=3 621+18=3 6( )21()=3 (216(3))(15)6=3 ? 
Math
Which Statements of congruence are true and which are false and why? 
math
Which Statements of congruence are true and which are false and why? 
Math
Which Statements of congruence are true and which are false and why? 
Proofs and numbers
Prove the following theorem: Suppose p is a prime number, r, s are positive integers and x is an arbitrary integer. Then we have x^r identical to x^s (mod p) whenever r is identical to s (mod 11).for x belongs to an integer 
Math
Find all numbers $r$ for which the system of congruences: x == r mod 6 x == 9 mod 20 x == 4 mod 45 has a solution.