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

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.

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)}$.

• Thanks a lot, I feel that this approach can help in solving my unsolved post at : math.stackexchange.com/questions/2641265/… – jitender Feb 9 '18 at 19:09
• I feel your approach confuses somewhat (a beginner like me), when take your proof's line: $a\frac c{\gcd(c,n)} = b\frac c{\gcd(c,n)} + k \frac n{\gcd(c,n)}$. It does not show division by $c$. To show the same, there should be shown cancellation of the $\frac c{\gcd(c,n)}$ term from all $3$ terms. This step should lead to $a = n.\frac k{c} + b$. Once this occurs, it is back to the starting problem. – jitender Feb 9 '18 at 19:52
• Let $d = \gcd (c,n)>0$. Let $c = c'd$ and $n=n'd$. The $\gcd(c',n') =1$. then $ac = bc + kn$ means $adc' = bdc' + kdn'$ so $ac' =bc' + dn'$ so $ac'\equiv bc' \mod n'$. And $\gcd(c',n') = 1$ !!!!YOU!!! have proven in your post that if $\gcd(c', n') = 1$ then this means $a \equiv b \mod n'$. So we are done. – fleablood Feb 9 '18 at 21:57
• The $k$ factor does not encompasses $c$. The $k$ factor is completely irrelevant. It is the $n$ factors and the $c$ factor that both encompass the $\gcd(c,n)$ factor. What remains is then $c' = \frac c {\gcd(c,n)}$ and $n' = \frac c{\gcd(c,n)}$ are relatively prime to each other. So as $ac' \equiv bc' \mod n'$ and $\gcd(c', n') = 1$ then you know that $a\equiv b \mod n'$. – fleablood Feb 9 '18 at 22:01
• "(a beginner like me)"; naivite of the beginner can only account for so much. Eventually you will have to start figuring things out on your own. – fleablood Feb 9 '18 at 22:21

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).$$
• As I was discussing reasoning for the invalid case, so can you please extend your logic to describe the failure for non-units' case. Or is it that, the valid case is used by you to make a base from which to approach by contra-positive or by contradiction for the non-unit(s') case. – jitender Feb 9 '18 at 16:10
• @jitender: There's no contrapositive used in the general case, only a careful examination of what happens. I've added what can be said in this case, and gave a general conclusion. – Bernard Feb 9 '18 at 17:27
• Thanks for covering the general case, that covers both ways the congruence equation is handled. By both ways, I mean that the case when $(c,m)=1$ and $(c,m)\gt 1$. – jitender Feb 9 '18 at 17:37