# Need help proving a congruence statement

• Mar 19th 2011, 04:53 PM
s3a
Need help proving a congruence statement
*Sorry if this isn't the correct section. I'm not too sure about the naming of topics and my course is simply called "Discrete Mathematics" and I got an infraction last time for posting in this thread that's why I'm saying.*

Ok so the question is: "Is it true that for all natural numbers n, if ab ≡ ac (mod n), then b ≡ c (mod n). Justify your answer."

My friend wrote something which I agree with quite a lot but do not fully understand everything.

So, everything that is simply written is what I agree with while the stuff marked with "*[a number]" is stuff I still question or have trouble with.

Hypothesis:
ab ≡ ac (mod n) ∀n ∈ ℕ [*1]
a ≡ a (mod n) [*2]

Conclusion:
b ≡ c (mod n)
ab ≡ ac (mod n) ⇔ ab - ac = nq, q ∈ ℤ
ab ≡ ac (mod n) ⇔ a(b-c) = nq

a ≡ a (mod n) ⇔ a - a = ns, s ∈ ℤ [*3]
a ≡ a (mod n) ⇔ a(1-1) = ns where s = 0 [*3]

[1] a(b-c) = nq ⇒ b - c = n ⇒ b ≡ c (mod n))
[2] a(b-c) = nq if a = 0 ⇒ TRUE

I put [*1] because my teacher said that "that is not always true". Is he right? If so, can someone please elaborate? For [*2], how do we know that? For [*3], I don't see the relevance of that step in the grand scheme of things.

Any help would be GREATLY appreciated!