Post a New Question

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!

Answer This Question

First Name
School Subject
Your Answer

Related Questions

More Related Questions

Post a New Question