Scaling and cancellation equivalence for congruence and divisibility

230 Views Asked by At

I'm quite new to modular arithmetic. Therefore, this question may be very silly. Sorry for this.

Suppose that I want to prove that: $$a \cdot b \equiv 0 \mod{c}.$$

If I know that

$$c \equiv 0 \mod{a},$$

then can I conclude that:

$$b \equiv 0 \mod{d} \Rightarrow a \cdot b \equiv 0 \mod{c},$$

where $c = a \cdot d$?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, it's simply $\ \bbox[5px,border:1px solid #c00]{ad\mid ab\iff d\mid b}\,\ $ by cancelling or scaling by $\,a\neq 0,\ $ i.e.

$\ \, \dfrac{ab}{ad} = \dfrac{b}d,\ $ so $\,\ ad\mid ab\iff \dfrac{ab}{ad}\in \Bbb Z\iff \dfrac{b}{d}\in\Bbb Z\iff d\mid b$

Alternatively, eliminating fractions and emphasizing an equational view

$$ ad\mid ab\iff \exists x\!:\, ad\,x = ab \iff \exists x\!:\, d\,x = b\iff d\mid b $$

i.e. equationally: $\ \,ad\,x = ab\,$ has an integer root $x\!\iff\! d\,x = b\, $ has an integer root $x$

with very easy proof: cancelling $\,a\neq 0\,$ yields $(\Rightarrow)$, and scaling by $\,a\,$ yields $(\Leftarrow)$.

i.e. the operation of "scaling by $a$" is invertible if $a$ is cancellable, so scaling by $a$ and cancelling $a$ yield equivalent equations (same set of roots), so these operations preserve solvability.

This preservation of equations is well known in the special case that $a$ is invertible (e.g. $\,a\neq 0\,$ in a field like $\,\Bbb Q,\Bbb R,\Bbb C)$ when we normalize polynomials to be monic (lead coef $=1$) by scaling by $a^{-1}$.

Alternatively it can be viewed as a special case of congruence scaling / division / cancellation when written in the language of congruences (vs. divisibility).