Modular Arithmetic#

Theorem: Division with Remainder

For any two integers $a, b \in \mathbb{Z}$ with $b \ne 0$, there exist integers $q, r \in \mathbb{Z}$ such that

\[ a = bq + r \]

with

\[ 0 \le r \lt |b| \]

Definition: Quotient

We call $q$ the quotient of the division of $a$ by $b$.

Definition: Remainder

We call $r$ the remainder of the division of $a$ by $b$.

Notation

We often write $r$ in the following way:

\[ a \bmod b \]

Proof

TODO

Theorem: Finding the Remainder

The remainder is always given by the following formula:

\[ a \bmod b = a - |b| \cdot \left\lfloor \frac{a}{|b|} \right\rfloor \]

Proof

TODO

Modular Congruence#

Definition: Modular Congruence

Let $a, b \in \mathbb{Z}$ and let $n \in \mathbb{Z} \setminus \{0\}$.

We say that $a$ and $b$ are congruent modulo $n$ if $n$ is a divisor of $a - b$:

\[ (a - b) \bmod n = 0 \]

Notation

\[ a \equiv b \mod n \qquad a \equiv b \pmod n \]

Modular Arithmetic#

Definition: Modular Addition

Let $a, b \in \mathbb{Z}$ and let $n \in \mathbb{N}$.

The addition of $a$ and $b$ modulo $n$ is defined as the remainder upon dividing $a + b$ by $n$:

\[ (a + b) \bmod n \]

Notation

\[ a \oplus_n b \]

Theorem: Simplifying Modular Addition

Addition modulo $n$ has the following property:

\[ a \oplus_n b = ((a \bmod n) + (b \bmod n)) \bmod n \]

Proof

The following proof was generated by AI and has not been human-verified. As such, it may contain mistakes.

By definition, the left-hand side (LHS) is:
$$
a \oplus_n b = (a + b) \bmod n
$$

We want to prove that this is equal to the right-hand side (RHS):
$$
((a \bmod n) + (b \bmod n)) \bmod n
$$

We can express $a$ and $b$ in terms of their quotients and remainders when divided by $n$.

Let:

$a = q_a n + r_a$, where $q_a$ is an integer and $r_a = a \bmod n$ (with $0 \le r_a < n$).
$b = q_b n + r_b$, where $q_b$ is an integer and $r_b = b \bmod n$ (with $0 \le r_b < n$).

Now, let's analyze the LHS by substituting these expressions:

\[ \begin{aligned} (a + b) \bmod n &= ((q_a n + r_a) + (q_b n + r_b)) \bmod n \\ &= (q_a n + q_b n + r_a + r_b) \bmod n \\ &= ((q_a + q_b)n + (r_a + r_b)) \bmod n \end{aligned} \]

The term $(q_a + q_b)n$ is an integer multiple of $n$, so it does not affect the remainder when the entire sum is divided by $n$. Therefore, the expression simplifies to:

\[ \text{LHS} = (r_a + r_b) \bmod n \]

Next, let's analyze the RHS by substituting the definitions of $r_a$ and $r_b$:

\[ \begin{aligned} ((a \bmod n) + (b \bmod n)) \bmod n &= (r_a + r_b) \bmod n \\ \text{RHS} &= (r_a + r_b) \bmod n \end{aligned} \]

Since both the LHS and RHS simplify to the same expression, $(r_a + r_b) \bmod n$, they are equal.

\[ (a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n \]

This completes the proof.

Definition: Modular Addition

Let $a, b \in \mathbb{Z}$ and let $n \in \mathbb{N}$.

The multiplication of $a$ and $b$ modulo $n$ is defined as the remainder upon dividing $a \cdot b$ by $n$:

\[ (a \cdot b) \bmod n \]

Notation

\[ a \otimes_n b \]

Theorem: Simplifying Modular Multiplication

Multiplication modulo $n$ has the following property:

\[ a \otimes_n b = ((a \bmod n) \cdot (b \bmod n)) \bmod n \]

Proof

The following proof was generated by AI and has not been human-verified. As such, it may contain mistakes.

By the definition of modular multiplication, the expression $a \otimes_n b$ is equivalent to $(a \cdot b) \bmod n$. Therefore, our goal is to prove that:

\[ (a \cdot b) \bmod n = ((a \bmod n) \cdot (b \bmod n)) \bmod n \]

For any integers $a$ and $n$ (with $n > 0$), there exist unique integers $q$ (quotient) and $r$ (remainder) such that $a = qn + r$ and $0 \le r < n$. By definition, $r = a \bmod n$.

Let's apply this to integers $a$ and $b$:

Let $r_a = a \bmod n$. This means there exists an integer $q_a$ such that $a = q_a n + r_a$.
Let $r_b = b \bmod n$. This means there exists an integer $q_b$ such that $b = q_b n + r_b$.

Now, let's consider the product $a \cdot b$:

\[ \begin{aligned} a \cdot b &= (q_a n + r_a) \cdot (q_b n + r_b) \\ &= (q_a n)(q_b n) + (q_a n)(r_b) + (r_a)(q_b n) + (r_a)(r_b) \\ &= q_a q_b n^2 + q_a r_b n + r_a q_b n + r_a r_b \end{aligned} \]

We can factor out $n$ from the first three terms:

\[ a \cdot b = n (q_a q_b n + q_a r_b + r_a q_b) + r_a r_b \]

Let $k = q_a q_b n + q_a r_b + r_a q_b$. Since $q_a, q_b, n, r_a, r_b$ are all integers, $k$ must also be an integer. So we can write:

\[ a \cdot b = kn + r_a r_b \]

This equation shows that $a \cdot b$ and $r_a r_b$ have the same remainder when divided by $n$. In the language of modular congruence, this means $a \cdot b \equiv r_a r_b \pmod{n}$.

Therefore, by the definition of the modulo operator:

\[ (a \cdot b) \bmod n = (r_a \cdot r_b) \bmod n \]

Now, we substitute back the definitions of $r_a$ and $r_b$:

\[ (a \cdot b) \bmod n = ((a \bmod n) \cdot (b \bmod n)) \bmod n \]

This completes the proof.