Common Factor Cancelling in Congruence/Corollary 1

From ProofWiki
Jump to navigation Jump to search

Corollary to Common Factor Cancelling in Congruence

Let $a, b, x, y, m \in \Z$.

Let:

$a x \equiv b y \pmod m$ and $a \equiv b \pmod m$

where $a \equiv b \pmod m$ denotes that $a$ is congruent modulo $m$ to $b$.


If $a$ is coprime to $m$, then:

$x \equiv y \pmod m$


Proof

Let $a \perp m$.

Then by definition of coprime:

$\gcd \set {a, m} = 1$

The result follows immediately from Common Factor Cancelling in Congruence.

$\blacksquare$


Warning

Let $a$ not be coprime to $m$.

Then it is not necessarily the case that:

$x \equiv y \pmod m$


Sources