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.

📄️ ExponentiationSingle Page

📄️ InverseSingle Page