Why can I cancel in modular arithmetic

elementary-number-theorymodular 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.

Best Answer

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.

Related Question