3
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ Commented Jun 5, 2020 at 8:57
  • $\begingroup$ there are a number of answers in the duplicate. Can you point to where you dont understand in the elementary one? $\endgroup$ Commented Jun 5, 2020 at 8:58
  • $\begingroup$ @CalvinKhor If possible, I would like to understand the 1st answer $\endgroup$ Commented Jun 5, 2020 at 9:02
  • $\begingroup$ @Peter are you referring to the blockquote? $\endgroup$ Commented Jun 5, 2020 at 9:03
  • $\begingroup$ 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? $\endgroup$ Commented Jun 5, 2020 at 9:04

4 Answers 4

Reset to default
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The alternative explanation was nice! $\endgroup$ Commented Jun 5, 2020 at 9:29
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Commented Jun 5, 2020 at 9:27
  • $\begingroup$ @Leon; the inverse is multiplied on line 3, and only affects the $5$ and not $x$. $\endgroup$ Commented Jun 5, 2020 at 9:44
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Sorry, I haven't learnt this topic "rings" $\endgroup$ Commented Jun 5, 2020 at 9:00
  • $\begingroup$ Just think about $Z_n$. $\endgroup$ Commented Jun 5, 2020 at 9:37
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.