# Why can I cancel in modular arithmetic?

Based on my school, the cancellation law for modular arithmetic is as stated:

For all integers $$a$$, $$b$$, $$c$$, $$n$$, with $$n > 1$$ and $$a$$ and $$n$$ are coprime, if $$ab$$ $$≡ ac$$( $$mod$$ $$n$$), then $$b ≡ c$$ ( $$mod$$ $$n$$ ).

Apparently, the proof for this was to multiply both sides by $$a$$-1.

2 questions then stem from this:

1) If you do modular multiplication, shouldn't you multiply the modulus as well?

If $$a \equiv b \mod n$$, then $$ma\equiv mb \mod {nm}$$. Why isn't this happening when $$a$$-1 is multiplied on both sides,i.e. I don't see a $$a$$-1 in the modulus?

2)Isn't multiplicative inverse of modulo $$n$$ such that $$a$$-1$$a$$$$1$$ ( $$mod$$ $$n$$) (ie must be congruent to 1 modulo n)?

$$\boxed{\text{Solve the equation 5 x+13 y=75 for integers x, y\quad }}$$

Such an equation is called a $$\color{red}{\text{Diophantine equation}}$$.

1. Re-write: $$5 x=75-13 y$$
2. Then $$5 x \equiv 75(\bmod 13),$$ by Theorem $$8.4 .1$$ (Epp)
3. Re-write: $$5 x \equiv 5 \cdot 15(\bmod 13)$$
4. Note that 5 and 13 are coprime.
5. Thus, $$x \equiv 15(\bmod 13),$$ by Theorem $$8.4 .9$$ (Epp)
6. Thus, $$x \equiv 2(\bmod 13),$$ because 15 mod $$13=2$$
7. So $$x=2$$ is a solution.
8. Substituting back into the equation: $$5(2)+13 y=75$$
9. And thus $$y=5$$

(Transcribed from this image)

As you can see, on line 5, when they multiply both sides by $$5$$-1, its not congruent to 1 modulo 13?

PS:

I looked up on this possible duplicate: Why can I cancel in modular arithmetic when working modulus a prime number? but didn't seem to understand both the poster and the answerer.

• In $b\equiv c\mod n$ ... , it should be $b\equiv c\mod m$. In this case, it is not difficult to show the implication. The other direction is more difficult. Commented Jun 5, 2020 at 8:57
• there are a number of answers in the duplicate. Can you point to where you dont understand in the elementary one? Commented Jun 5, 2020 at 8:58
• @CalvinKhor If possible, I would like to understand the 1st answer
– Leon
Commented Jun 5, 2020 at 9:02
• @Peter are you referring to the blockquote?
– Leon
Commented Jun 5, 2020 at 9:03
• No, to this : If b≡c ( mod n ), then na≡nb (mod nm). Why isn't this happening when a-1 is multiplied on both sides,ie I don't see a a-1 in the modulus? Commented Jun 5, 2020 at 9:04

Multiplying both sides of a modular equation without changing the modulus is valid, and if two numbers are equivalent modulo $$pq$$, they're certainly equivalent modulo $$p$$. (It's division that's a little more iffy.)

In this case, multiplying by $$a^{-1}$$ isn't necessary (although it does work, with some justification). A better way to do this is to observe that $$ab \equiv ac \pmod n$$ implies $$a(b-c) = ab - ac \equiv 0 \pmod n,$$ which means that $$n|a(b-c)$$. Since $$n$$ and $$a$$ are coprime, this then means $$n|b-c$$, or in other words, $$b \equiv c \pmod n$$.

For your second question, $$a a^{-1}$$ being $$1$$ modulo $$n$$ doesn't mean that multiplying anything with an $$a^{-1}$$ yields $$1$$ mod $$n$$. The inverse of $$5$$ is $$8$$; you can check easily that $$5 \times 8 \equiv 1 \pmod {13}$$, and that multiplying $$8$$ on both sides in line 3 yields line 5.

• The alternative explanation was nice!
– Leon
Commented Jun 5, 2020 at 9:29

If $$a\equiv b \mod n$$, then we can write $$a=b+kn$$ for some $$k\in\mathbb{Z}$$.

So multiplying by $$m$$ say gives $$am=bm+knm$$, which can be written as $$am\equiv bm \mod mn$$, but also as $$am\equiv bm \mod n$$, with $$km$$ as the 'new' $$k$$.

$$a^{-1}$$ exists as $$\gcd(a,n)=1$$, and is an integer between $$1$$ and $$n-1$$, and doesn't appear in the modulus for the reason given above.

For part 2, $$5^{-1}\cdot 5\equiv 1 \mod {13}$$, and

$$5x\equiv 5\cdot15 \mod {13}$$ $$5^{-1}\cdot 5x\equiv 5^{-1}\cdot 5\cdot15 \mod {13}$$ $$x\equiv 15 \mod {13}$$

• For part 2) , are you saying that, multiplying by its inverse does guarantee a congruency to 1 modulo n. Its just the $x$ causing my confusion that makes it a congruency to 2 modulo n instead?
– Leon
Commented Jun 5, 2020 at 9:27
• @Leon; the inverse is multiplied on line 3, and only affects the $5$ and not $x$.
– JMP
Commented Jun 5, 2020 at 9:44

Hint: In a commutative ring $$R$$, $$ab=ac$$ implies $$b=c$$ if $$a\ne0$$ is not a zero divisor. It’s not necessary that $$a$$ is a unit.

Indeed, if $$ab=ac$$, then $$a(b-c)=0$$. Since $$a$$ is not a zero divisor, then $$b-c=0$$ and hence $$b=c$$.

In the ring $$Z_n$$, each nonzero element is a zero divisor or a unit. So this is a special case.

• Sorry, I haven't learnt this topic "rings"
– Leon
Commented Jun 5, 2020 at 9:00
• Just think about $Z_n$. Commented Jun 5, 2020 at 9:37

Recall that $$ab=ac$$ mod $$n$$ iff there is some integer $$k$$ such that $$a(b-c)=kn$$. In particular $$a$$ is a divisor of the product $$kn$$. Now you use the coprime assumption: none of the prime factors of $$a$$ divide $$n$$, so all of them must divide $$k$$; so $$a$$ divides $$k$$, which is to say $$k/a=j$$ is some integer $$j\in\mathbb Z$$. Thus $$b-c = (k/a) n = jn$$ so $$b=c$$ mod $$n$$.