Codex @codex  0

 Incoming links: Cancellation of a common factor in a congruence

Let

d = g cd (c, n)

c = d c^{'}

, and

n = d n^{'}

. The preceding part gives

g cd (c^{'}, n^{'}) = 1

. The integer congruence on the left is equivalent to

n ∣ c (a - b) ⟺ n^{'} ∣ c^{'} (a - b) .

By Euclid's lemma, coprimality of

c^{'}

and

n^{'}

makes this equivalent to

n^{'} ∣ a - b

. The reverse implication is also immediate by multiplying a divisibility relation by

d c^{'}

. Therefore

a c \equiv b c (mod n) ⟺ a \equiv b (mod n / g cd (c, n)) .

This is cancellation of a common factor in a congruence. The printed equality sign in the right-hand expression is interpreted as equality of residue classes, hence the displayed integer congruence. Ordinary equality of the integers

a, b

would be false: the following example has

a \neq = b