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

Показать описание

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:

Рекомендации по теме

Комментарии

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.

martinepstein

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.

adandap

the one speaking sounds like blackpenredpen

asabelesabelo

I understood everything, I learned something - thanks a lot for this explanation!

I especially liked your pronunciation of the number twenty!!

keinKlarname

In evening when I get this question from a book I can, t solve it
In night when I open you tube this vedio was in top.
And the question is same.
What a coencidence

AmanKumar-loiz

Many Thanks. It helps me a lot in life to known how to calculate 2017 to the power of 2018 to the power 2019.

dunabogdany

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.

mangler

I really needed this for a coding challenge. So glad I got recommended this!

StrangePerson

Solution is too long.This can be done within 30 seconds without totient, without Chinese remainder theorem.

sudhirsirohi

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?

jessiechen

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

maheshwaran

You go slow for the easy introductory part, and then too fast for the more complicated part. You do not grasp how to teach to the mind of student who cannot go as fast as your mind.

barryzeeberg

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

BfhChaosXX

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

khbye

How to find last three digits of 23^123

VinodKumar-yeii

I wonder what trick you could use to find the first 2 digits of that number instead of the last 2 is

tonistack

Calculate Փ (440). Hint: Փ(pn ) = pn – p n–1 (can anyone help me with this answer and step by step procedure of this please)

b.vinith

I don't understand the line ( phi of 12 =12.1/2.2/3 =4 ) Please help me.

qmomolympiad

In 12:24 why you didn't use Euler's theorem for 2018^2019^2020 mod25?

elie.makdissi

Please guys anyone have this in code in java or any language?

alaala

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

The Chinese Remainder Theorem made easy

Chinese Remainder Theorem | Sun Tzu's Theorem

The Chinese Remainder Theorem (Solved Example 1)

Chinese Remainder Theorem and Cards - Numberphile

Chinese Remainder Theorem

30. Chinese Remainder Theorem Introduction. (Part-1)

Chinese Remainder Theorem

A Crash Course on the Chinese Remainder Theorem

Sol ch 3 (fermant; Wilson and Chinese remainder theorem)

Number Theory | Chinese Remainder Theorem Proof

Chinese Remainder Theorem, 2-minute Method

Number Theory | Chinese Remainder Theorem: Example 4

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

Chinese remainder theorem｜Dr.egg

Number Theory 53 - The Chinese Remainder Theorem - Introduction

The Chinese Remainder Theorem (Solved Example 2)

Number Theory | Chinese Remainder Theorem: Example 1

Number Theory: Chinese Remainder Theorem

Chinese Remainder Theorem -- Number Theory 11

System of congruences, modular arithmetic

Number Theory | Chinese Remainder Theorem: Example 3

Learn Chinese Remainder Theorem using Sun Tzu's Problem | Number Theory for Math Olympiad

Chinese Remainder Theorem with NUMERICAL in Cryptography | Abhishek Sharma

Decrypting RSA Using the Chinese Remainder Theorem