# Cancellability of Congruences/Corollary 1

Jump to navigation
Jump to search

## 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$

where $\equiv$ denotes congruence.

## Proof 1

Recall that $c \perp n$ means $\gcd \set {c, n} = 1$.

The result follows directly from Cancellability of Congruences.

$\blacksquare$

## Proof 2

We are given that $c$ and $n$ are coprime.

So:

\(\ds \exists x, y \in \Z: \, \) | \(\ds c x + n y\) | \(=\) | \(\ds 1\) | Integer Combination of Coprime Integers | ||||||||||

\(\ds \leadsto \ \ \) | \(\ds 1 - cx\) | \(=\) | \(\ds y n\) | |||||||||||

\(\text {(1)}: \quad\) | \(\ds c x\) | \(\equiv\) | \(\ds 1\) | \(\ds \pmod n\) | Definition of Congruence |

Then:

\(\ds a\) | \(\equiv\) | \(\ds a\) | \(\ds \pmod n\) | Equal Numbers are Congruent | ||||||||||

\(\text {(2)}: \quad\) | \(\ds \leadsto \ \ \) | \(\ds a c x\) | \(\equiv\) | \(\ds a\) | \(\ds \pmod n\) | Modulo Multiplication is Well-Defined and from $(1)$ | ||||||||

\(\ds b\) | \(\equiv\) | \(\ds b\) | \(\ds \pmod n\) | Equal Numbers are Congruent | ||||||||||

\(\text {(3)}: \quad\) | \(\ds \leadsto \ \ \) | \(\ds b c x\) | \(\equiv\) | \(\ds b\) | \(\ds \pmod n\) | Modulo Multiplication is Well-Defined and from $(1)$ | ||||||||

\(\text {(4)}: \quad\) | \(\ds x c a\) | \(\equiv\) | \(\ds x c b\) | \(\ds \pmod n\) | Modulo Multiplication is Well-Defined and from $c a \equiv c b \pmod n$ |

Thus:

\(\ds a\) | \(\equiv\) | \(\ds a c x\) | \(\ds \pmod n\) | from $(2)$ above | ||||||||||

\(\ds \) | \(\equiv\) | \(\ds b c x\) | \(\ds \pmod n\) | from $(4)$ above | ||||||||||

\(\ds \) | \(\equiv\) | \(\ds b\) | \(\ds \pmod n\) | from $(3)$ above |

$\blacksquare$

## Proof 3

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$