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:
    usclip.net/p/PLpoKXj-PWCbaDXYHES37_zX4O-kCWxguM

Comments • 53

  • Sitanshu Chaudhary
    Sitanshu Chaudhary 22 days ago +1

    8:58 why you take mod 20

    • Omar
      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
    Arnav kumar Sinha Month ago

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

    • Varun Gupta
      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
    shashvat singh 2 months ago +1

    i can find only the units digit

  • 3ch0
    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
    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
    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
    magnifecent 6 months ago

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

  • Elle Lawliet
    Elle Lawliet 6 months ago +2

    Nice and Useful. Thanks

  • mahesh waran
    mahesh waran 6 months ago +1

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

    • LetsSolveMathProblems
      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
    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
    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
    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:
    services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvMy9hLzRjODgwODk0NDdiYTMxMTY1MmRhMTk4MTAzZDU0NWEwMDRhMGQzLnBkZg==&rn=aGFuZG91dHY0LnBkZg==

  • Moslema Sultana
    Moslema Sultana 6 months ago +1

    love you brother

  • Kh Bye
    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
      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
    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
      Arnav kumar Sinha Month ago

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

    • LetsSolveMathProblems
      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
      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
      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
      Kh Bye 6 months ago

      @Aryansh Shrivastava thank you for the article!

  • Vatsal Gupta
    Vatsal Gupta 6 months ago +1

    Whack

  • adandap
    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
      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
    batman rules 6 months ago +2

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

  • Marvin Lee
    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
      Manuele Pedicillo 6 months ago

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

    • Sudheer Thunga
      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
      Manuele Pedicillo 6 months ago

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

    • Sudheer Thunga
      Sudheer Thunga 6 months ago +1

      @Manuele Pedicillo I'm 14

    • Manuele Pedicillo
      Manuele Pedicillo 6 months ago +1

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