Common Factor Cancelling in Congruence/Corollary 1
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
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory: Law $\text{B}$
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $20$