Cancellability of Congruences/Corollary 1

From ProofWiki
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$