# Modular arithmetic

## Definition

$a \equiv b \mod m :\Leftrightarrow \exists k \in \mathbb{Z} : a - b = k \cdot m$

## Basic properties

### Addition and multiplication

\left.\begin{aligned} a &\equiv b \mod m \\ c &\equiv d \mod m \end{aligned}\right\rbrace \Rightarrow \left\lbrace\begin{aligned} a + c &\equiv b + d \mod m \\ a - c &\equiv b - d \mod m \\ a \cdot c &\equiv b \cdot d \mod m \end{aligned}\right.

#### Proof

By definition, $a - b = k_1 \cdot m \\ c - d = k_2 \cdot m$

Therefore:

(1): $a - b + c - d = k_1 m + k_2 m$ reordered gives $(a + c) - (b + d) = (k_1 + k_2)m$.

(2): Follows trivially from (1)

(3): $ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d) = c k_1 m + b k_2 m = (c k_1 + b k_2)m$

### Powers

$a \equiv b \mod m \Rightarrow \forall k \in \mathbb{N} : a^k \equiv b ^k \mod m$

#### Proof

\begin{aligned} a \equiv b \mod m \\ a \equiv b \mod m \end{aligned}

implies $a^2 \equiv b^2 \mod m$. For greater exponents the statement is true by induction.

### Combination with different moduli

x \equiv a \mod n_1 n_2 \Rightarrow \left\lbrace\begin{aligned} x &\equiv a \mod n_1 \\ x &\equiv a \mod n_2 \end{aligned}\right.

If $\gcd(n_1, n_2) = 1$, then the converse also holds: \left.\begin{aligned} x &\equiv a \mod n_1 \\ x &\equiv a \mod n_2 \end{aligned}\right\rbrace \Rightarrow x \equiv a \mod n_1 n_2

## General simultaneous congruences

It holds, that \left.\begin{aligned} x &\equiv a_1 \mod n_1 \\ x &\equiv a_2 \mod n_2 \\ L &\neq \varnothing \end{aligned}\right\rbrace \Leftrightarrow \left\lbrace\begin{aligned} a_1 &\equiv a_2 \mod \gcd(n_1, n_2) \\ x_1 &\equiv x_2 \mod \lcm(n_1, n_2) \quad\forall x_1,x_2 \in L \end{aligned}\right.

where $L$ is the solution set.

### Proof

($\Rightarrow$): First, we prove that $a_1$ must be equivalent to $a_2$ modulo $\gcd(n_1, n_2)$: \begin{aligned} \left\lbrace\begin{aligned} x &\equiv a_1 \mod n_1 \\ x &\equiv a_2 \mod n_2 \end{aligned}\right. &\Rightarrow \left\lbrace\begin{aligned} x - a_1 &\equiv 0 \mod n_1 \\ x - a_2 &\equiv 0 \mod n_2 \end{aligned}\right. \\ &\Rightarrow \left\lbrace\begin{aligned} x - a_1 &\equiv 0 \mod \gcd(n_1, n_2) \\ x - a_2 &\equiv 0 \mod \gcd(n_1, n_2) \end{aligned}\right. \\ &\Rightarrow x - a_1 - x + a_2 \equiv 0 \mod \gcd(n_1, n_2) \\ &\Rightarrow a_2 - a_1 \equiv 0 \mod \gcd(n_1, n_2) \\ &\Rightarrow a_1 \equiv a_2 \mod \gcd(n_1, n_2) \end{aligned}

The set of solutions $L$ is defined modulo $\lcm(n_1, n_2)$, because given $x_1, x_2 \in L \neq \varnothing$ it follows, that \begin{aligned} x_1 &= a_1 + k_1 \cdot n_1 \\ x_1 &= a_2 + k_2 \cdot n_2 \\ x_2 &= a_1 + k_3 \cdot n_1 \\ x_2 &= a_2 + k_4 \cdot n_2 \end{aligned}

where $k_1, k_2, k_3, k_4 \in \mathbb{Z}$. By subtracting the third row from the first one and the fourth row from the second one we get: \begin{aligned} x_1 - x_2 &= a_1 + k_1\cdot n_1 - a_1 - k_3 \cdot n_1 = (k_1 - k_3) \cdot n_1 \\ x_1 - x_2 &= a_2 + k_2 \cdot n_2 - a_2 - k_4 \cdot n_2 = (k_2 - k_4) \cdot n_2 \end{aligned}

So $x_1 - x_2$ must be a multiple of both $n_1$ and $n_2$ and therefore: $x_1 - x_2 \equiv 0 \mod \lcm(n_1, n_2)$

($\Leftarrow$): By assumption, we know that for some $k \in \mathbb{Z}$ $a_1 - a_2 = k \cdot \gcd(n_1, n_2)$

Also, as stated in the Bézout Lemma, we can write the greatest common divisor as a linear combination: $\gcd(n_1, n_2) := u \cdot n_1 + v \cdot n_2$

By replacing $\gcd(n_1, n_2)$ with the linear combination we get: $a_1 - a_2 = k \cdot u \cdot n_1 + k \cdot v \cdot n_2$

Thus, $\underbrace{a_1 - k \cdot u \cdot n_1}_{\equiv a_1 \bmod n_1} = \underbrace{a_2 + k \cdot v \cdot n_2}_{\equiv a_2 \bmod n_2}$

Assuming the solution is defined modulo $\lcm(n_1, n_2)$, it follows that: $x \equiv a_1 - k \cdot u \cdot n_1 \equiv a_2 + k \cdot v \cdot n_2 \mod \lcm(n_1, n_2)$