8

This post is to clear some of the doubts related to modulo arithmetic.

Addition on both sides

$a \equiv b \pmod p \iff$ $(a+k) \equiv (b+k) \pmod p$

Subtraction on both sides

$a \equiv b \pmod p \iff$ $(a-k) \equiv (b-k) \pmod p$

Multiplication on both sides

$a \equiv b \pmod p \iff$ $ak \equiv bk \pmod p$

But for division,

$a \equiv b \pmod p \iff$ $a/k \equiv b/k \pmod {p/k}$
(if $a/k, b/k$ and $p/k$ are integers)

Is my understanding right on this? Is there an alternate form exists for division or why the general form is different for division? Please help me to understand this.

ᴇɴᴅᴇʀᴍᴀɴ
  • 143
Kiran
  • 4,198
  • Is this covered in discrete mathematics book? I did not see those properties in DM book before. – Avv Mar 18 '21 at 20:10

2 Answers2

3

Try some numbers for division and see if you can see why. 20 = 8 mod 12 so 10 = 4 mod 12. why does that not work?

Note $a = b \mod n$ means $a = m*n + b$ so $a/k = (m*n)/k + b/k$ assuming $k|a; k|m*n; k|b$. Well, we want to say that means $a/k = (m/k)*n + b/k$. But what if $k \not \mid m$ but $k | nm$

That's what happens with $20 = 1*12 + 8$ and $20/2 = 1*12/2 = 8/2$. $2 \not \mid 1$ so instead we get $20/2 = 12/2 + 8/2$ so $10 = 6 + 4$ so $10 \equiv 4 \mod 6$ and not $10 \equiv 4 \mod 12$.

So division is more complicated. Is does work sometimes and sometimes it doesn't.

For example $24 \equiv 4 \mod 5$ and $12 \equiv 2 \mod 5$. In this case $\gcd(5,2) = 1$ so if $2|24$ and $2|4$ then $2\not \mid 5$ so if $24 = 5*k + 4$ then $\gcd(2,5) = 1$ so $2|k$ so we do get $12 = 5*(k/2) + 2$.

fleablood
  • 124,253
1

Your understanding on the first three definitions is OK, but in the last you should have $\frac{p}{\gcd(p,k)}$ in the modulo, as $p$ might not be divisible by $k$. Also $a$ and $b$ must be divisible by $k$, otherwise we have to be sure that $k$ is invertible modulo $p$, which acutally reduces to multiplication by the inverse.

To see why it's true recall that $a \equiv b \pmod p \iff p \mid a-b$. So if $a=ka', b=kb'$ then $p \mid k(a'-b')$. From this we can be sure that the $a'-b'$ is still divisible by the factors of $p$, but not of $k$.

Stefan4024
  • 35,843