Modular Arithmetic

Division Algorithm

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<|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\mathrm{mod}b$$

PROOF

TODO

Theorem: Finding the Remainder

The remainder is always given by the following formula:

$$a\mathrm{mod}b=a-|b|\cdot \lfloor \frac{a}{|b|}\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)\mathrm{mod}n=0$$

NOTATION

$$a\equiv b\mathrm{mod}na\equiv b(\mathrm{mod}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)\mathrm{mod}n$$

NOTATION

$$a{\oplus }_{n}b$$

Theorem: Simplifying Modular Addition

Addition modulo $n$ has the following property:

$$a{\oplus }_{n}b=((a\mathrm{mod}n)+(b\mathrm{mod}n))\mathrm{mod}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)\mathrm{mod}n$$

We want to prove that this is equal to the right-hand side (RHS):

$$((a\mathrm{mod}n)+(b\mathrm{mod}n))\mathrm{mod}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\mathrm{mod}n$ (with $0\le r_a<n$).
• $b=q_{b}n+r_b$, where $q_b$ is an integer and $r_b=b\mathrm{mod}n$ (with $0\le r_b<n$).

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

$$\begin{array}{rl}(a+b)\mathrm{mod}n& =((q_{a}n+r_a)+(q_{b}n+r_b))\mathrm{mod}n\\ & =(q_{a}n+q_{b}n+r_a+r_b)\mathrm{mod}n\\ & =((q_a+q_b)n+(r_a+r_b))\mathrm{mod}n\end{array}$$

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)\mathrm{mod}n$$

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

$$\begin{array}{rl}((a\mathrm{mod}n)+(b\mathrm{mod}n))\mathrm{mod}n& =(r_a+r_b)\mathrm{mod}n\\ \text{RHS}& =(r_a+r_b)\mathrm{mod}n\end{array}$$

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

$$(a+b)\mathrm{mod}n=((a\mathrm{mod}n)+(b\mathrm{mod}n))\mathrm{mod}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)\mathrm{mod}n$$

NOTATION

$$a{\otimes }_{n}b$$

Theorem: Simplifying Modular Multiplication

Multiplication modulo $n$ has the following property:

$$a{\otimes }_{n}b=((a\mathrm{mod}n)\cdot (b\mathrm{mod}n))\mathrm{mod}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)\mathrm{mod}n$. Therefore, our goal is to prove that:

$$(a\cdot b)\mathrm{mod}n=((a\mathrm{mod}n)\cdot (b\mathrm{mod}n))\mathrm{mod}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\mathrm{mod}n$.

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

1. Let $r_a=a\mathrm{mod}n$. This means there exists an integer $q_a$ such that $a=q_{a}n+r_a$.
2. Let $r_b=b\mathrm{mod}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{array}{rl}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{array}$$

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(\mathrm{mod}n)$.

Therefore, by the definition of the modulo operator:

$$(a\cdot b)\mathrm{mod}n=(r_a\cdot r_b)\mathrm{mod}n$$

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

$$(a\cdot b)\mathrm{mod}n=((a\mathrm{mod}n)\cdot (b\mathrm{mod}n))\mathrm{mod}n$$

This completes the proof.