# 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

$x\equiv_{m}y$ (22.29)

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

$m|(y-x)\iff y-x=km.$ (22.32)

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) (22.33)

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

$-R_{m}(y)\leqq R_{m}(x)-R_{m}(y) (22.34)

which in turn implies that

$-m (22.35)

Therefore, we can write that

$x-y=am+R_{m}(x)-(bm+R_{m}(y))$ (22.36)

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

$(k-a+b)m=R_{m}(x)-R_{m}(y).$ (22.37)

Then as $-m it must be true that

$R_{m}(x)-R_{m}(y)=0m=0$ (22.38)

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

$a+c\equiv_{m}b+d$ (22.39)

Proof: TODO

###### Theorem 22.2.3

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

$ac\equiv_{m}cd$ (22.40)

Proof: TODO

###### Example 22.2.1

Calculate

$R_{10}(17^{17})$ (22.41)

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

$a^{m}\equiv_{m}m$ (22.46)

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

###### Example 22.2.2

Find the value of

$R_{11}\left(2^{3^{40}}\right)$

. 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

$2^{11}\equiv_{11}2\implies 2^{10}\equiv_{11}1.$ (22.47)

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

$(R_{6}(x),R_{8}(x))=(a,b),$ (22.57)

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.