Introduction to Modulo Arithmetic

Hi everyone. In this post, we will learn about modulo arithmetic and discuss
some rules.

Modular arithmetic is a system of arithmetic for integers, which consists of remainders.
Consider the following expression:
$a = qn + r \quad | \quad 0 \le r \lt a$

$\therefore\:, \;\; a \equiv r \;\; (mod \;\; n)$
For example,
$13 \equiv 21 \;\; (mod \;\; 2)$
as
$13 = 1 \;\; (mod \;\; 2)$
and
$21 = 1 \;\; (mod \;\; 2)$

Note: $\equiv$ is not the same as $=$

Addition properties

• If $a + b = c$, then $a\;($mod $N)$ $+$ $b\;($mod $N)$ $\equiv$ $c\;($mod $N)$.
• If $a \equiv b \;($mod $N)$, then $a + k \equiv b + k \;($mod $N)$ for any integer $k$.
• If $a \equiv b \;($mod $N)$ and $c \equiv d \;($mod $N)$, then $a + c \equiv b + d \;($mod $N)$.
• If $a \equiv b \;($mod $N)$, then $-a \equiv -b \;($mod $N)$.

Multiplication properties

• If $a \cdot b = c$, then $a\;($mod $N)$ $\cdot$ $b\;($mod $N)$ $\equiv$ $c\;($mod $N)$.
• If $a \equiv b \;($mod $N)$, then $ka \equiv kb \;($mod $N)$ for any integer, $k$.
• If $a \equiv b \;($mod $N)$ and $c \equiv d \;($mod $N)$, then $ac \equiv bd \;($mod $N)$.

Exponentiation property

If $a \equiv b \;($mod $N)$, then $a^k \equiv b^k \;($mod $N)$, for any positive integer, $k$.

Division property

If gcd$(k, N) = 1$, and $ka \equiv kb\;($mod $N)$, then $a \equiv b\;($mod $N)$.

You can’t just divide both sides, unless the above property is true.

Modular inverse

If $a$ and $N$ are integers such that gcd$(a, N) = 1$, then there exists an integer,
$x$, such that $ax \equiv 1 \;($mod $N)$.