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.
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.
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
@@khbye2411 services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvMy9hLzRjODgwODk0NDdiYTMxMTY1MmRhMTk4MTAzZDU0NWEwMDRhMGQzLnBkZg==&rn=aGFuZG91dHY0LnBkZg== This handout I wrote covers everything about elementary modular arithmetic, along with these questions and much more. It should help you develop a strong base.
@@martinepstein9826 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!
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.
@@LetsSolveMathProblems This is the first video I'm seeing on your channel. Subscribed! I loved your explanation for Euler Totient function! You can say that if p, q are prime factors of n, then total number of coprimes of p*q less than p*q are (p-1)(q-1) according to Chinese remainder theorem. Coprimes less than n would be (p-1)(q-1) * n/lcm(p,q) or (p-1)(q-1)*n/pq. Anyway, this video was great! Thank you!
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
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?
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.
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).
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.
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.
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.
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.
Stop.
@@newkid9807 why
I understood everything, I learned something - thanks a lot for this explanation!
I especially liked your pronunciation of the number twenty!!
Many Thanks. It helps me a lot in life to known how to calculate 2017 to the power of 2018 to the power 2019.
You aren't calculating that.... Just finding out last 2 digits!
I really needed this for a coding challenge. So glad I got recommended this!
First time I watched a video where I can honestly say I understood everything - made me so happy! Thanks for your great content :)
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.
Well...
What is the answer?
777
I am getting the answer to be 657...Are you sure it is 777?
Please reply I have been working on this one for long...please
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
8:50 I don't understand how taking mod(phi(25)) that is mod20 will reduce the power?
@@khbye2411 services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvMy9hLzRjODgwODk0NDdiYTMxMTY1MmRhMTk4MTAzZDU0NWEwMDRhMGQzLnBkZg==&rn=aGFuZG91dHY0LnBkZg==
This handout I wrote covers everything about elementary modular arithmetic, along with these questions and much more. It should help you develop a strong base.
17^40 = (17^20)^2 = 1^2 = 1 mod 25
@@aryanshshrivastava2650 thank you for the article!
@@martinepstein9826 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!
Where do you get these problems?
Man!
Mind blowing!!!
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.
@@LetsSolveMathProblems This is the first video I'm seeing on your channel. Subscribed! I loved your explanation for Euler Totient function! You can say that if p, q are prime factors of n, then total number of coprimes of p*q less than p*q are (p-1)(q-1) according to Chinese remainder theorem. Coprimes less than n would be (p-1)(q-1) * n/lcm(p,q) or (p-1)(q-1)*n/pq. Anyway, this video was great! Thank you!
LetsSolveMathProblems hey I made this problem cut the shit
@@LetsSolveMathProblems nice😏
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
wrong spelling but I think youtube is trying to tell you something...
Don't watch games before solving math, trust me, I learned that the hard way.
Nice and Useful. Thanks
In 12:24 why you didn't use Euler's theorem for 2018^2019^2020 mod25?
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?
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
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.
LetsSolveMathProblems hey fuck you
I wish he'd go a little slower instead. And explain the theorems he's using in between the lines. Couldn't understand half the stuff.
8:58 why you take mod 20
20 = phi (25)
Since 17^(2018^2019) =
17^(20q+r) by division algorithm which is equal to 17^r =
17^ (2018^2019 mod (20))
Make a vedio about gcd and lcm problems please and fundamental theorem of arithemetic
At 9:35 ,can we use CRT again with mod 4 and mod 5 ??
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).
I wonder what trick you could use to find the first 2 digits of that number instead of the last 2 is
That's not possible!
i can find only the units digit
can you consider same problems to find last three digits?
Sure you have to split each number mod 8 and mod 125 and apply CRT
I don't understand the line ( phi of 12 =12.1/2.2/3 =4 ) Please help me.
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.
the one speaking sounds like blackpenredpen
Bruh
How to find last three digits of 23^123
Please guys anyone have this in code in java or any language?
love you brother
Very nice!
Calculate Փ (440). Hint: Փ(pn ) = pn - p n-1 (can anyone help me with this answer and step by step procedure of this please)
The first 1:05 min make me scary
⭐️
Solution is too long.This can be done within 30 seconds without totient,without Chinese remainder theorem.
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.
I solved it before watching the video without CRT gyazo.com/865af49cbdf63d2a2b67bc7d334898eb let's go