Logic for invalid division in congruence arithmetic when $(divisor, modulus)\ne 1$.

Question

Have found that in congruence arithmetic, division will not work unless the above condition is met.

A usual proof is given below, & want to algebraically find out the significance of the given condition:

Let $\exists m \in \mathbb{Z+}, \exists a, b,c \in \mathbb{Z}$. If $ac\equiv bc \pmod {m}$ and $(c, m)=1$, then $a\equiv b \pmod {m}$.

Proof. Because $ac \equiv bc \pmod {m}, m \mid (ac - bc) = c(a - b)$. As $(c, m)= 1$, so $m \mid (a- b)$. So, $a \equiv b \pmod m$.

My incomplete reasoning is:
If $(c,m)\ne1$, then there would be prime factors in common to $c,m$, let $p_1^1$. If so, then $c=p_1k, m = p_1l, (k,l)=1$.
Then $p_1k \mid ap_1k \equiv bp_1k \pmod {p_1l} \implies a-b\pmod{{l\over k}}$.

I want to correlate this reasoning to the invalid division example:
$2\mid 14 \equiv 8 \pmod 6 \implies 7 \equiv 4 \pmod 6$.

On comparing, I see that my reasoning falters, where it divides the modulus too. There is no division possible for modulus, as it just forms the equivalence class and declares that the given two quantities ($a,b$) lie in the same equivalence class. Suppose, as a hypothetical case if the modulus is also divided, then no issues and leads to correct division. In the example above also, that hypothetical division would lead to $7 \equiv 4 \pmod 3.$

Edit Have found that my so-called 'hypothetical division' is not so hypothetical at all. In fact, it is completely valid, if the point of view is changed to see the modulus as another number (i.e., apart from $a$) in the linear combination of the form $ac-my = bc \implies ap_1kx - p_1ly = bc.$ This view is used in the solution of congruence equations when $(c,m)\ne 1$, as stated by Beachy, here and also here (in Theorem 1.3.5), among other places.

Answer 1

You can generalize to this:

Proposition: $ac \equiv bc \mod n \implies a \equiv b \mod \frac n{\gcd(n,c)}$

This will allow you to do what you wish:

$14 \equiv 32 \mod 9 \implies 7\equiv 16 \mod 9$ which is true.

Likewise $14\equiv 8 \mod 6\implies 7\equiv 4 \mod 3$ is also true although $7\not \equiv 4 \mod 6$ (obviously).

Proof:

Case 1: $\gcd(c,n) = 1$ then.... cut and paste ....

"Proof. Because $ac≡bc(\mod n),n∣(ac−bc)=c(a−b)$. As $(c,n)=1$, so $n∣(a−b)$. So, $a≡b(\mod n)$."

Case 2: $\gcd(c,n) = d > 0$.

Let $c = c'd$ and $n = n'd$. Then $\gcd(c',n')=1 $. (because $\gcd(c',n')*d$ is a common divisor of both $c,n$ so $\gcd(c',n')*d \le d = \gcd(c,n)$.)

$ac \equiv bc \mod n \implies$

$ac = bc + kn$

$ac'd = dc'd + kdn'$

$ac' = dc' + kn'$

$ac' \equiv bc' \mod n' =\frac{n}{\gcd(c,n)} $

And as $\gcd(c', n') = 1$ then

$a \equiv b \mod \frac n{\gcd(c,n)}$ by Case 1:

..... or .... if you like.

$ac \equiv bc \mod n$ means

$n|ac -bc = c(a-b)$ and so

$\frac n{\gcd(n,c)}|\frac c{\gcd(n,c)}(a-b)$.

As $\frac n{\gcd(n,c)}$ and $\frac c{\gcd(n,c)}$ must be coprime, that means

$\frac n{\gcd(n,c)}|(a-b)$

So $a \equiv b \mod \frac n{\gcd(n,c)}$.

Answer 2

The condition $\gcd(c,m)=1$ is illuminated if you see the congruence classes modulo $m$ as the ring $\mathbf Z/m\mathbf Z$:

That $c$ and $m$ are primes is equivalent to a Bézout's relation: $uc+vm=1$ for some $u,v\in\mathbf Z$. This relation means, in terms of congruences that $\; uc\equiv 1 \mod m$, in other words, $c$ is a unit in the ring $\mathbf Z/m\mathbf Z$, and as in any ring, we have the cancellation law for units: $$ac\equiv bc\implies acu\equiv bcu \iff a\cdot 1\:(=a)\equiv b\cdot 1 \:(=b)\mod m. $$

• If $\gcd(c,m)=d>1$, $c$ is a zero-divisor in the ring $\mathbf Z/m\mathbf Z$, and we cannot simplify by $c$ any more.Let $c'=\dfrac cd$, $m'=\dfrac md$. It is easily checked that $$ac\equiv bc \mod m\iff ac'\equiv bc'\mod m'\iff a\equiv b\mod m'. $$ Furthermore, since $\gcd(c',m')=1$, this means by the previous case that $$ac'\equiv bc'\mod m'\iff a\equiv b\mod m'. $$
• To sum it up: $$ ac\equiv bc \mod m \iff a\equiv b\mod\biggl(\frac m{\gcd(c,m)}\biggr). $$