That is true only when gcd(a,n)=1.
Try to prove this:
If ab ≡ ac (mod n) then b ≡ c (mod n/d), when d=gcd(a,n)
(The conclusion from here is my first line in this post).
*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!
Thanks in advance!