# 22.2 Modular arithmetic

Given that we now know that division really exists (as if there was ever any doubt), we can start to talk about remainders.

## 22.2.1 Core definitions

###### Definition 22.2.1

We say that for $x,y,m\in\mathbb{Z}$ that

if and only if $m|(x-y)$.

###### Theorem 22.2.1

For $x,y,m\in\mathbb{Z}$, $x\equiv_{m}y$ if and only if $R_{m}(x)=R_{m}(y)$.

Proof: first we prove the \sayif direction; suppose that $x=a\times m+r$ and $y=b\times m+r$ where we define $r=R_{m}(x)=R_{m}(y)$. In this case

$\displaystyle x-y$ | $\displaystyle=a\times m+r-b\times m-r$ | (22.30) | ||

$\displaystyle=(a-b)\times m$ | (22.31) |

and thus $m|(x-y)$.

For the \sayonly if direction, things are marginally more hairy. Let us suppose that $x\equiv_{m}y$, then

Here we will apply the division algorithm (Theorem 22.1.1), which tells us that we have unique $R_{m}(a)$ and $R_{m}(b)$ such that

$\displaystyle x=am+R_{m}(x)$ | $\displaystyle y=bm+R_{m}(y)$ | $\displaystyle 0\leqq R_{m}(x),R_{m}(y)<m$ | (22.33) |

Then, it follows from $0\leqq R_{m}(x),R_{m}(y)<m$ that

which in turn implies that

Therefore, we can write that

from which we can show that $m|(R_{m}(x)-R_{m}(y))$; as $m|(x-y)$ by definition there exists integer $k$ such that $x-y=km$, and thus that

Then as $-m<R_{m}(x)-R_{m}(y)<m$ it must be true that

and thus the desired equality holds.

## 22.2.2 The properties which make modular arithmetic

The first core property is this

###### Theorem 22.2.2

If $a\equiv_{m}b$ and $c\equiv_{m}d$, then

Proof: TODO

###### Theorem 22.2.3

If $a\equiv_{m}b$ and $c\equiv_{m}d$, then

Proof: TODO

###### Example 22.2.1

Calculate

This requires a bit of careful thinking about, but the result should be

$\displaystyle 17^{17}$ | $\displaystyle\equiv_{10}7^{17}$ | $\displaystyle\equiv_{10}77^{16}$ | (22.42) | ||

$\displaystyle\equiv_{10}7\left(7^{2}\right)^{8}$ | (22.43) | ||||

$\displaystyle\equiv_{10}7\left(-1\right)^{8}$ | (22.44) | ||||

$\displaystyle\equiv_{10}7$ | (22.45) |

## 22.2.3 Fermat’s little theorem

There is also Fermat’s non-little theorem (called Fermat’s Last Theorem which was unproven for 358 years).

###### Theorem 22.2.4 (Fermat’s little theorem)

Let $a$ and $m$ be two coprime integers (i.e. $\gcd(a,m)=1$) then

todo: proof (it’s by induction, or using some abstract algebra).

###### Example 22.2.2

Find the value of

. That is, the remainder when $2^{3^{40}}$ is divided by $11$.

The first thing to do is quickly write down that by Fermat’s Little Theorem (Theorem 22.2.4) we know that

Therefore, if we let $q$ be the quotient and $r$ the remainder of dividing $3^{40}$ by $10$, we can then write

$\displaystyle 2^{3^{40}}$ | $\displaystyle\equiv_{11}2^{q\times 10+r}$ | (22.48) | ||

$\displaystyle\equiv_{11}2^{q\times 10}2^{r}$ | (22.49) | |||

$\displaystyle\equiv_{11}\left(2^{10}\right)^{q}2^{r}$ | (22.50) | |||

$\displaystyle\equiv_{11}1^{q}2^{r}$ | (22.51) | |||

$\displaystyle\equiv_{11}2^{r}$ | (22.52) |

We have substantially simplified this problem because it is now only a problem of finding $r$, which we can do by computing $3^{40}\mod 10$. This requires a bit of arithmetic, but (if you know the rules of modular arithmetic) nothing too horrible;

$\displaystyle 3^{40}$ | $\displaystyle\equiv_{11}$ | (22.53) | ||

$\displaystyle\equiv_{11}(3^{4})^{10}$ | (22.54) | |||

$\displaystyle\equiv_{11}1^{10}$ | (22.55) | |||

$\displaystyle\equiv_{11}1.$ | (22.56) |

Therefore, the answer is that $R_{11}(2^{3^{40}})=R_{11}(2)=2$.

## 22.2.4 The Chinese remainder theorem (and related problems)

###### Example 22.2.3

Consider the function $f:\mathbb{Z}_{48}\to\mathbb{Z}_{6}\times\mathbb{Z}_{8}$, where $f$ is defined by $f(x)=\big{(}R_{6}(x),R_{8}(x)\big{)}$. Prove or disprove whether $f$ is surjective.

This statement is false, and we can prove it like this; first note that for $f$ to be surjective it must be true that for every $(a,b)\in\mathbb{Z}_{6}\times\mathbb{Z}_{8}$ there exists some $x$ such that

which is equivalent to the system of congruence equations

$\displaystyle x\equiv_{6}a$ | (22.58) | ||

$\displaystyle x\equiv_{8}b$ | (22.59) |

I found it helpful to draw a number line here, e.g. something like this

Thinking about some values for $a$ and $b$, to me at least, the problematic values will be those that are close to $6$ and $8$ (or multiples therefore). If we think about, for example, numbers which are divisible by $6$, but one bigger than $8$ or a multiple of $8$ (i.e. divisible by $8$ with remainder $1$), we encounter a problem, which is this; for the specific values $a=0$ and $b=1$ we are trying to solve the system of modular equations

$\displaystyle x\equiv_{6}0\implies\text{ x is even}$ | (22.60) | ||

$\displaystyle x\equiv_{8}1\implies\text{ x is odd}$ | (22.61) |

But there are no numbers which are both odd and even, so there exists no $x$ such that $f(x)=(0,1)$, i.e. $f$ cannot be surjective.