Number operations

Denote by $[m] = \{0,1,\ldots, m\}$. Recall the notation $a \mid b$ "$a$ divides $b$", meaning $(\exists k \in {\mathbb Z}) b = a k$. Also, the congruent notation $a \equiv b \pmod{m}$ ("$a$ is congruent to $b$ modulo $m$"), which means $m \mid (a-b)$. Modular arithmetic deals with relations under this modulo notation. Another name for modular arithmetic is "calendar arithmetic", e.g., $36 \equiv 1 \pmod{7}$ implies that, if today is Sunday, then $36$ days from now will be Monday.

Exercise 42

Prove that $\equiv$ under modulo $q$ is an equivalence relation.

Exercise 43

If $a \equiv c \pmod{m}$ and $b \equiv d \pmod{m}$, then $a + b \equiv c+d \pmod{m}$ and $ab \equiv cd \pmod{m}$

The above exercise allows us to have an easier time working in modular arithmetic. For instance, if we want to find the last digit of number $11^{100}$, we could simply write $11 \equiv 1 \pmod{10}$ and then we can raise both sides to the power of $100$, which gives us $11^{100} \equiv 1 \pmod{10}$. The last digit of this number is $1$!

Exercise 44

What is the last digit of $999^{10001}$? Prove your answer.

📄️ Exponentiation

Now we may ask ourselves: How fast can we do these modular arithmetic operations? When we multiply two $n$-digit numbers, it is easy to see that a school multiplication method would give us $O(n^2)$ bit operations.

📄️ Inverse

The next operation we want to discuss is the inverse operation. The inverse of addition is subtraction, which can be done easily. But the concept of multiplicative inverse in modular arithmetic is less clear (for real numbers, the inverse of $x$ is simply $1/x$).