I found this right after watcching your second video from four years ago about finding the last digit (as opposed to multiple last digits as in this video). I learned two new concepts here that were not in the other video. Presentation was really polished too.
07:18 I took an online class for Number Theory and never had someone explain it this plainly. You got my attention, and a new subscriber. Thank you so much!
Your passion and clarity are unparalleled. Excellent work. Want show a way that avoids the Euler totient function, relying only on modular arithmetic. The main ideas are to show 3^20==1(mod 100) and laws of exponents.(Totient function not needed) We can avoid the Euler Phi function in the following way: 3^5== 43 (mod 100), 3^10==43^2=1849==49 (mod 100) 3^20== 49^2=2401==1 (mod 100) So, since 3^20==1 (mod 100), 3^431 = ((3^20)^21)(3^11) == 3x3^10 = 3x49==47(mod 100) which means the last two digits of 3^431 are 47
Great video, I stumbled upon a problem when i was doing programming exercises that got me quite intrigued, but never figured it out. It was quite similar to what you did in this video, it states: "Find the N-th number of N^N". For example 14-th number of 14^14 is 8 and with values larger than 10 its hard to hardcode :D Anyway, did a little research and i found the Euler's theorem and Euler's totient function, somehow i had a feeling that it would be relatable to my problem but couldn't figure out how. If you could help would mean the world to me, because this problem is bugging me for a long time :)) plus i thing it would be an interesting video
Here's what I came up with. Hope it helps! For any positive integer 𝑛, we can write 𝑛^𝑛 = 𝑎⋅10^𝑚 where 𝑎 ∈ [1, 10), 𝑚 ∈ ℕ. Note that the number of digits of 𝑛^𝑛 is 𝑚 + 1. Taking log₁₀ of both sides we get 𝑛 log 𝑛 = log(𝑎) + 𝑚. For the special case 𝑎 = 1, it's not too difficult to show that 𝑛 ∈ {1, 10, 100, 1000, ...}, for which the 𝑛-th digit of 𝑛^𝑛 is 0 (except for 𝑛 = 1, since the 1st digit of 1^1 is 1). In all other cases, 𝑎 ∈ (1, 10) ⇒ log(𝑎) ∈ (0, 1) ⇒ ⌈𝑛 log 𝑛⌉ = 𝑚 + 1. This means that the 𝑛-th digit from the beginning is the (⌈𝑛 log 𝑛⌉ − 𝑛 + 1)-th digit from the end. For example, 𝑛 = 14 ⇒ ⌈14 log 14⌉ − 14 + 1 = 4, so the 14th digit of 14¹⁴ is also the 4th-to-last digit of 14¹⁴. So, if we could calculate 14¹⁴ mod 10,000 we could just take the first digit of the result and that would be our answer. The way to do this is to write 14¹⁴ as a product of powers that we actually can calculate, e.g. 14⁷⋅14⁷, because 14¹⁴ mod 10000 = ((14⁷ mod 10000)⋅(14⁷ mod 10000)) mod 10000 = 8016. Just for clarity, we could also do ((((14⁵ mod 10000)⋅(14⁵ mod 10000)) mod 10000)⋅(14⁴ mod 10000)) mod 10000.
The group of units of 100 is isomorphic to Z_2×Z_20 so x^20 is always congruent to 1 if x is relatively prime to 100... 3^431 is congruent to 3^11 which you can find on your own without using Chinese remainder theorem...
Becase gcd (3,100)=1 3^341 = 3^ (341 mod 40) ( mod 100) We can mod the base 100 and the power mod phi(100) This can be upplied even for stack power 3^(55^66) The higher power will be mod phi(phi(100) = 16 Also there is easier equation to find phi If prime facter of n are p1, p2... , pk Phi (n ) = n × (p1 -1)/p1 × (p2 -1)/p2 .....× (pk -1)/ pk For example the prime factor of 100 are 2 and 5 Phi(100) = 100 × 1/2 × 4/5 = 40 Another equation Phi(n) = n (1-1/p1) (1-1/p2) ..(1-1/pk) Phi(100) = 100(1-1/2)(1-1/5) = 100× 1/2 × 4/5=40
I like my version better. since it works in more cases. This only works when the number and the base are relatively prime. For instance 4 and 27. Mine works for situations like 20 and 8 as well as all cases where Euler's Totient Function works. I actually figured out mine from scratch before I even heard of Euler's Totient function or Euler's theorem. I actually started with trying to find a method for making code using numbers to different powers, but I ended up with a pattern instead.
pretty much instead of [ a^nϕ(b) ≡ 1 mod b ] it is [ a^nϕ(b)+1 a mod b ] if anyone knows how to denote the highest prime power that is a factor of b let me know.
the situations where this could work compared to the Euler's Totient Function is a bit complicated to describe. Lets say that is a set containing all of the highest power of prime factors of B which are factors of B. Examples: = {4,5} = {4, 25} = {7, 16, 25} If ∀m ∈ , m|a or gcf(m,a) = 1, then a^nϕ(b)+1 a mod b
Thank you for this video. Very informative. I struggled at the step of 3^31. Is there a way to quickly calculate that 3^15 is equivalent to 7 mod 100? I began making a table of powers of 3 mod 100, but realized I was using quite a bit of time. I didn't see a pattern. Once again, GREAT video!
Just discovered 3^20 is equivalent to 1 mod 100. This will quickly reduce the problem to 3^11. Then , we can use 3^3 * 3^3 * 3^3 *3^1 or some other combination.
Yes. 20 is called the order of 3 (mod100). It is the smallest exponent that gives 1. I didn't want to teach that in the video. I'll show that another time.
gcd means the greatest common divider. Let's consider the following: gcd (2,6). What are the factors of 2? 1 and 2. What are the factors of 6? 1, 2, 3 and 6. Since the greatest factor of 2 is 2 and 2 is one of the factors of 6, the answer to the aforementioned would be 2.
You really think 3^15 is easy to do manualy? That's quite not elegant to do. It takes time, and with higher numbers you would for sure not be able to compute this manually
I found this right after watcching your second video from four years ago about finding the last digit (as opposed to multiple last digits as in this video). I learned two new concepts here that were not in the other video. Presentation was really polished too.
07:18 I took an online class for Number Theory and never had someone explain it this plainly. You got my attention, and a new subscriber. Thank you so much!
Thank you, sir. You are an incredible teacher, and I am currently preparing for my GRE. Your teaching style is truly exceptional.
Only video I got for my tomorrow exam , its really helpful 🙂
Good luck tomorrow!
You're an Outstanding teacher! Glad I've found your channel!
Your passion and clarity are unparalleled. Excellent work.
Want show a way that avoids the Euler totient function, relying only on modular arithmetic. The main ideas are to show
3^20==1(mod 100) and laws of exponents.(Totient function not needed)
We can avoid the Euler Phi function in the following way:
3^5== 43 (mod 100), 3^10==43^2=1849==49 (mod 100)
3^20== 49^2=2401==1 (mod 100)
So, since 3^20==1 (mod 100), 3^431 = ((3^20)^21)(3^11) == 3x3^10 = 3x49==47(mod 100)
which means the last two digits of 3^431 are 47
new subscriber best teaching for free of cost hats off to u sir
I so much love your teaching 😉😉
This man just saved my life ❤
Great video, I stumbled upon a problem when i was doing programming exercises that got me quite intrigued, but never figured it out. It was quite similar to what you did in this video, it states: "Find the N-th number of N^N". For example 14-th number of 14^14 is 8 and with values larger than 10 its hard to hardcode :D
Anyway, did a little research and i found the Euler's theorem and Euler's totient function, somehow i had a feeling that it would be relatable to my problem but couldn't figure out how.
If you could help would mean the world to me, because this problem is bugging me for a long time :)) plus i thing it would be an interesting video
Here's what I came up with. Hope it helps!
For any positive integer 𝑛, we can write
𝑛^𝑛 = 𝑎⋅10^𝑚
where 𝑎 ∈ [1, 10), 𝑚 ∈ ℕ.
Note that the number of digits of 𝑛^𝑛 is 𝑚 + 1.
Taking log₁₀ of both sides we get
𝑛 log 𝑛 = log(𝑎) + 𝑚.
For the special case 𝑎 = 1, it's not too difficult to show that 𝑛 ∈ {1, 10, 100, 1000, ...}, for which the 𝑛-th digit of 𝑛^𝑛 is 0 (except for 𝑛 = 1, since the 1st digit of 1^1 is 1).
In all other cases,
𝑎 ∈ (1, 10) ⇒ log(𝑎) ∈ (0, 1) ⇒ ⌈𝑛 log 𝑛⌉ = 𝑚 + 1.
This means that the 𝑛-th digit from the beginning is the (⌈𝑛 log 𝑛⌉ − 𝑛 + 1)-th digit from the end.
For example, 𝑛 = 14 ⇒ ⌈14 log 14⌉ − 14 + 1 = 4,
so the 14th digit of 14¹⁴ is also the 4th-to-last digit of 14¹⁴.
So, if we could calculate 14¹⁴ mod 10,000 we could just take the first digit of the result and that would be our answer.
The way to do this is to write 14¹⁴ as a product of powers that we actually can calculate,
e.g. 14⁷⋅14⁷,
because 14¹⁴ mod 10000 = ((14⁷ mod 10000)⋅(14⁷ mod 10000)) mod 10000 = 8016.
Just for clarity, we could also do
((((14⁵ mod 10000)⋅(14⁵ mod 10000)) mod 10000)⋅(14⁴ mod 10000)) mod 10000.
@@jumpman8282 Thank you, this is very helpful :)
@@jumpman8282 Thank you, that's really helpful :)
Thank you. this will help me in my yearly. Earned a sub
thanks this is so helpful, and so well-explained!
This was awesome, thank you! CZcams has some awesome teachers on it!
That was very interesting, thank you!
To Be Honest, BRILLIANT!!
best math video i have ever seen
The group of units of 100 is isomorphic to Z_2×Z_20 so x^20 is always congruent to 1 if x is relatively prime to 100... 3^431 is congruent to 3^11 which you can find on your own without using Chinese remainder theorem...
Becase gcd (3,100)=1
3^341 = 3^ (341 mod 40) ( mod 100)
We can mod the base 100 and the power mod phi(100)
This can be upplied even for stack power
3^(55^66)
The higher power will be mod phi(phi(100) = 16
Also there is easier equation to find phi
If prime facter of n are p1, p2... , pk
Phi (n ) = n × (p1 -1)/p1 × (p2 -1)/p2 .....× (pk -1)/ pk
For example the prime factor of 100 are 2 and 5
Phi(100) = 100 × 1/2 × 4/5 = 40
Another equation
Phi(n) =
n (1-1/p1) (1-1/p2) ..(1-1/pk)
Phi(100) = 100(1-1/2)(1-1/5)
= 100× 1/2 × 4/5=40
I like my version better. since it works in more cases. This only works when the number and the base are relatively prime. For instance 4 and 27. Mine works for situations like 20 and 8 as well as all cases where Euler's Totient Function works. I actually figured out mine from scratch before I even heard of Euler's Totient function or Euler's theorem. I actually started with trying to find a method for making code using numbers to different powers, but I ended up with a pattern instead.
pretty much instead of [ a^nϕ(b) ≡ 1 mod b ] it is
[ a^nϕ(b)+1 a mod b ]
if anyone knows how to denote the highest prime power that is a factor of b let me know.
the situations where this could work compared to the Euler's Totient Function is a bit complicated to describe.
Lets say that is a set containing all of the highest power of prime factors of B which are factors of B. Examples:
= {4,5}
= {4, 25}
= {7, 16, 25}
If ∀m ∈ , m|a or gcf(m,a) = 1, then a^nϕ(b)+1 a mod b
Please keep posting. I'll look at your work. Sounds quite interesting.
Yesss sirr, thankyou so much
how do you know so fast that the last two digits of 3^15 are 07? is there some trick?
Nice video ❤
Thank you 👍🏿
Thank you for this video. Very informative. I struggled at the step of 3^31. Is there a way to quickly calculate that 3^15 is equivalent to 7 mod 100? I began making a table of powers of 3 mod 100, but realized I was using quite a bit of time. I didn't see a pattern. Once again, GREAT video!
You don't have to use 3^15. You can use 3^3 but you'll be getting 27 ten times . The only shortcut is experience or luck 😀
@@PrimeNewtons Thanks!
Just discovered 3^20 is equivalent to 1 mod 100. This will quickly reduce the problem to 3^11. Then , we can use 3^3 * 3^3 * 3^3 *3^1 or some other combination.
Yes. 20 is called the order of 3 (mod100). It is the smallest exponent that gives 1. I didn't want to teach that in the video. I'll show that another time.
@@PrimeNewtons Thanks! I look forward to that upcoming video!
Thank you so much sir
Sir, so what should we use if gcd of (a,n) is not equivalent to 1 or if they aren’t co-prime
gcd means the greatest common divider. Let's consider the following: gcd (2,6). What are the factors of 2? 1 and 2. What are the factors of 6?
1, 2, 3 and 6. Since the greatest factor of 2 is 2 and 2 is one of the factors of 6, the answer to the aforementioned would be 2.
i used binomial theorem and got the same answer
here for tomorrows discreet mathematics exam
Enjoy well
Go in more depth for number theory please. It is my weakest area 😭, and its really annoying me.
Email me some problems
Tq sir
You really think 3^15 is easy to do manualy? That's quite not elegant to do. It takes time, and with higher numbers you would for sure not be able to compute this manually
That's what I was thinking too... an alternative would be to calculate 3^6 by hand
(729) and then get 29^5, could work as well.
But i think the last digit for this number should be 9 how come you are getting 7
Don't say 'I think'. Say 'I know'.