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
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.
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
i approached this is a very different way. successivly multiplied by 3 simply discarding the higher digits. (effectively modulo 100). this produced a series of 20 values. Taking 431 modulo 20 picked the 11th term of the series which was 47 Here is the whole series: 03 09 27 81 43 29 87 61 83 49 [47] 41 23 69 07 21 63 89 67 01
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...
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.
Hello, it's me again :) I'm writing this because i found another solution to the problem and i thought that you might find it interesting I'll be using 14^14 as an example 14 in base 2 = 1110 (2^8 + 2^4 + 2^2 + 2^0) Then i can writhe the expression as 14^8 * 14^4 * 14^2 (since exponents sum when the base is multiplied by itself) Then finding the length of the number by using Floor[log10(n^n) + 1] will convert to Floor[n*log10(n) + 1] which is 17 Then starting from the 14^2 to the 14^8 will solve the issue and since we need to modulo the whole thing we can even strip the number by 10^4 digits with each calculation 14^1 = 14 (don't include it in the final answer, because ls1b is 0) 14^2 = 196 mod 10 000 = 196 14^4 = (14^2)^2 = 38 416 mod 10 000 = 8 416 14^8 = (14^4)^2 = 70 829 056 mod 10 000 = 9 056 14^16 is not calculated because it exceeds our power 14 Then at the end we just multiply everything and mod the thing again, because the properties of modulo and the result should look like this 9 056 * 8 416 * 196 = 14,938,198,016 mod 10 000 = 8 016 And the 1st digit of that number is the n-th digit of the n^n-th number
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.
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.
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
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
Thank you, sir. You are an incredible teacher, and I am currently preparing for my GRE. Your teaching style is truly exceptional.
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.
Thanks so much for this lesson! You’re one of the best teachers I’ve come across and hope you keep pursuing your passion!
You're an Outstanding teacher! Glad I've found your channel!
You are a great teacher, so passionate and your explanation is riveting, and never boring. Amazing, I haven't came across another teacher like you!
Only video I got for my tomorrow exam , its really helpful 🙂
Good luck tomorrow!
new subscriber best teaching for free of cost hats off to u sir
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
You are perfect in every possible way,i just subscribed..
This man just saved my life ❤
You give your number i will send a solution better than this
Brilliant teaching, thank you so much, sir!❤❤❤❤❤❤❤❤❤❤❤❤❤
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.
i approached this is a very different way. successivly multiplied by 3 simply discarding the higher digits. (effectively modulo 100). this produced a series of 20 values. Taking 431 modulo 20 picked the 11th term of the series which was 47
Here is the whole series: 03 09 27 81 43 29 87 61 83 49 [47] 41 23 69 07 21 63 89 67 01
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...
This was awesome, thank you! RUclips has some awesome teachers on it!
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 :)
Hello, it's me again :)
I'm writing this because i found another solution to the problem and i thought that you might find it interesting
I'll be using 14^14 as an example
14 in base 2 = 1110 (2^8 + 2^4 + 2^2 + 2^0)
Then i can writhe the expression as 14^8 * 14^4 * 14^2 (since exponents sum when the base is multiplied by itself)
Then finding the length of the number by using Floor[log10(n^n) + 1]
will convert to Floor[n*log10(n) + 1] which is 17
Then starting from the 14^2 to the 14^8 will solve the issue and since we need to modulo the whole thing we can even strip the number by 10^4 digits with each calculation
14^1 = 14 (don't include it in the final answer, because ls1b is 0)
14^2 = 196 mod 10 000 = 196
14^4 = (14^2)^2 = 38 416 mod 10 000 = 8 416
14^8 = (14^4)^2 = 70 829 056 mod 10 000 = 9 056
14^16 is not calculated because it exceeds our power 14
Then at the end we just multiply everything and mod the thing again, because the properties of modulo and the result should look like this
9 056 * 8 416 * 196 = 14,938,198,016 mod 10 000 = 8 016
And the 1st digit of that number is the n-th digit of the n^n-th number
thanks this is so helpful, and so well-explained!
sir i have a question for the phi you did using 2 square and 5 square could i use other combination as well?
how do you know so fast that the last two digits of 3^15 are 07? is there some trick?
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.
best math video i have ever seen
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!
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.
The lat two digit will be 49
just keep multiplying the last two digits by 3 if you want the last two digits
Last digit 3^10= 49
3^20= 01
3^20= 01
3^40= 01
(3^40)^10*((3^10)^3)*3
Last Two digit
1*49*3=47
Last 2 digit 47.
Find the last three digits of the number 19^97
Muy buena solución, aplicando la función phi de Euler
Thanks ; continue ❤
That was very interesting, thank you!
How do you know that 3^15=7(mod100)
I so much love your teaching 😉😉
14:37 Not Also You wrote Aslo
Thank you 👍🏿
Yesss sirr, thankyou so much
Thank you so much sir
i love you content
Enjoy well
To Be Honest, BRILLIANT!!
thank you sir
Nice video ❤
here for tomorrows discreet mathematics exam
Go in more depth for number theory please. It is my weakest area 😭, and its really annoying me.
Email me some problems
Tq sir
i used binomial theorem and got the same answer
😮
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'.
I am better than this to find last two digits