# Cancellability of Congruences/Corollary 1/Proof 3

## Corollary to Cancellability of Congruences

Let $c$ and $n$ be coprime integers, that is:

$c \perp n$

Then:

$c a \equiv c b \pmod n \implies a \equiv b \pmod n$

## Proof

Let:

$c a \equiv c b \pmod n$

Then by definition of congruence:

$n \divides k \paren {x - y}$

We have that:

$c \perp n$

Thus by Euclid's Lemma:

$n \divides \paren {x - y}$

So by definition of congruence:

$a \equiv b \pmod n$

$\blacksquare$