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,mx,y,m\in\mathbb{Z} that

xmyx\equiv_{m}y (22.29)

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

Theorem 22.2.1

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

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

xy\displaystyle x-y =a×m+rb×mr\displaystyle=a\times m+r-b\times m-r (22.30)
=(ab)×m\displaystyle=(a-b)\times m (22.31)

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

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

m|(yx)yx=km.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 Rm(a)R_{m}(a) and Rm(b)R_{m}(b) such that

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

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

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

which in turn implies that

m<Rm(x)Rm(y)<m.-m<R_{m}(x)-R_{m}(y)<m. (22.35)

Therefore, we can write that

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

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

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

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

Rm(x)Rm(y)=0m=0R_{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 amba\equiv_{m}b and cmdc\equiv_{m}d, then

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

Proof: TODO

Theorem 22.2.3

If amba\equiv_{m}b and cmdc\equiv_{m}d, then

acmcdac\equiv_{m}cd (22.40)

Proof: TODO

Example 22.2.1


R10(1717)R_{10}(17^{17}) (22.41)

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

1717\displaystyle 17^{17} 10717\displaystyle\equiv_{10}7^{17} 107716\displaystyle\equiv_{10}77^{16} (22.42)
107(72)8\displaystyle\equiv_{10}7\left(7^{2}\right)^{8} (22.43)
107(1)8\displaystyle\equiv_{10}7\left(-1\right)^{8} (22.44)
107\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 aa and mm be two coprime integers (i.e. gcd(a,m)=1\gcd(a,m)=1) then

ammma^{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


. That is, the remainder when 23402^{3^{40}} is divided by 1111.

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

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

Therefore, if we let qq be the quotient and rr the remainder of dividing 3403^{40} by 1010, we can then write

2340\displaystyle 2^{3^{40}} 112q×10+r\displaystyle\equiv_{11}2^{q\times 10+r} (22.48)
112q×102r\displaystyle\equiv_{11}2^{q\times 10}2^{r} (22.49)
11(210)q2r\displaystyle\equiv_{11}\left(2^{10}\right)^{q}2^{r} (22.50)
111q2r\displaystyle\equiv_{11}1^{q}2^{r} (22.51)
112r\displaystyle\equiv_{11}2^{r} (22.52)

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

340\displaystyle 3^{40} 11\displaystyle\equiv_{11} (22.53)
11(34)10\displaystyle\equiv_{11}(3^{4})^{10} (22.54)
11110\displaystyle\equiv_{11}1^{10} (22.55)
111.\displaystyle\equiv_{11}1. (22.56)

Therefore, the answer is that R11(2340)=R11(2)=2R_{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:486×8f:\mathbb{Z}_{48}\to\mathbb{Z}_{6}\times\mathbb{Z}_{8}, where ff is defined by f(x)=(R6(x),R8(x))f(x)=\big{(}R_{6}(x),R_{8}(x)\big{)}. Prove or disprove whether ff is surjective.

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

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

which is equivalent to the system of congruence equations

x6a\displaystyle x\equiv_{6}a (22.58)
x8b\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 aa and bb, to me at least, the problematic values will be those that are close to 66 and 88 (or multiples therefore). If we think about, for example, numbers which are divisible by 66, but one bigger than 88 or a multiple of 88 (i.e. divisible by 88 with remainder 11), we encounter a problem, which is this; for the specific values a=0a=0 and b=1b=1 we are trying to solve the system of modular equations

x60 x is even\displaystyle x\equiv_{6}0\implies\text{ x is even} (22.60)
x81 x is odd\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 xx such that f(x)=(0,1)f(x)=(0,1), i.e. ff cannot be surjective.