×

# Modular Arithmetic - An Introduction

Modular Arithmetic is an extremely useful way of thinking about numbers. It can be used to calculate the last three digits of $$2011^{2011}$$ by hand. The day of the week, the time of the day, and the flipping of a light switch are all based upon modular arithmetic. The day of the week is in $$\mod 7$$ (cycles in a period of $$7$$), the time of the day is in $$\mod 24$$, and a light switch is either on or off; $$\mod 2$$.

$$\textbf{Definitions}$$

Two integers are congruent modulo $$n$$ if their difference is a multiple of $$n$$. We write this as $a \equiv b \pmod{n}$ For example, $$36 \equiv 71 \pmod{7}$$, because $$71 - 36 = 35$$, and $$\dfrac{35}{7} = 5$$. We can alternatively write this as $$a-b = qn$$, for an integer $$q$$, or $$a = b + qn$$ (by adding $$b$$ to both sides). Notice that for any integers $$x$$ and $$y$$, if $$x \equiv y \pmod{n}$$, $$x$$ and $$y$$ leave the same remainder when divided by $$n$$. This is sometimes used as another definition for modular arithmetic. Since modular arithmetic is only defined for integers, let all variables be integers unless otherwise specified.

$$\textbf{Addition}$$

$$\textbf{Theorem 1:}$$ If $$a \equiv b \pmod{n}$$, then $$a+c \equiv b+c \pmod{n}$$.

If $$a \equiv b \pmod{n}$$, we know that $$a-b = qn$$ for some integer $$q$$. This means $$(a+c) - (b+c) = a-b = qn$$, so $$a+c \equiv b+c \pmod{n}$$. $$\blacksquare$$

If we know that $$123$$ leaves a remainder of $$2$$ when divided by $$11$$, and want the remainder when $$127$$ is divided by $$11$$, we can simply use Theorem 1: $$123 \equiv 2 \pmod{11} \implies 123 + 4 \equiv 2 + 4 \pmod{11}$$, so $$127 \equiv 6 \pmod{11}$$. A similar proof can be used to prove a stronger theorem:

$$\textbf{Theorem 2:}$$ If $$a \equiv b \pmod{n}$$, and $$c \equiv d \pmod{n}$$, then $$a+c \equiv b+d \pmod{n}$$.

We know that $$a-b = qn$$ for some integer $$q$$ and $$c-d = rn$$ for some integer $$r$$. Adding the equations gives $$(a+c) - (b+d) = qn + rn = (q+r)n$$. This means that the difference of $$a+c$$ and $$b+d$$ is a multiple of $$n$$, so $$a+c \equiv b+d \pmod{n}$$. $$\blacksquare$$

Theorem 2 can be generalized even further:

$$\textbf{Theorem 3:}$$ If $$a_1 \equiv b_1 \pmod{n}$$, $$a_2 \equiv b_2 \pmod{n}$$, $$\cdots , \ a_k \equiv b_k \pmod{n}$$ then $$a_1 + a_2 + \cdots + a_k \equiv b_1 + b_2 + \cdots + b_k \pmod{n}$$.

By the definition of modulos, we get $$a_1 - b_1 = q_1 n, \ a_2 - b_2 = q_2 n, \cdots , \ a_k - b_k = q_k n$$. Adding these, we get $(a_1 + a_2 + \cdots + a_k) - (b_1 + b_2 + \cdots + b_k) = (q_1 + q_2 + \cdots + q_k)n$,so $$a_1 + a_2 + \cdots + a_k \equiv b_1 + b_2 + \cdots + b_k \pmod{n}$$. $$\blacksquare$$

Theorem 3 can be used to solve the following problem:

$$\textbf{Problem 1}$$ Find the remainder when $$123 + 234+ 32+ 56+ 22 + 12 + 78$$ is divided by $$3$$

We know that $$123 \equiv 0 \pmod{3}$$, $$234 \equiv 0 \pmod{3}$$, $$32 \equiv 2 \pmod{3}$$, $$56 \equiv 2 \pmod{3}$$, $$22 \equiv 1 \pmod{3}$$, $$12 \equiv 0 \pmod{3}$$, and $$78 \equiv 0 \pmod{3}$$. From Theorem 3, $$123 + 234+ 32+ 56+ 22 + 12 + 78 \equiv 0+0+2+2+1+0+0 \equiv 5 \pmod{3}$$. $$5$$ has a remainder of $$2$$ when divided by $$3$$, so $$123 + 234+ 32+ 56+ 22 + 12 + 78$$ does too, and the answer is $$\boxed{2}$$.

$$\textbf{Subtraction}$$

The same theorems hold for subtraction as well:

$$\textbf{Theorem 4:}$$ If $$a \equiv b \pmod{n}$$, then $$a-c \equiv b-c \pmod{n}$$.

If $$a \equiv b \pmod{n}$$, we know that $$a-b = qn$$ for some integer $$q$$. This means $$(a-c) - (b-c) = a-b = qn$$, so $$a-c \equiv b-c \pmod{n}$$. $$\blacksquare$$

$$\textbf{Theorem 5:}$$ If $$a \equiv b \pmod{n}$$, and $$c \equiv d \pmod{n}$$, then $$a-c \equiv b-d \pmod{n}$$.

We know that $$a-b = qn$$ for some integer $$q$$ and $$c-d = rn$$ for some integer $$r$$. Subtracting the equations gives $$(a-c) - (b-d) = qn - rn = (q-r)n$$. This means that the difference of $$a-c$$ and $$b-d$$ is a multiple of $$n$$, so $$a-c \equiv b-d \pmod{n}$$. $$\blacksquare$$

$$\textbf{Multiplication}$$

Similar theorems hold for muliplication as well, but the proofs are different.

$$\textbf{Theorem 6:}$$ If $$a \equiv b \pmod{n}$$, then $$ac \equiv bc \pmod{n}$$.

If $$a \equiv b \pmod{n}$$, we know that $$a-b = qn$$ for some integer $$q$$. This means $$ac-bc = qcn$$, so $$ac \equiv bc \pmod{n}$$. $$\blacksquare$$

There is also another proof of this:

We know that $\underbrace{a \equiv b \pmod{n}, \ a \equiv b \pmod{n}, \cdots , \ a \equiv b \pmod{n}}_{\text{c statements}}$ From Theorem 3, we get $\underbrace{a+a+a+a+\cdots + a}_{\text{c "a"s}} \equiv \underbrace{b+b+b+b+\cdots + b}_{\text{c "b"s}}$ or $$ac \equiv bc \pmod{n}$$. $$\blacksquare$$

$$\textbf{Theorem 7:}$$ If $$a \equiv b \pmod{n}$$, and $$c \equiv d \pmod{n}$$, then $$ac \equiv bd \pmod{n}$$.

We repeatedly use Theorem 6: Since $$a \equiv b$$, $$ac \equiv bc$$, and since $$c \equiv d$$, $$bc \equiv bd$$. Therefore, $$ac \equiv bc \equiv bd$$, or $$ac \equiv bd \pmod{n}$$. $$\blacksquare$$

$$\textbf{Theorem 8:}$$ If $$a_1 \equiv b_1 \pmod{n}$$, $$a_2 \equiv b_2 \pmod{n}$$, $$\cdots , \ a_k \equiv b_k \pmod{n}$$ then $$a_1 a_2 \cdots a_k \equiv b_1 b_2 \cdots b_k \pmod{n}$$.

We repeatedly use Theorem 7: Because $$a_1 \equiv b_1 \pmod{n}$$, $$a_2 \equiv b_2 \pmod{n}$$, we get $a_1a_2 \equiv b_1b_2 \pmod{n}$ We also know $$a_3 \equiv b_3 \pmod{n}$$, so $a_1a_2a_3 \equiv b_1b_2b_3 \pmod{n}$ Also, $$a_4 \equiv b_4 \pmod{n}$$, so $a_1a_2a_3a_4 \equiv b_1b_2b_3b_4 \pmod{n}$ Continuing to do this will give $a_1 a_2 \cdots a_k \equiv b_1 b_2 \cdots b_k \pmod{n}$ $$\blacksquare$$

$$\textbf{Problem 2:}$$ Find the remainder when $$124 \cdot 134 \cdot 23 \cdot 49 \cdot 235 \cdot 13$$ is divided by $$3$$.

In Problem 1, manually adding the numbers up wouldn't take that much time, though the modular arithmetic solution is faster. However, in Problem 2, multiplying the numbers would be very tedious. Instead, we use Theorem 8: We know that $$124 \equiv 1$$, $$134 \equiv 2$$, $$23 \equiv 2$$, $$49 \equiv 1$$, $$235 \equiv 1$$, and $$13 \equiv 1$$. Therefore, from Theorem 8, $124 \cdot 134 \cdot 23 \cdot 49 \cdot 235 \cdot 13 \equiv 1 \cdot 2 \cdot 2 \cdot 1 \cdot 1 \cdot 1 \equiv 4 \equiv 1 \pmod{3}$ so the product leaves a remainder of $$\boxed{1}$$ when divided by $$3$$.

$$\textbf{Exponentiation}$$ Note that a corollary of Theorem 8, when $$a_1 = a_2 = \cdots = a_k$$ and $$a_1 = a_2 = \cdots = a_k$$, is that

$$\textbf{Theorem 9:}$$ If $$a \equiv b \pmod{n}$$, then $$a^k \equiv b^k \pmod{n}$$. One might expect the following theorem to hold:

If $$x \equiv y \pmod{n}$$, then $$a^x \equiv a^y \pmod{n}$$.

However, taking $$n = 3$$, $$a =2$$, $$x = 2$$, and $$y = 5$$, we get $$2 \equiv 5 \pmod{3}$$, but $$2^2 \equiv 1 \not\equiv 2 \equiv 2^5 \pmod{3}$$.

$$\textbf{Problem 3:}$$ What is the remainder when $$23^{12345}$$ is divided by $$22$$?

From Theorem 9, since $$23 \equiv 1 \pmod{22}$$, $$23^{12345} \equiv 1^{12345} \equiv 1 \pmod{22}$$, so $$23^{12345}$$ leaves a remainder of $$\boxed{1}$$ when divded by $$22$$.

$$\textbf{Problem 4:}$$ Find the last three digits of $$2^{40}$$

$\begin{eqnarray*}2^{40} &=& \left(2^{10}\right)^4 \\ &=& 1024^4 \\ &\equiv& 24^4 \\ &\equiv& 576^2 \pmod{1000}\end{eqnarray*}$ We can write $$576^2$$ as $\begin{eqnarray*}(500+76)(500+76) &=& 250000+2*500*76+76*76 \\ &=& 250000 + 76000 + 5776 \\ &\equiv& 0 + 5776 \\ &\equiv& 776 \pmod{1000}\end{eqnarray*}$. Since $$2^{40}$$ leaves a remainder of $$776$$ when divided by $$1000$$, its last three digits are $$\boxed{776}$$.

And finally, we get to the problem mentioned in the introduction:

$$\textbf{Problem 5:}$$ Find the last three digits of $$2011^{2011}$$

We know that $$2011 \equiv 11 \pmod{1000}$$, so $$2011^{2011} \equiv 11^{2011} \pmod{1000}$$. We can write $$11^{2011}$$ as $$(10+1)^{2011}$$ and use the Binomial Theorem to expand it. We get $\begin{eqnarray*} 11^{2011} &=& (10+1)^{2011} \\ &=& \dbinom{2011}{0} 10^{2011}1^{0}+\dbinom{2011}{1} 10^{2010}1^{1} + \cdots + \dbinom{2011}{2010} 10^11^{2010} + \dbinom{2011}{2011} 1^{2011} \end{eqnarray*}$ However, all powers of 10 above $$10^2$$ are divisible by $$1000$$, so are $$0 \pmod{1000}$$. Therefore, we can reduce them to $$0$$. All terms at the beginning are nullified, and we are left with $\dbinom{2011}{2009} 10^2 1^{2009} + \dbinom{2011}{2010} 10^11^{2010} + \dbinom{2011}{2011} 1^{2011} = 100 \cdot \dbinom{2011}{2} + 10 \cdot \dbinom{2011}{1} + 1 \cdot \dbinom{2011}{0}$ because of the property that $$\dbinom{2011}{2009} = \dbinom{2011}{2}$$, $$\dbinom{2011}{2010} = \dbinom{2011}{1}$$, and $$\dbinom{2011}{2011} = \dbinom{2011}{0}$$. We can write this as $\begin{eqnarray*}100 \cdot \dfrac{2011 \cdot 2010}{2} + 10 \cdot 2011 + 1 &\equiv& 100 \cdot \dfrac{11 \cdot 10}{2}+ 10 \cdot 11 + 1 \\ &=& 5500 + 110 + 1 \\ &\equiv& \boxed{611} \pmod{1000}\end{eqnarray*}$ $$\blacksquare$$

3 years, 5 months ago

Sort by:

Very good post, detailed and clear! Please fix that LaTeX in the middle (Thm. 6), though. · 3 years, 5 months ago

It's helpful, but it would be more helpful if you could write an 867-page article how to evaluate $$i\pmod{j}$$ for $$0\le i\neq j\le1000$$. · 3 years, 5 months ago

$$0<i\neq j\le 10$$.

For those who would want such an article, see here. It is a very enlightening article if you read it all the way through. · 3 years, 5 months ago

And also CRT · 3 years, 5 months ago

I didn't knew a single word about Modular Arithmetic..!! Thanks to u for letting me know what is it. · 2 years, 11 months ago

If $$a \equiv b \pmod{n}$$ implies $$a - b = qn$$ where q and n are integers, then is it true that $$a \equiv b \pmod{q}$$ ? · 3 years, 2 months ago

yes. Just use the definition. · 2 years, 9 months ago

What about Intermediate Modular Arithmetic? Brilliant Tecniques do not cover it · 3 years, 4 months ago

You wrote the same article in Aops, really good job anyway :D · 3 years, 5 months ago

Great job! It helps! · 3 years, 5 months ago

@Akshaj Kadaveru Can you add this to the Modular Arithmetic Wiki? Thanks! Staff · 2 years, 7 months ago

cool! · 3 years, 4 months ago

Shall we make all Theorems a little more users friendly!
$$\Large{a, ~b,~\alpha,~\beta,~c,~m~~ all~ integers. \\ \color{red}{a_1 \equiv b_1 \pmod m,~~~ a_2 \equiv b_2 \pmod m....a_n \equiv b_n \pmod m }.\\~~~~~~ \\ \textbf{Addition and Subtraction}\\ \textit{Theorem 1}~~~~~a \pm c \equiv b \pm c \pmod m\\\textit{Theorem 2}~~~~~a_1 \pm a_2 \pm. . .\pm a_n \equiv b_1 \pm b_2 \pm . . .\pm b_n \pmod m~~~\\ \textbf{Multiplication}\\\textit{Theorem 3a}~~~~~a_1*a_2* . . . * a_n \equiv b_1*b_2* . . .*b_n \pmod m~~~~\\\textit{Theorem 3b}~~~~~a^n \equiv b^n \pmod m}$$ · 2 years, 3 months ago

Thanks once again for a wonderful writeup. I've added parts of it, especially the example problems, to the Modular Arithmetic Wiki. Staff · 2 years, 5 months ago

VERY nice !!!!!!!!! · 3 years ago

@HARSH SHrivastava -Which class are you in? · 2 years, 10 months ago

I am in 9th (early admission.).In which class are you? · 2 years, 10 months ago

10TH- But I must say you are very lucky to have found Brilliant in 9th itself~!!!!!! · 2 years, 10 months ago