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.
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.
Thank you!
If a and n are not relatively prime, it is not true that ab = ac (mod n) implies b = c (mod n). The statement only holds when a and n are relatively prime.
Here is a counterexample to demonstrate this:
Let's consider a = 2, n = 4, b = 3, and c = 1.
We have ab = 2 * 3 = 6 and ac = 2 * 1 = 2.
Now, let's check whether ab ≡ ac (mod n):
6 ≡ 2 (mod 4)
Indeed, ab is congruent to ac (mod n).
However, b ≡ 3 (mod 4) and c ≡ 1 (mod 4), which means that b and c are not congruent modulo n.
Therefore, the statement that ab = ac (mod n) implies b = c (mod n) is not true when a and n are not relatively prime.
If a and n are not relatively prime, it is not necessarily true that ab = ac (mod n). It is possible that ab and ac are congruent modulo n, even if b and c are not congruent modulo n. Let's consider a counterexample:
Let a = 2, b = 6, c = 9, and n = 4. Here, a and n are not relatively prime because they share a common factor of 2.
We have ab = 2 * 6 = 12, and ac = 2 * 9 = 18. Taking both modulo 4, we get:
12 (mod 4) = 0,
18 (mod 4) = 2.
Clearly, 0 is not congruent to 2 modulo 4, so ab is not equal to ac modulo 4.
This counterexample shows that if a and n are not relatively prime, the statement ab = ac (mod n) does not hold. The condition of being relatively prime is necessary for the conclusion to be true.