Modular Arithmetic

The Mod Operator

Recall the Division Theorem; for any integers $a$ and $b$ with $b\ne 0$, there exist unique integers $q$ and $r$ such that

$$a=qb+r,0\le r<|b|.$$

In a lot of situations we don't actually care about the quotient $q$ at all; the remainder $r$ is the interesting part, so we give it its own operator.

Basically, $a\mathrm{mod}b$ is just "the remainder when you divide $a$ by $b$"; we throw away the quotient and keep only the leftover part. Notice that $a\mathrm{mod}b=0$ if and only if $b\mid a$, since a remainder of zero means $a$ is a perfect multiple of $b$.

In most programming languages this operator is written as %, but that symbol is never used for this purpose in actual mathematics.

Example. Find $19\mathrm{mod}4$, $-11\mathrm{mod}5$ and $333\mathrm{mod}3$.
For each one, write out the Division Theorem and read off the remainder;

$$\begin{array}{rlrl}19& =4\times 4+3& & \Rightarrow 19\mathrm{mod}4=3,\\ -11& =-3\times 5+4& & \Rightarrow -11\mathrm{mod}5=4,\\ 333& =111\times 3+0& & \Rightarrow 333\mathrm{mod}3=0.\end{array}$$

It is important to remember that the remainder is always non-negative, even when $a$ is negative. It is tempting to say $-11\mathrm{mod}5=-1$, but $-1$ is not a valid remainder; instead we push the quotient one lower ($-3$ rather than $-2$) so that the leftover becomes $+4$. Therefore, $19\mathrm{mod}4=3$, $-11\mathrm{mod}5=4$ and $333\mathrm{mod}3=0$.

Modular Congruence

We just saw that $19\mathrm{mod}4=3$, and of course there are infinitely many integers $x$ satisfying $x\mathrm{mod}4=3$ (namely $\dots ,-5,-1,3,7,11,\dots ,19,\dots ,47,\dots$). All of these numbers have something in common, so we say they belong to the same equivalence class. Instead of writing something clunky like $19\mathrm{mod}4=47\mathrm{mod}4$, we use a special congruence notation, $19\equiv 47(\mathrm{mod}4)$.

Basically, two numbers are congruent modulo $m$ if they land on the same spot when you wrap the number line around a circle of circumference $m$; think of a clock, where 13 o'clock and 1 o'clock are the same thing because $13\equiv 1(\mathrm{mod}12)$.

Proof. Statements (1), (2) and (3) all say the same thing by definition, so it is enough to show that (3) $\Rightarrow$ (4) $\Rightarrow$ (5) $\Rightarrow$ (3), looping back around.

(3) $\Rightarrow$ (4): Suppose $a$ and $b$ leave the same remainder $r$; then by the Division Theorem,

$$\begin{array}{rl}a& =q_{1}m+r,\\ b& =q_{2}m+r,\\ a-b& =(q_1-q_2)m,\text{ (subtracting the two equations)},\\ a& =b+mk,\text{ where }k=q_1-q_2\in \mathbb{Z}.\end{array}$$

(4) $\Rightarrow$ (5): If $a=b+mk$, then $a-b=mk$, which is precisely the definition of $m\mid (a-b)$.

(5) $\Rightarrow$ (3): Suppose $m\mid (a-b)$, and write $a=q_{1}m+r_1$ and $b=q_{2}m+r_2$ where $0\le r_1,r_2<m$. Then

$$\begin{array}{rl}a-b& =(q_1-q_2)m+(r_1-r_2).\end{array}$$

Since $m$ divides both $a-b$ and $(q_1-q_2)m$, it must also divide their difference $r_1-r_2$. But $-m<r_1-r_2<m$, and the only multiple of $m$ strictly between $-m$ and $m$ is $0$; hence $r_1=r_2$. $■$

The last characterisation is by far the most useful one in practice:

$$\boxed{a\equiv b(\mathrm{mod}m)⟺m\mid (a-b).}$$

Example. Is it true that $47\equiv 19(\mathrm{mod}4)$?
Rather than computing both remainders separately, just subtract and test divisibility;

$$\begin{array}{rl}47-19& =28\\ & =4\times 7,\end{array}$$

so $4\mid (47-19)$. Therefore, $47\equiv 19(\mathrm{mod}4)$. Notice how checking $m\mid (a-b)$ only needs one division, so it's usually the fastest way to verify a congruence.

Congruence is an Equivalence Relation

Reflexivity and symmetry are pretty self explanatory so I'm not gonna write much; $m\mid (a-a)=0$ since everything divides $0$, and if $m\mid (a-b)$ then $m\mid -(a-b)=(b-a)$. For transitivity, we know $m\mid (a-b)$ and $m\mid (b-c)$, and since divisibility is preserved under sums,

$$\begin{array}{rl}m& \mid (a-b)+(b-c)\\ m& \mid (a-c).\end{array}$$

This is exactly why congruence behaves so much like ordinary equality; it slices $\mathbb{Z}$ up into $m$ equivalence classes (one for each possible remainder), and $\equiv$ acts like "$=$" between the classes.

Properties of Modular Arithmetic

Basically, congruences can be added, subtracted and multiplied together just like ordinary equations, and both sides can be raised to a positive power (property 9 is just property 4 applied to itself $k$ times). Property 1 says a congruence survives shrinking the modulus to any of its divisors; for instance $26\equiv 14(\mathrm{mod}12)$, and since $6\mid 12$, we also get $26\equiv 14(\mathrm{mod}6)$ for free (both leave remainder $2$).

The odd ones out are properties 7 and 8, which are the only two ways to cancel. You cannot freely divide both sides of a congruence; cancellation is only allowed if you also divide the modulus by the same factor (property 7), or if the factor being cancelled is coprime with the modulus (property 8).

We prove two of these; the rest follow from very similar arguments.

Proof (property 4). Since $a\equiv b(\mathrm{mod}m)$ and $c\equiv d(\mathrm{mod}m)$, we can write $a=b+mk$ and $c=d+m\ell$ for some $k,\ell \in \mathbb{Z}$. Then

$$\begin{array}{rl}ac& =(b+mk)(d+m\ell )\\ & =bd+bm\ell +mkd+m^{2}k\ell \\ & =bd+m(b\ell +kd+mk\ell ).\end{array}$$

Since $b\ell +kd+mk\ell \in \mathbb{Z}$, we have $m\mid (ac-bd)$, and hence $ac\equiv bd(\mathrm{mod}m)$. $■$

Proof (property 8). Since $ak\equiv bk(\mathrm{mod}m)$, we know that

$$\begin{array}{rl}m& \mid (ak-bk)\\ m& \mid (a-b)k.\end{array}$$

Because $\gcd (m,k)=1$, we can write $mx+ky=1$ for some $x,y\in \mathbb{Z}$ (the gcd is always an integer linear combination, via the extended Euclidean algorithm). Multiplying through by $a-b$,

$$\begin{array}{rl}a-b& =(a-b)mx+(a-b)ky.\end{array}$$

Now $m$ divides the first term (it contains a factor of $m$), and $m$ divides the second term (since $m\mid (a-b)k$). Therefore $m\mid (a-b)$, i.e. $a\equiv b(\mathrm{mod}m)$. $■$

Example. Find $(123\times 456+789)\mathrm{mod}11$.
The whole point of properties 2 and 4 is that we can reduce every number before doing any arithmetic, instead of multiplying huge numbers together. Reducing each term modulo $11$;

$$\begin{array}{rlrl}123& =11\times 11+2& & \Rightarrow 123\equiv 2(\mathrm{mod}11),\\ 456& =41\times 11+5& & \Rightarrow 456\equiv 5(\mathrm{mod}11),\\ 789& =71\times 11+8& & \Rightarrow 789\equiv 8(\mathrm{mod}11).\end{array}$$

Then,

$$\begin{array}{rl}123\times 456+789& \equiv 2\times 5+8(\mathrm{mod}11)\\ & \equiv 10+8(\mathrm{mod}11)\\ & \equiv 18(\mathrm{mod}11)\\ & \equiv 7(\mathrm{mod}11).\end{array}$$

Therefore, $(123\times 456+789)\mathrm{mod}11=7$; we never had to touch a number bigger than $18$.

Example. It is true that $6\equiv 2(\mathrm{mod}4)$. Can we cancel the common factor of $2$ to conclude that $3\equiv 1(\mathrm{mod}4)$?
No! Checking directly,

$$\begin{array}{rl}3-1& =2,\\ 4& \nmid 2,\end{array}$$

so $3\not\equiv 1(\mathrm{mod}4)$; naive cancelling produced a false statement. The problem is that $\gcd (2,4)=2\ne 1$, so property 8 does not apply. What we are allowed to do is property 7, dividing the two sides and the modulus by $2$;

$$\begin{array}{rl}6& \equiv 2(\mathrm{mod}4)\\ 3& \equiv 1(\mathrm{mod}2),\end{array}$$

which is true, since $3$ and $1$ are both odd. Therefore, before cancelling a factor $k$ from a congruence, always check $\gcd (m,k)$ first; if $k$ shares a factor with the modulus, that factor must be divided out of the modulus too.

The Set of Integers Modulo m

Since congruence modulo $m$ behaves so much like equality, we can build an entire self-contained number system out of it.

Basically, ${\mathbb{Z}}_m$ is clock arithmetic; only the $m$ numbers $0$ to $m-1$ exist, and everything else wraps around. We may write "$a=b$ in ${\mathbb{Z}}_m$" to mean exactly the same thing as congruence modulo m. For example, the following statements are all valid:

• $19=3$ in ${\mathbb{Z}}_4$.
• $19=-1=4$ in ${\mathbb{Z}}_5$.
• Working in ${\mathbb{Z}}_7$, we have $699=-1=6$ (since $700=7\times 100$).

Notice how useful the negative representatives are; being allowed to swap $699$ for $-1$ in ${\mathbb{Z}}_7$ means we can trade a big ugly number for a tiny one, which makes taking powers almost trivial.

Example. Show that $4^{100}$ leaves a remainder of $1$ when divided by $5$.
Since $4\equiv -1(\mathrm{mod}5)$, property 9 lets us replace the base $4$ with $-1$ before taking the power, and $(-1{)}^{100}=1$ because $100$ is even. Here are three ways of writing the exact same proof:

• $4^{100}\mathrm{mod}5=(-1{)}^{100}\mathrm{mod}5=1\mathrm{mod}5=1$.
• $4^{100}\equiv (-1{)}^{100}\equiv 1(\mathrm{mod}5)$.
• $4^{100}=(-1{)}^{100}=1$ in ${\mathbb{Z}}_5$.

Therefore, $4^{100}\mathrm{mod}5=1$; all three notations are interchangeable, so use whichever is cleanest for the question at hand.

Reducing Powers Modulo m

Finding large powers $a^k$ in ${\mathbb{Z}}_m$ is difficult, because you are allowed to reduce the base $a$ modulo $m$, but you can NEVER reduce the exponent $k$ modulo $m$. As a quick counterexample, take $2^4$ in ${\mathbb{Z}}_3$; reducing the exponent $4\mathrm{mod}3=1$ would suggest $2^4\equiv 2^1(\mathrm{mod}3)$, but

$$\begin{array}{rl}{2}^4=16& \equiv 1(\mathrm{mod}3),\\ 2^1& \equiv 2(\mathrm{mod}3),\end{array}$$

which are clearly not the same. The exponent counts how many times we multiply; it is not itself a number living in ${\mathbb{Z}}_m$.

Instead, the trick is to hunt for a small power of $a$ that reduces to something close to $0$ in ${\mathbb{Z}}_m$ (ideally $1$ or $-1$), and then use the Division Theorem on the exponent;

$$\boxed{\text{If }{a}^j\equiv \pm 1(\mathrm{mod}m)\text{ and }k=qj+r,\text{ then }{a}^k=(a^j{)}^q\cdot a^r\equiv (\pm 1{)}^q{a}^r(\mathrm{mod}m).}$$

Example. Find $7^{1001}\mathrm{mod}12$.
Try small powers of $7$ in ${\mathbb{Z}}_{12}$;

$$\begin{array}{rl}{7}^2& =49\\ & =4\times 12+1\\ & \equiv 1(\mathrm{mod}12),\end{array}$$

so we found a power congruent to $1$ almost immediately. Splitting the exponent as $1001=2\times 500+1$,

$$\begin{array}{rl}{7}^{1001}& =(7^2{)}^{500}\times 7^1\\ & \equiv 1^{500}\times 7(\mathrm{mod}12)\\ & \equiv 7(\mathrm{mod}12).\end{array}$$

Therefore, $7^{1001}\mathrm{mod}12=7$.

Example. Find $12^{1001}\mathrm{mod}7$.
First reduce the base; $12\equiv 5\equiv -2(\mathrm{mod}7)$, and $-2$ is the smaller (in size) representative, so work with that. Trying small powers of $-2$,

$$\begin{array}{rl}(-2{)}^2& =4\equiv 4(\mathrm{mod}7),\\ (-2{)}^3& =-8\equiv -1(\mathrm{mod}7),\end{array}$$

so the cube gets us to $-1$. Splitting the exponent as $1001=3\times 333+2$,

$$\begin{array}{rl}12^{1001}& \equiv (-2{)}^{1001}(\mathrm{mod}7)\\ & ={\left((-2{)}^3\right)}^{333}\times (-2{)}^2\\ & \equiv (-1{)}^{333}\times 4(\mathrm{mod}7)\\ & \equiv -4(\mathrm{mod}7)\\ & \equiv 3(\mathrm{mod}7).\end{array}$$

Therefore, $12^{1001}\mathrm{mod}7=3$. Don't forget the very last step; the mod operator demands a remainder between $0$ and $6$, so $-4$ must be converted to $3$ before you write down the final answer.

Example. Find $5^{1001}\mathrm{mod}93$.
Small powers of $5$ don't immediately give $\pm 1$ here, but keep going;

$$\begin{array}{rl}{5}^2& =25\equiv 25(\mathrm{mod}93),\\ 5^3& =125=93+32\equiv 32(\mathrm{mod}93),\\ 5^6& =(5^3{)}^2\equiv 32^2=1024(\mathrm{mod}93),\end{array}$$

and since $1024=11\times 93+1$, we get $5^6\equiv 1(\mathrm{mod}93)$. Splitting the exponent as $1001=6\times 166+5$,

$$\begin{array}{rl}{5}^{1001}& =(5^6{)}^{166}\times 5^5\\ & \equiv 1^{166}\times 5^3\times 5^2(\mathrm{mod}93)\\ & \equiv 32\times 25(\mathrm{mod}93)\\ & \equiv 800(\mathrm{mod}93)\\ & \equiv 800-8\times 93(\mathrm{mod}93)\\ & \equiv 56(\mathrm{mod}93).\end{array}$$

Therefore, $5^{1001}\mathrm{mod}93=56$. We will see some more efficient ways to reduce powers modulo $m$ in Topic 5.

When No Power Reduces to 1

Sometimes the "find $a^j\equiv \pm 1$" strategy is doomed from the start. If $\gcd (a,m)\ne 1$, then every power of $a$ shares that common factor with $m$, so no power of $a$ can ever be congruent to $1$ or $-1$. In that case, look for a repeating cycle in the powers instead.

Example. Find $3^{103}\mathrm{mod}15$.
Here $\gcd (3,15)=3\ne 1$, so every power of $3$ is a multiple of $3$ in ${\mathbb{Z}}_{15}$, and neither $1$ nor $14$ is; hunting for $\pm 1$ would be a waste of time. Instead, list the powers and wait for a repeat;

$$\begin{array}{rl}{3}^1& \equiv 3(\mathrm{mod}15),\\ 3^2& \equiv 9(\mathrm{mod}15),\\ 3^3=27& \equiv 12(\mathrm{mod}15),\\ 3^4=81& \equiv 6(\mathrm{mod}15),\\ 3^5=243& \equiv 3(\mathrm{mod}15).\end{array}$$

Since $3^5\equiv 3^1$, the powers cycle with period $4$ from exponent $1$ onwards; multiplying both sides by $3$ repeatedly gives $3^{k+4}\equiv 3^k(\mathrm{mod}15)$ for all $k\ge 1$. So we can strip multiples of $4$ off the exponent (as long as we stop before reaching $0$);

$$\begin{array}{rl}{3}^{103}& \equiv 3^{103-4\times 25}(\mathrm{mod}15)\\ & \equiv 3^3(\mathrm{mod}15)\\ & \equiv 12(\mathrm{mod}15).\end{array}$$

Therefore, $3^{103}\mathrm{mod}15=12$. Note the subtlety: the cycle starts at exponent $1$, not $0$ ($3^0=1$ is not part of the loop), so we reduce the exponent using the cycle we found, never by blindly taking $103\mathrm{mod}4$ and allowing exponent $0$.

Alternate solution. We can also exploit property 6 from the properties of modular arithmetic. Write $3^{103}=3\times 3^{102}$ and $15=3\times 5$; then it is enough to find $3^{102}$ in ${\mathbb{Z}}_5$, where $\gcd (3,5)=1$ so the usual trick works;

$$\begin{array}{rl}{3}^2=9& \equiv -1(\mathrm{mod}5),\\ 3^{102}=(3^2{)}^{51}& \equiv (-1{)}^{51}(\mathrm{mod}5)\\ & \equiv -1(\mathrm{mod}5)\\ & \equiv 4(\mathrm{mod}5).\end{array}$$

Now multiply both sides and the modulus by $3$ (property 6 with $k=3$);

$$\begin{array}{rl}{3}^{102}& \equiv 4(\mathrm{mod}5)\\ 3\times 3^{102}& \equiv 3\times 4(\mathrm{mod}15)\\ 3^{103}& \equiv 12(\mathrm{mod}15).\end{array}$$

Therefore, $3^{103}\mathrm{mod}15=12$, agreeing with the first method. The decision here is worth remembering; when the base shares a factor with the modulus, either find the cycle directly, or factor that common divisor out and work in the smaller coprime modulus.

Applications of Modular Arithmetic

These kinds of questions rarely announce themselves as "modular arithmetic"; the skill is recognising that some quantity wraps around with a fixed period, and choosing the right modulus.

Last Digit Problems

The last digit of a number is exactly its remainder modulo $10$ (this drops straight out of the base $10$ representation, since every higher digit is multiplied by a power of $10$, and $10\equiv 0(\mathrm{mod}10)$).

Example. Find the last digit of $7^{2026}$.
We want $7^{2026}\mathrm{mod}10$. Hunting for small powers of $7$ in ${\mathbb{Z}}_{10}$,

$$\begin{array}{rl}{7}^2& =49\\ & \equiv -1(\mathrm{mod}10),\end{array}$$

and since $2026=2\times 1013$,

$$\begin{array}{rl}{7}^{2026}& =(7^2{)}^{1013}\\ & \equiv (-1{)}^{1013}(\mathrm{mod}10)\\ & \equiv -1(\mathrm{mod}10)\\ & \equiv 9(\mathrm{mod}10).\end{array}$$

Therefore, the last digit of $7^{2026}$ is $9$.

Day of the Week Problems

Days of the week repeat with period $7$, so any "what day will it be" question is just arithmetic in ${\mathbb{Z}}_7$.

Example. Today is a Thursday. What day of the week will it be $1000$ days from now?
Reduce the number of days modulo $7$;

$$\begin{array}{rl}1000& =142\times 7+6\\ & \equiv 6(\mathrm{mod}7).\end{array}$$

So $1000$ days is $142$ complete weeks (which change nothing) plus $6$ extra days, and counting six days on from Thursday lands on Wednesday. Even quicker, notice that $6\equiv -1(\mathrm{mod}7)$; going forward $1000$ days is the same as going back one day, i.e. the day before Thursday. Therefore, $1000$ days from now it will be a Wednesday.

Divisibility Tests via Digit Sums

Since $10\equiv 1(\mathrm{mod}9)$, property 9 gives $10^k\equiv 1^k\equiv 1(\mathrm{mod}9)$ for every $k\in {\mathbb{Z}}^{+}$; so in ${\mathbb{Z}}_9$, every number collapses down to the sum of its digits. This is exactly where the "divisible by 9 if its digit sum is" test comes from (and the same works modulo $3$, since $10\equiv 1(\mathrm{mod}3)$ too).

Example. Is $76543218$ divisible by $9$?
Expanding in base $10$ and reducing each power of $10$ to $1$,

$$\begin{array}{rl}76543218& =7\times 10^7+6\times 10^6+5\times 10^5+4\times 10^4+3\times 10^3+2\times 10^2+1\times 10+8\\ & \equiv 7+6+5+4+3+2+1+8(\mathrm{mod}9)\\ & \equiv 36(\mathrm{mod}9)\\ & \equiv 0(\mathrm{mod}9).\end{array}$$

Therefore, $9\mid 76543218$; the number is divisible by $9$ because its digit sum is.

Showing a Number is Not a Perfect Square

A classic exam trick is to rule something out by reducing modulo a small number and checking which residues are even possible.

Example. Show that $218745983$ is not a perfect square.
Work in ${\mathbb{Z}}_4$. Every integer $n$ is congruent to one of $0,1,2,3$ modulo $4$, so by property 9 there are only four cases for $n^2$;

$$\begin{array}{rl}{0}^2& \equiv 0(\mathrm{mod}4),\\ 1^2& \equiv 1(\mathrm{mod}4),\\ 2^2=4& \equiv 0(\mathrm{mod}4),\\ 3^2=9& \equiv 1(\mathrm{mod}4).\end{array}$$

So every perfect square is congruent to $0$ or $1$ modulo $4$; a square can never be $2$ or $3$ in ${\mathbb{Z}}_4$. Now, since $100\equiv 0(\mathrm{mod}4)$, any number is congruent modulo $4$ to just its last two digits, hence

$$\begin{array}{rl}218745983& \equiv 83(\mathrm{mod}4)\\ & \equiv 3(\mathrm{mod}4),\text{ (as }83=20\times 4+3).\end{array}$$

Since $3$ is not an achievable residue for a square, $218745983$ cannot be a perfect square. Therefore, we ruled it out without computing a single square root; picking a small modulus and eliminating impossible residues is often far faster than direct computation.