Find the last two digits.

Using Euler's generalization of Fermat's little theorem we look at a classic number theory problem.

If you are going to use an ad-blocker, considering using brave and tipping me BAT!

Books I like:

Abstract Algebra:

Differential Forms:

Number Theory:

Analysis:

Calculus:

My Filming Equipment:

[sholinwright]

You’re the best. I love these things; it explores a math area I wasn’t exposed to in engineering classes.

[prathikkannan]

Im still kinda confused around the 8:30 mark where he takes mod phi(n) and then mod phi(phi(n)) for the other power. Can someone explain this clearly?
Ill think about it more in the meanwhile :)

[goodplacetostop]

12:26

85K subs also. 15K more before the silver play button...

[murkbaccafett]

I haven't been in a math class since 1997 (I am a chemistry professor), but I've always had a fondness for it. I'd never heard of these concepts before, but your explanation is amazing. I actually could follow along for what that's worth. Kudos!

[ccbgcfe]

This channel is one of the best math channels in youtube, keep making great content!

[followNoxville]

Solution using what, when I used to do maths olympiads, we were told were called 'cyclic patterns'.

Let d(x) = x mod 100.

Evaluate d(123^n) for increasing n until, until d(123^n) == 23. The first occurrence of this is n = 21, so we know the cyclic length of 123 is 21-1 = 20.

We now just need to know 789^456 mod 20, since d(123^n) == d(123^m) if n == m (mod 20)

789^456 mod 20
= ((789 mod 20)^456) mod 20 (modular exponentiation property)
= (9^456) mod 20
= (9^450 * 9^6) mod 20
= [(9^450 mod 20) * (9^6 mod 20)] mod 20
(removed a mod 20 due to idempotence]
= [((9^10 mod 20)^45 mod 20) * (9^6 mod 20)] mod 20
note that in modulo 20, 9^10 = 9^6 = 1, thus
[((9^10 mod 20)^45 mod 20) * (9^6 mod 20)] mod 20 = 1

As a result d(123^789^456) = d(123^1) = 23.

[CM_France]

Hi,

For fun:
1 "so may be the best thing to do is",
1 "now, the next thing that I want to do",
1 "the first thing that I want to notice",

2 "let's go ahead and",
1 "let's may be go ahead and",

3 "great".

[arjjanwalia]

7:40
At this point, you can just reduce the exponent (mod 8) since (mod 16) doesn't have any primitive roots. 456 is congruent to 0(mod 8) which means the problem just simplifies to finding last 2 digits of 123, which are 23.

[maelhostettler]

I personaly beginned by reducing mod 25 and mod 4. I got 3 mod 4 and 23 mod 25 wich obviously gave me a bit quicker result of 23 mod 100

[zenwheat]

I love how straight to the point you are while going through these. I often have to pause to look up theorems I'm not familiar with but that's a better way for me to learn rather than have you explain every little detail of the solution

[MrRyanroberson]

so we're looking for 23^(789^456) mod 100.
(100a+b)^x mod 100 = b^x mod 100
2-digit cycle of 23 from 0: [01, 23, 29, 67, 41, 43, 89, 47, 81, 63, 49, 27, 21, 83, 09, 07, 61, 03, 69, 87]; length 20.
so 23^(20a+b) mod 100 = 23^b mod 100
so we're looking for 23^(789^456 mod 20) mod 100
(20a+b)^x mod 20 = b^x mod 20
so we're looking for 23^(9^456 mod 20) mod 100
mod 20 cycle for 9 from 0: [01, 09]; length 2.
so we're looking for 23^(9^(456 mod 2) mod 20) mod 100
that's 23^(9^0 mod 20) mod 100 = 23 mod 100 = 23

[akanegally]

Hello, I use a different technique cause I didn't know about the generalisation of fermat little therorem.

I noticed that 123^20 = 1 mod 100.
Then I tried to calculate 789^456 mod 20

I noticed that 789^456=9^456 mod 20
Obviously 9^2 mod 20 = 1
So I reformulate like this 9^456 mod 20=(9^2)^278 mod 20
which is equal to 1^278 mod 20= 1 mod 20

To conclude 123^789^456 mod 100= 23^20^(something) * 23 mod 100
Which is equal to 1^something*23 mod 100 = 23 mod 100

So the last two digit are 2 and 3.

The hard guess was 123^20 = 1 mod 100
But I was dit it progressively like this :
23^2=43 mod 100
23^4= 41 mod 100
23^8= 81 mod 100
23^10 = 49 mod 100 <-- Bingo cause -51*-51=1 mod 100

Nice problem, If 100 was prime, I would have used femat little therorem, I didn't know about the generalisation.
Thank you for showing up this method. I will definitely get a look at your course.

[raismin]

how i did it:
i just need the last two digit, so i take 123 in mod 10 and this will give me 23
so i put down the list of power of 23 in mod 10 and i see that they will repeat itself after 20 powers
23, 29, 67, 41, 43, 89, 47, 81, 63, 49, 27, 21, 83, 9, 7, 61, 3, 69, 87, 1

at this poit i need to find 789^456 in mod 20 (the number of powers before the pattern reapeat itself)
so i take first of all 89 in mod 20 and that give me 9 (or -11 that is what he did find)
so i take thos 9 powers in mod 20 and i see they repeat after 2 times (9, 1)
so i need to take 456 in mod 2 and that's give me 0 (or for semplicity 2)
so i need to take the second power of the array (9, 1) and that's 1
so i need to take he 1st power of the 23 powers array and that's 23

so the result is 23

it's kind of funny how i did it without knowing basically nothing about number theory and still did a provess quite similar lol

[canonpi]

you don't necessarily have to calculate mod 16

789^2=1(mod 40)
therefore, 789^456-1=40a for some a.
123^40a=1(mod 100)
123^(40a+1)=123=23(mod 100)

[MrKrabs-xftr]

I'd just like to say that at 1:18, shouldn't it be less than n rather than less than or equal to n? I believe that's what the totient function attempts to find. Regardless, amazing video, I loved it.

[TechToppers]

Can you please present the proof of Fermat's little theorem with Multinomial theorem? Please... There is no good explanation on YouTube.

[srijanbhowmick]

Can't believe I did this myself and that too in under 5 minutes! Michael's videos really help in problem-solving.

[gregoryshipley]

I love you're channel. I often use your videos as staring points for challenge problems in my math classes. However I think there is a much easier way to solve:

mods are cyclical
123^n mod 100 has a period of 20
123^x mod 100 = 123^(x+20) mod 100

123^(789^456) mod 100 = 123^( (789^456) mod 20 )

789 mod 20 only has a period of 2
789^x mod 20 = 789^(x+2) mod 20

456 mod 2 = 0
789^456 mod 20 = 789^0 mod 20 =1
123^(789^456) mod 100 = 123^1 mod 100 = 123 mod 100 =23

Perhaps a bit more number crunching to work out the periods but it avoids the totient function, and any of the number theory proofs about how it works with mods.

[Zibeline]

I want to like, but there are already 123 likes, hmmm...

[Problematica.]

May be is easy for you but.
Find the last three digits of the number 19^97