Homework Help: Math (Proof)

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

Geometry- how to write proof - ABC is a right triangle. Angle C is 90 degree. ...
math - write a 2 column proof, Given D is the midpoint of AC, E is the midpoint...
geometry - ABC IS a isoceles triangle in which AB=AC 'IF AB and AC are ...
math - in an isosceles triangle ABC ,AB=AC.if AB and AC are produced to D and E ...
math - in an isosceles triangle ABC ,AB=AC.if AB and AC are produced to D and E ...
geometry - write a 2 column proof, Given D is the midpoint of AC, E is the ...
Proofs and numbers - Prove the following theorem: Suppose p is a prime number, r...
geometry - 1)given-AB=CD,CD=EF prove-AB-EF (in 5 steps that show why it is ...
Writing a 2 column proof.. - I have no idea where to start! and I've got ...
math - Let ABC be a triangle such that angle ACB = 135 degrees. Prove that AB^2...

For Further Reading

First Name:
School Subject:
Answer: