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 201120112011^{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 mod7\mod 7 (cycles in a period of 77), the time of the day is in mod24\mod 24, and a light switch is either on or off; mod2\mod 2.

Definitions\textbf{Definitions}

Two integers are congruent modulo nn if their difference is a multiple of nn. We write this as ab(modn)a \equiv b \pmod{n} For example, 3671(mod7)36 \equiv 71 \pmod{7}, because 7136=3571 - 36 = 35, and 357=5\dfrac{35}{7} = 5. We can alternatively write this as ab=qna-b = qn, for an integer qq, or a=b+qna = b + qn (by adding bb to both sides). Notice that for any integers xx and yy, if xy(modn)x \equiv y \pmod{n}, xx and yy leave the same remainder when divided by nn. 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.

Addition\textbf{Addition}

Theorem 1:\textbf{Theorem 1:} If ab(modn)a \equiv b \pmod{n}, then a+cb+c(modn)a+c \equiv b+c \pmod{n}.

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

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

Theorem 2:\textbf{Theorem 2:} If ab(modn)a \equiv b \pmod{n}, and cd(modn)c \equiv d \pmod{n}, then a+cb+d(modn)a+c \equiv b+d \pmod{n}.

We know that ab=qna-b = qn for some integer qq and cd=rnc-d = rn for some integer rr. Adding the equations gives (a+c)(b+d)=qn+rn=(q+r)n(a+c) - (b+d) = qn + rn = (q+r)n. This means that the difference of a+ca+c and b+db+d is a multiple of nn, so a+cb+d(modn)a+c \equiv b+d \pmod{n}. \blacksquare

Theorem 2 can be generalized even further:

Theorem 3:\textbf{Theorem 3:} If a1b1(modn)a_1 \equiv b_1 \pmod{n}, a2b2(modn)a_2 \equiv b_2 \pmod{n}, , akbk(modn)\cdots , \ a_k \equiv b_k \pmod{n} then a1+a2++akb1+b2++bk(modn)a_1 + a_2 + \cdots + a_k \equiv b_1 + b_2 + \cdots + b_k \pmod{n}.

By the definition of modulos, we get a1b1=q1n, a2b2=q2n,, akbk=qkna_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 (a1+a2++ak)(b1+b2++bk)=(q1+q2++qk)n(a_1 + a_2 + \cdots + a_k) - (b_1 + b_2 + \cdots + b_k) = (q_1 + q_2 + \cdots + q_k)n,so a1+a2++akb1+b2++bk(modn)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:

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

We know that 1230(mod3)123 \equiv 0 \pmod{3}, 2340(mod3)234 \equiv 0 \pmod{3}, 322(mod3)32 \equiv 2 \pmod{3}, 562(mod3)56 \equiv 2 \pmod{3}, 221(mod3)22 \equiv 1 \pmod{3}, 120(mod3)12 \equiv 0 \pmod{3}, and 780(mod3)78 \equiv 0 \pmod{3}. From Theorem 3, 123+234+32+56+22+12+780+0+2+2+1+0+05(mod3)123 + 234+ 32+ 56+ 22 + 12 + 78 \equiv 0+0+2+2+1+0+0 \equiv 5 \pmod{3}. 55 has a remainder of 22 when divided by 33, so 123+234+32+56+22+12+78123 + 234+ 32+ 56+ 22 + 12 + 78 does too, and the answer is 2\boxed{2}.

Subtraction\textbf{Subtraction}

The same theorems hold for subtraction as well:

Theorem 4:\textbf{Theorem 4:} If ab(modn)a \equiv b \pmod{n}, then acbc(modn)a-c \equiv b-c \pmod{n}.

If ab(modn)a \equiv b \pmod{n}, we know that ab=qna-b = qn for some integer qq. This means (ac)(bc)=ab=qn(a-c) - (b-c) = a-b = qn, so acbc(modn)a-c \equiv b-c \pmod{n}. \blacksquare

Theorem 5:\textbf{Theorem 5:} If ab(modn)a \equiv b \pmod{n}, and cd(modn)c \equiv d \pmod{n}, then acbd(modn)a-c \equiv b-d \pmod{n}.

We know that ab=qna-b = qn for some integer qq and cd=rnc-d = rn for some integer rr. Subtracting the equations gives (ac)(bd)=qnrn=(qr)n(a-c) - (b-d) = qn - rn = (q-r)n. This means that the difference of aca-c and bdb-d is a multiple of nn, so acbd(modn)a-c \equiv b-d \pmod{n}. \blacksquare

Multiplication\textbf{Multiplication}

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

Theorem 6:\textbf{Theorem 6:} If ab(modn)a \equiv b \pmod{n}, then acbc(modn)ac \equiv bc \pmod{n}.

If ab(modn)a \equiv b \pmod{n}, we know that ab=qna-b = qn for some integer qq. This means acbc=qcnac-bc = qcn, so acbc(modn)ac \equiv bc \pmod{n}. \blacksquare

There is also another proof of this:

We know that ab(modn), ab(modn),, ab(modn)c statements\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 a+a+a+a++ac "a"sb+b+b+b++bc "b"s\underbrace{a+a+a+a+\cdots + a}_{\text{c "a"s}} \equiv \underbrace{b+b+b+b+\cdots + b}_{\text{c "b"s}} or acbc(modn)ac \equiv bc \pmod{n}. \blacksquare

Theorem 7:\textbf{Theorem 7:} If ab(modn)a \equiv b \pmod{n}, and cd(modn)c \equiv d \pmod{n}, then acbd(modn)ac \equiv bd \pmod{n}.

We repeatedly use Theorem 6: Since aba \equiv b, acbcac \equiv bc, and since cdc \equiv d, bcbdbc \equiv bd. Therefore, acbcbdac \equiv bc \equiv bd, or acbd(modn)ac \equiv bd \pmod{n}. \blacksquare

Theorem 8:\textbf{Theorem 8:} If a1b1(modn)a_1 \equiv b_1 \pmod{n}, a2b2(modn)a_2 \equiv b_2 \pmod{n}, , akbk(modn)\cdots , \ a_k \equiv b_k \pmod{n} then a1a2akb1b2bk(modn)a_1 a_2 \cdots a_k \equiv b_1 b_2 \cdots b_k \pmod{n}.

We repeatedly use Theorem 7: Because a1b1(modn)a_1 \equiv b_1 \pmod{n}, a2b2(modn)a_2 \equiv b_2 \pmod{n}, we get a1a2b1b2(modn)a_1a_2 \equiv b_1b_2 \pmod{n} We also know a3b3(modn)a_3 \equiv b_3 \pmod{n}, so a1a2a3b1b2b3(modn)a_1a_2a_3 \equiv b_1b_2b_3 \pmod{n} Also, a4b4(modn)a_4 \equiv b_4 \pmod{n}, so a1a2a3a4b1b2b3b4(modn)a_1a_2a_3a_4 \equiv b_1b_2b_3b_4 \pmod{n} Continuing to do this will give a1a2akb1b2bk(modn)a_1 a_2 \cdots a_k \equiv b_1 b_2 \cdots b_k \pmod{n} \blacksquare

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

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 1241124 \equiv 1, 1342134 \equiv 2, 23223 \equiv 2, 49149 \equiv 1, 2351235 \equiv 1, and 13113 \equiv 1. Therefore, from Theorem 8, 12413423492351312211141(mod3)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 1\boxed{1} when divided by 33.

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

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

If xy(modn)x \equiv y \pmod{n}, then axay(modn)a^x \equiv a^y \pmod{n}.

However, taking n=3n = 3, a=2a =2, x=2x = 2, and y=5y = 5, we get 25(mod3)2 \equiv 5 \pmod{3}, but 221≢225(mod3)2^2 \equiv 1 \not\equiv 2 \equiv 2^5 \pmod{3}.

Problem 3:\textbf{Problem 3:} What is the remainder when 231234523^{12345} is divided by 2222?

From Theorem 9, since 231(mod22)23 \equiv 1 \pmod{22}, 23123451123451(mod22)23^{12345} \equiv 1^{12345} \equiv 1 \pmod{22}, so 231234523^{12345} leaves a remainder of 1\boxed{1} when divded by 2222.

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

240=(210)4=102442445762(mod1000)\begin{aligned}2^{40} &=& \left(2^{10}\right)^4 \\ &=& 1024^4 \\ &\equiv& 24^4 \\ &\equiv& 576^2 \pmod{1000}\end{aligned} We can write 5762576^2 as (500+76)(500+76)=250000+250076+7676=250000+76000+57760+5776776(mod1000)\begin{aligned}(500+76)(500+76) &=& 250000+2*500*76+76*76 \\ &=& 250000 + 76000 + 5776 \\ &\equiv& 0 + 5776 \\ &\equiv& 776 \pmod{1000}\end{aligned}. Since 2402^{40} leaves a remainder of 776776 when divided by 10001000, its last three digits are 776\boxed{776}.

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

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

We know that 201111(mod1000)2011 \equiv 11 \pmod{1000}, so 20112011112011(mod1000)2011^{2011} \equiv 11^{2011} \pmod{1000}. We can write 11201111^{2011} as (10+1)2011(10+1)^{2011} and use the Binomial Theorem to expand it. We get 112011=(10+1)2011=(20110)10201110+(20111)10201011++(20112010)10112010+(20112011)12011\begin{aligned} 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{aligned} However, all powers of 10 above 10210^2 are divisible by 10001000, so are 0(mod1000)0 \pmod{1000}. Therefore, we can reduce them to 00. All terms at the beginning are nullified, and we are left with (20112009)10212009+(20112010)10112010+(20112011)12011=100(20112)+10(20111)+1(20110)\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 (20112009)=(20112)\dbinom{2011}{2009} = \dbinom{2011}{2}, (20112010)=(20111)\dbinom{2011}{2010} = \dbinom{2011}{1}, and (20112011)=(20110)\dbinom{2011}{2011} = \dbinom{2011}{0}. We can write this as 100201120102+102011+110011102+1011+1=5500+110+1611(mod1000)\begin{aligned}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{aligned} \blacksquare

Note by Akshaj Kadaveru
5 years, 8 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

Michael Tang - 5 years, 8 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(modj)i\pmod{j} for 0ij10000\le i\neq j\le1000.

Cody Johnson - 5 years, 8 months ago

Log in to reply

0<ij100<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 - 5 years, 8 months ago

Log in to reply

And also CRT

Dinesh Chavan - 5 years, 8 months ago

Log in to reply

Great job! It helps!

Jordi Bosch - 5 years, 8 months ago

Log in to reply

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

Abhijeeth Babu - 5 years, 8 months ago

Log in to reply

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

Jordi Bosch - 5 years, 7 months ago

Log in to reply

If ab(modn) a \equiv b \pmod{n} implies ab=qn a - b = qn where q and n are integers, then is it true that ab(modq) a \equiv b \pmod{q} ?

Shabarish Ch - 5 years, 5 months ago

Log in to reply

yes. Just use the definition.

mathh mathh - 5 years 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 - 5 years, 2 months ago

Log in to reply

cool!

Fatin Farhan - 5 years, 7 months ago

Log in to reply

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

Calvin Lin Staff - 4 years, 10 months ago

Log in to reply

VERY nice !!!!!!!!!

Harsh Shrivastava - 5 years, 3 months ago

Log in to reply

@HARSH SHrivastava -Which class are you in?

Krishna Ar - 5 years, 1 month ago

Log in to reply

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

Harsh Shrivastava - 5 years, 1 month 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 - 5 years, 1 month ago

Log in to reply

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

Manish Mayank - 5 years 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 - 4 years, 8 months ago

Log in to reply

Shall we make all Theorems a little more users friendly!
a, b, α, β, c, m  all integers.a1b1(modm),   a2b2(modm)....anbn(modm).      Addition and SubtractionTheorem 1     a±cb±c(modm)Theorem 2     a1±a2±...±anb1±b2±...±bn(modm)   MultiplicationTheorem 3a     a1a2...anb1b2...bn(modm)    Theorem 3b     anbn(modm)\Large{a, ~b,~\alpha,~\beta,~c,~m~~ all~ integers. \\ \color{#D61F06}{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 - 4 years, 7 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...