# Intro to Chinese Remainder Theorem and Euler's Totient Theorem via a Challenging Problem

Share
Embed
• Published on Nov 29, 2018
• Let's acquaint ourselves with two of the most important theorems in elementary number theory (and competition math like AMC/AIME) by solving an interesting problem. The only prerequisite is the basic knowledge of modular arithmetic (what it is, how it behaves under addition/multiplication, some intuition on number theory).
Congratulations to Essentials of Math, Gustavo Exel, Devansh Sehta, Minh Cong Nguyen, Prathmesh, Eliot Argüello, Jack Miller, NoName, Daulian Doge, and Benjamin Wang for successfully solving this challenge question! Essentials of Math was the first person to solve the question.
Your support is truly a huge encouragement.
Please take a second to subscribe in order to send us your valuable support and receive notifications for new videos!
Every subscriber and every like are wholeheartedly appreciated.
For more Weekly Math Challenges:

## Comments • 53

• Sitanshu Chaudhary 22 days ago +1

8:58 why you take mod 20

• Omar 17 days ago

20 = phi (25)
Since 17^(2018^2019) =
17^(20q+r) by division algorithm which is equal to 17^r =
17^ (2018^2019 mod (20))

• Arnav kumar Sinha Month ago

At 9:35 ,can we use CRT again with mod 4 and mod 5 ??

• Varun Gupta 29 days ago

You could. It is probably easier that way because you know that it is obviously 0 (mod 4) and taking 2018 (mod 5) gets you 3. The 3s cycle every four so it's pretty easy to find that the whole thing is 2 (mod 5), so it is 12 (mod 20).

• shashvat singh 2 months ago +1

i can find only the units digit

• 3ch0 4 months ago

First time I watched a video where I can honestly say I understood everything - made me so happy! Thanks for your great content :)

• jessie chen 5 months ago +1

You do this with mod 4 and mod 25 instead of any other numbers because they are the only relatively prime ones, right? why not use mod 4 at the beginning?

• Ashmit Dutta 6 months ago

Isn’t Chinese remainder theorem:
N == n (mod x)
N == n (mod y)
Thus N == n (mod xy) where, gcd (x, y)=1.
So isn’t this practically more of an intro of Euler Totient Theorem, and solving linear modular congruence rather than CRT? Or is CRT basically solving a system of linear congruences?

• magnifecent 6 months ago

Hello can you consider doing some math olympiad questions. There are some of the hardest questions. Thanks

• Elle Lawliet 6 months ago +2

Nice and Useful. Thanks

• mahesh waran 6 months ago +1

Where do you get these problems?
Man!
Mind blowing!!!

• LetsSolveMathProblems  6 months ago +3

With the exception of approximately 12 problems (out of 69 so far), all Weekly Math Challenge problems--including this one--were made by myself. The exceptions owe their existence to my younger brother or both of us working in conjunction.

• Martin Epstein 6 months ago +5

I'm grateful to see the Chinese remainder theorem in action! Using it isn't so bad, but my eyes glaze over whenever I try to read the formal statement.

• Martin Epstein 6 months ago +2

I must have learned that you can calculate the totient like that but I completely forgot. I reasoned that for t(100) you start with 100 numbers, you take away 50 multiples of 2 and 20 multiples of 5 so you have 30 numbers left, but you took away the 10 multiples of 10 twice so you have to add those back, for a total of 40. I wonder if there's an obvious way to see that my method simplifies to your method. Equivalently, for primes p,q,r,... how can we show that
1 - 1/p - 1/q - 1/r - ... + 1/(pq) + 1/(pr) + ... - 1/(pqr) - ... = (p-1)/p * (q-1)/q * (r-1)/r * ...
Ah I see. Going from right to left is pretty easy. If we rewrite the RHS as (1-1/p) (1-1/q) (1-1/r)... and expand in the most straightforward way we get the LHS exactly. Turns out p,q,r,... didn't need to be prime, whoops.

• Aryansh Shrivastava 6 months ago +1

Hi @LetsSolveMathProblems I have a handout on modular arithmetic that covers all of this and more, along with the very basics, with comprehensive examples. Below is the link, in case anyone wants to see it:

• Moslema Sultana 6 months ago +1

love you brother

• Kh Bye 6 months ago +2

10:07 is this a routine kind of question/thought process that you would go through in number theory? I'm shocked by the speed man

• LetsSolveMathProblems  6 months ago +3

It is one of the key problem-solving techniques that could be used for problems similar to the one in the video (where we wish to evaluate a^b (mod c) ) because it is always guaranteed to work. To see why the sequence must eventually repeat in our problem, note that there are only 20 possible remainders when we divide by 20 (0, 1, 2, ..., 19). Since the sequence is infinitely long (specifically, longer than 20), we obviously must have at least one remainder that shows up twice, and the sequence will repeat afterward. (This argument generalizes to positive integers other than 20.) Of course, if we are concerned with 23^x (mod 1567), trying to find the pattern by hand would be very inefficient. However, when we have small numbers as the base of the exponent and the modulus (as in the video), it could be a viable method.

• Kh Bye 6 months ago +2

8:36 sorry but what am I suppose to know about 17^40? (I only know a little bit about number theory). Bcos 17^20=1mod25, then 17^40=1mod25? I can't make the connection

• Arnav kumar Sinha Month ago

@Aryansh Shrivastava the link is not opening
It is giving error 404

• LetsSolveMathProblems  6 months ago +5

Here is a nice proof of the theorem we need to support the claims made in the video: (I personally first encountered this proof in "Elementary Number Theory" by Charles Vanden Eynden; it is an outstanding book for a beginner in elementary number thoery.)

Theorem: If a == b mod n and c == d mod n, then ac == bd mod n.
Proof: We know that n divides both (a-b) and (c-d) because a == b mod n and c == d mod n. (In fact, this is how modular congruence is sometimes defined.) It follows that n divides (a-b)*c + (c-d)*b. This expression is equal to ac - bd, so n divides ac - bd. The desired assertion follows.

So, if we want to find the smallest positive integer congruent to 31*52 mod 5, we don't have to start by multiplying 31 and 52. We may begin by replacing 31 and 52 with numbers that are equal to them (mod 5)--For example, 1 and 2, respectively. Thus, 31*52 == 1*2 = 2 mod 5, and we are quickly done. The computations done in the video can be justified similarly.

Hope this helps. =)

• Martin Epstein 6 months ago

Exactly. That's what makes modular arithmetic so powerful. If a = b mod n and c = d mod n then a+c = b+d mod n and ac = bc mod n. As far as addition, subtraction, and multiplication of integers is concerned "equivalent mod n" really does mean equivalent.

• Kh Bye 6 months ago +2

@Martin Epstein ok I think more questions than answers are popping out of my head now...So in modular arithmetic you're allowed to substitute the 17^20mod25 with 1 bcos they are identical (in terms of mod25)? And 1^2 is still 1mod25...
I need to read more on basic modular arithmetic before I even ask my questions hahaha thanks for answering!

• Kh Bye 6 months ago

@Aryansh Shrivastava thank you for the article!

• Vatsal Gupta 6 months ago +1

Whack

• adandap 6 months ago +22

Sometimes you post problems for which I know the requisite technical tricks (like the ants on an octahedron problem), and that's fun. Sometimes I have to work things out from first principles, and those are more fun. Best of all are ones where I have no idea of the tricks required and have to learn a bunch of new things. This is one of those. I don't think I've ever heard the word 'totient' before, and CRT is a cathode ray tube for a physicist of my vintage. :) Thanks for the chance to acquaint myself with some new mathematical friends.

• Brian talks about 6 months ago

Hey wanna come to my channel and solve a problem? I encoded bitcoin in the answer. So if u solve it first... u win!

• batman rules 6 months ago +2

Make a vedio about gcd and lcm problems please and fundamental theorem of arithemetic

• Marvin Lee 6 months ago +5

Here's a similar problem: find the last three digits of 2017^2017^2017^...^2017 where there are 2017 of the the 2017's in the expression.

• Manuele Pedicillo 6 months ago

@Sudheer Thunga oh ok sorry, I misunderstood, I'm not english

• Sudheer Thunga 6 months ago

@Manuele Pedicillo I meant to say that I was solving it in a free period in school today in a free class

• Manuele Pedicillo 6 months ago

@Sudheer Thunga And you do these things at school?? It's crazy man

• Sudheer Thunga 6 months ago +1

@Manuele Pedicillo I'm 14

• Manuele Pedicillo 6 months ago +1

@Sudheer Thunga Only one question, how old are you?