From this definition we can deduce a series of properties that are very useful: - $ a\equiv b \pmod m \Rightarrow a + n \equiv b + n \pmod m \hspace{1cm} \forall n \in \mathbb{Z}$ - $ a\equiv b \pmod m \Rightarrow a \cdot n \equiv b \cdot n \pmod m \hspace{1cm} \forall n \in \mathbb{Z}$ - $ a\equiv b \pmod m \Rightarrow a^n \equiv b^n \pmod m \hspace{1cm} \forall n \in \mathbb{Z^+}$ Let's prove the first one. We know from the definition that $a \equiv b \pmod m$, and we want to prove that $a + n \equiv b + n \pmod m$. Another way to see it is that we want to show $(a + n) - (b + n)$ is a multiple of $m$. After this operation, it is clear that this evaluates to $a-b$, which we know already is a multiple of $m$. Thus, modular addition preserves equivalence. For example, if $13 \equiv 3 \pmod 5$, then $13 + 1 \equiv 3 + 1 \pmod 5$. It can be seen that if both clocks point to the same time, if we again advance $n$ hours on each one, they will still point to the same time.

Similarly, for example, $4 \cdot 13\equiv 4 \cdot 3 \pmod 5$ or $13^4 \equiv 3^4 \pmod 5$. --- ***Exercise S.1.1.*** Prove that $ a\equiv b \pmod m \Rightarrow a \cdot n \equiv b \cdot n \pmod m$ for any integer $n$.

Solution.

In the same way as before, we want to see that $a \cdot n - b \cdot n$ is a multiple of $m$. In particular, $a \cdot n - b \cdot n = (a-b) \cdot n$ and since by hypothesis $a-b$ is a multiple of $m$, any multiple of $a-b$ will be as well. ▢

--- The third property is based on a notable product that states that: $$a^n-b^n= (a-b)(a^{n-1} + a^{n-2}b + a^{n-3}b^2+...+ab^{n-2}+b^{n-1}).$$ In particular, if $a-b$ is a multiple of $m$, then so is $a^n-b^n$ since, as we can see, $a-b$ is a factor of its decomposition. --- ***Exercise S.1.2.*** Calculate the last two digits of $43^{43}$.

Hint.

The last two digits are equivalent to calculating the remainder after dividing by 100, that is, $43^{43}$ modulo $100$.

Hint.

Try to calculate the first values of $43^n \pmod {100}$. What happens at $n = 4$?

Hint.

Remember the third property: $a\equiv b \pmod m \Rightarrow a^n \equiv b^n \pmod m$.

Solution.

Let's calculate the first values of $43^n \pmod {100}$: $$43^1 = 43 \pmod {100},$$ $$43^2 = 49 \pmod {100},$$ $$43^3 = 7 \pmod {100},$$ $$43^4 = 1 \pmod {100}.$$ We have just obtained that $43^4 = 1$, so now we can take advantage of $a\equiv b \pmod m \Rightarrow a^n \equiv b^n \pmod m$: $$43^{43} \equiv 43^343^{40} \equiv 43^3(43^4)^{10} \equiv 7 \cdot 1^{10} \equiv 7 \pmod {100}.$$

▢

Codercise S.1.1 - Modular equivalence

Codercise S.1.2 - The inverse in modular arithmetic

The notion of modular arithmetic

Properties of modular arithmetic

Inverse of a number