22.2 Modular arithmetic ‣ Chapter 22 Number theory ‣ Part III General mathematics ‣ A calculus of the absurd‣ Chapter 22 Number theory ‣ Part III General mathematics ‣ A calculus of the absurd

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)<m

(22.33)

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

-R_{m}(y)\leqq R_{m}(x)-R_{m}(y)<m-R_{m}(y)

(22.34)

which in turn implies that

-m<R_{m}(x)-R_{m}(y)<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<R_{m}(x)-R_{m}(y)<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.