Why can I cancel in modular arithmetic?

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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