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

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:

usclip.net/p/PLpoKXj-PWCbaDXYHES37_zX4O-kCWxguM

Sitanshu Chaudhary22 days ago^{+1}8:58 why you take mod 20

Omar17 days ago20 = 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 SinhaMonth agoAt 9:35 ,can we use CRT again with mod 4 and mod 5 ??

Varun Gupta29 days agoYou 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 singh2 months ago^{+1}i can find only the units digit

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

jessie chen5 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 Dutta6 months agoIsn’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?

magnifecent6 months agoHello can you consider doing some math olympiad questions. There are some of the hardest questions. Thanks

Elle Lawliet6 months ago^{+2}Nice and Useful. Thanks

mahesh waran6 months ago^{+1}Where do you get these problems?

Man!

Mind blowing!!!

LetsSolveMathProblems6 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 Epstein6 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 Epstein6 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 Shrivastava6 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:

services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvMy9hLzRjODgwODk0NDdiYTMxMTY1MmRhMTk4MTAzZDU0NWEwMDRhMGQzLnBkZg==&rn=aGFuZG91dHY0LnBkZg==

Moslema Sultana6 months ago^{+1}love you brother

Kh Bye6 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

LetsSolveMathProblems6 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 Bye6 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 SinhaMonth ago@Aryansh Shrivastava the link is not opening

It is giving error 404

LetsSolveMathProblems6 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 Epstein6 months agoExactly. 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 Bye6 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 Bye6 months ago@Aryansh Shrivastava thank you for the article!

Vatsal Gupta6 months ago^{+1}Whack

adandap6 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 about6 months agoHey wanna come to my channel and solve a problem? I encoded bitcoin in the answer. So if u solve it first... u win!

batman rules6 months ago^{+2}Make a vedio about gcd and lcm problems please and fundamental theorem of arithemetic

Marvin Lee6 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 Pedicillo6 months ago@Sudheer Thunga oh ok sorry, I misunderstood, I'm not english

Sudheer Thunga6 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 Pedicillo6 months ago@Sudheer Thunga And you do these things at school?? It's crazy man

Sudheer Thunga6 months ago^{+1}@Manuele Pedicillo I'm 14

Manuele Pedicillo6 months ago^{+1}@Sudheer Thunga Only one question, how old are you?