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$
  • $\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$ – Peter Jun 5 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$ – Calvin Khor Jun 5 at 8:58
  • $\begingroup$ @CalvinKhor If possible, I would like to understand the 1st answer $\endgroup$ – Leon Jun 5 at 9:02
  • $\begingroup$ @Peter are you referring to the blockquote? $\endgroup$ – Leon Jun 5 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$ – Peter Jun 5 at 9:04
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}$$

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Leon Jun 5 at 9:27
  • $\begingroup$ @Leon; the inverse is multiplied on line 3, and only affects the $5$ and not $x$. $\endgroup$ – JMP Jun 5 at 9:44
3
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The alternative explanation was nice! $\endgroup$ – Leon Jun 5 at 9:29
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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry, I haven't learnt this topic "rings" $\endgroup$ – Leon Jun 5 at 9:00
  • $\begingroup$ Just think about $Z_n$. $\endgroup$ – Wuestenfux Jun 5 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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.