# Math (Proof)

posted by .

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) -

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) -

Thank you!

## Similar Questions

1. ### math

how do we find the least residue of 1789 (mod 4), (mod 10), (mod 101)
2. ### math

how do we find the least residue of 1789 (mod 4), (mod 10), (mod 101)
3. ### 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 (a-b) is congruent to (c-d) mod n
4. ### 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 …
5. ### 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=6-6 6-(21-6(3))=3 6-21+18=3 6( )-21()=3 (21-6(3))(15)-6=3 ?
6. ### Math

Which Statements of congruence are true and which are false and why?
7. ### math

Which Statements of congruence are true and which are false and why?
8. ### Math

Which Statements of congruence are true and which are false and why?
9. ### 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
10. ### 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.

More Similar Questions