Waste less time on Facebook — follow Brilliant.
×

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

Note by Akshaj Kadaveru
3 years, 10 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Very good post, detailed and clear! Please fix that LaTeX in the middle (Thm. 6), though.

Michael Tang - 3 years, 10 months ago

Log in to reply

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\).

Cody Johnson - 3 years, 10 months ago

Log in to reply

\(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.

Daniel Chiu - 3 years, 10 months ago

Log in to reply

And also CRT

Dinesh Chavan - 3 years, 10 months ago

Log in to reply

I didn't knew a single word about Modular Arithmetic..!! Thanks to u for letting me know what is it.

Sudipta Biswas - 3 years, 4 months ago

Log in to reply

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} \) ?

Shabarish Ch - 3 years, 7 months ago

Log in to reply

yes. Just use the definition.

Mathh Mathh - 3 years, 2 months ago

Log in to reply

What about Intermediate Modular Arithmetic? Brilliant Tecniques do not cover it

Jordi Bosch - 3 years, 9 months ago

Log in to reply

You wrote the same article in Aops, really good job anyway :D

Abhijeeth Babu - 3 years, 10 months ago

Log in to reply

Great job! It helps!

Jordi Bosch - 3 years, 10 months ago

Log in to reply

@Akshaj Kadaveru Can you add this to the Modular Arithmetic Wiki? Thanks!

Calvin Lin Staff - 3 years ago

Log in to reply

cool!

Fatin Farhan - 3 years, 9 months ago

Log in to reply

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}\)

Niranjan Khanderia - 2 years, 8 months ago

Log in to reply

Thanks once again for a wonderful writeup. I've added parts of it, especially the example problems, to the Modular Arithmetic Wiki.

Calvin Lin Staff - 2 years, 10 months ago

Log in to reply

VERY nice !!!!!!!!!

Harsh Shrivastava - 3 years, 5 months ago

Log in to reply

@HARSH SHrivastava -Which class are you in?

Krishna Ar - 3 years, 3 months ago

Log in to reply

I am in 9th (early admission.).In which class are you?

Harsh Shrivastava - 3 years, 3 months ago

Log in to reply

@Harsh Shrivastava 10TH- But I must say you are very lucky to have found Brilliant in 9th itself~!!!!!!

Krishna Ar - 3 years, 3 months ago

Log in to reply

@Krishna Ar When am I going to read modular arithmetic. I am also in class 9.

Manish Mayank - 3 years, 2 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...