Find the last two digits.
Вставка
- Опубліковано 29 вер 2024
- Using Euler's generalization of Fermat's little theorem we look at a classic number theory problem.
Please Subscribe: www.youtube.co...
Merch: teespring.com/...
Personal Website: www.michael-pen...
Randolph College Math: www.randolphcol...
Randolph College Math and Science on Facebook: / randolph.science
Research Gate profile: www.researchga...
Google Scholar profile: scholar.google...
If you are going to use an ad-blocker, considering using brave and tipping me BAT!
brave.com/sdp793
Buy textbooks here and help me out: amzn.to/31Bj9ye
Buy an amazon gift card and help me out: amzn.to/2PComAf
Books I like:
Sacred Mathematics: Japanese Temple Geometry: amzn.to/2ZIadH9
Electricity and Magnetism for Mathematicians: amzn.to/2H8ePzL
Abstract Algebra:
Judson(online): abstract.ups.edu/
Judson(print): amzn.to/2Xg92wD
Dummit and Foote: amzn.to/2zYOrok
Gallian: amzn.to/2zg4YEo
Artin: amzn.to/2LQ8l7C
Differential Forms:
Bachman: amzn.to/2z9wljH
Number Theory:
Crisman(online): math.gordon.edu...
Strayer: amzn.to/3bXwLah
Andrews: amzn.to/2zWlOZ0
Analysis:
Abbot: amzn.to/3cwYtuF
How to think about Analysis: amzn.to/2AIhwVm
Calculus:
OpenStax(online): openstax.org/s...
OpenStax Vol 1: amzn.to/2zlreN8
OpenStax Vol 2: amzn.to/2TtwoxH
OpenStax Vol 3: amzn.to/3bPJ3Bn
My Filming Equipment:
Camera: amzn.to/3kx2JzE
Lense: amzn.to/2PFxPXA
Audio Recorder: amzn.to/2XLzkaZ
Microphones: amzn.to/3fJED0T
Lights: amzn.to/2XHxRT0
White Chalk: amzn.to/3ipu3Oh
Color Chalk: amzn.to/2XL6eIJ
You’re the best. I love these things; it explores a math area I wasn’t exposed to in engineering classes.
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 :)
12:26
85K subs also. 15K more before the silver play button...
No H/W?
@@srijanbhowmick9570 I'm on time crunch these days so I dont have a lot of time to find good homeworks. On top of that, the last two homeworks had zero and one answer so I guess the homework craving is over.
Oh yes
Hw plssss
@@shivanggoyal7280 I still post them, just not daily until I get my time back. Don’t hold your breath 😛
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!
This channel is one of the best math channels in youtube, keep making great content!
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.
So, just to make sure I have this correctly: you start by checking d(123^n) at n=1, which is 23, and then keep going until you get 23 again?
@@Umbra451 you continue until you see a padded number you've seen already, but in this case, yes, that number is 23
@@followNoxville would that not take ages to solve since you would have to compute up to 23^21 in this case?
@@sohamsud6152 you can truncate at each step though, reducing a work a lot.
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".
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.
Nicely spotted
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
I'm digging the hoodie
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
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
after watching the video, i don't recall you mentioning that (ak+b)^x mod a = b^x mod a
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
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
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)
Amazing problem 👍👍
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.
When you are ranging over all m values, it doesn't matter whether you use "
Can you please present the proof of Fermat's little theorem with Multinomial theorem? Please... There is no good explanation on UA-cam.
Can't believe I did this myself and that too in under 5 minutes! Michael's videos really help in problem-solving.
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.
That's how I solved it. I had pretty much the exact same workings as you.
Find 123^789^456 = 23^789^456 mod 100.
Notice 23^x = 23^(20k + x) mod 100 for all integers k. (line 2)
Write 789^456 = 20k+x, solve for x (i.e., find 789^456 mod 20).
Write 789^456 = 9^456 mod 20.
Notice 9^y = 9^(2k+y) mod 20 for all integers k.
Write 456 = 2k + y, solve for y (i.e., find 456 mod 2). Notice y=0 for some k. Thus 9^456 = 9^(2k+0) = (9^2)^k = 1^k = 1 mod 20.
Thus 789^456 = 1 mod 20, thus 789^456=20k+1 for some k, thus x=1. Thus 23^(20k+1) = 23^(789^456) mod 100 = (23^(20k))23^1 = ((23^20)^k)23 = (1^k)23 = 23 mod 100. We are done.
23^20=1 mod 100 comes from letting x=0 and k=1 on line 2. I had to reuse variables for different purposes a couple of times, hopefully it wasn't confusing.
I want to like, but there are already 123 likes, hmmm...
May be is easy for you but.
Find the last three digits of the number 19^97
So imagine you knew nothing about Euler' theorem, number theory or exponentiation for that matter. Perhaps you just wandered into the wrong classroom. An you totally misunderstood the question and answered 23. Everybody laughs at you. Then the professor spends 12 minutes proving you right, and then ... a weird silence ;-)
Thank you, sir for solving this amazing problem.
Way too many ads!
I found the last digit to be 3 on my own, but I couldn't figure out the second to last digit
This is my favorite math channel. Do you know of any interesting proofs that utilize Pólya's Theorem of counting?
This is a great vid, I was able to solve it.
This is the first vid where I could finally understand this topic, you are great., thanks for sharing.
Just like in his example you can use 5^2 instead of 5^4, for the middle modulus you can use 20 instead of 40. That reduces the problem to 23^9^456. But 9^2 is 81, or 1 mod 20, so (9^2)^228 is 1 mod 20, thus the whole thing collapses to 23^1, or 23 mod 100.
Rather than use Euler's totient function, I just use a spreadsheet, successively multiplying by X and modding N, to find the power of X that is 1 mod N. For any problem I've been presented, this works quicker than using pure number theory.
You should talk about the Carmichael function, it makes this problem a lot faster.
phi(100)=40
phi(40)=16
789^456==29^456==29^(16*28+8)==29^8==11^8==121^4==1 (mod 40)
123^{789^456}==23^{1}==23 (mod 100)
Can you solved them?
you could do it faster. we know that the gdc(123,100)=1 so 123^phi(100)=1(mod 100) since phi(100)=40 we obtain 123^40=1(mod 100) . now we calculate 789^456 mod 40 and after a bit of calculation we arrive at 789^456=1(mod 40) hence we have 123^789^456=123^(40k+1)=123=23(mod 100)
123 = 23 mod 100. 23×23 = 29 mod 100. 29×23 = 87 mod 100. 87×23 = 1 mod 100. Thus, there is a cycle of 4. 789 = 1 mod 4. 1^456 = 1 mod 4. Thus, 123^789^456=23^1 mod 100, and our last two digits are 23.
And now how many digits in this number? Is there a method to solve this question?
Take the log base 10, add one.
Floor(log_10(n)) + 1
2.4e1321 digits, was wondering the same
CHHABI SARKAR it's not ceil and you can check that by substituting 10 for example. You get ceil(log(10)) and that's ceil(1) which is 1 and should be 2.
@@Kokurorokuko oh sorry my bad , then it should be floor + to i guess
So... the last two digits of any 3-digit number, xyz raised to 789 raised to 456 will be yz? Or did I miss some step somewhere...?
maybe yes , he did not change the "base" number , just change 123 to 23 , well you right
okay that's brilliant
Awesome 👍🏻
Beautiful work
Very nice!
Michael Penn can you consider problems about to find last Three digits ?
Find digital sum of 2020^2020.
20776 , but I do not know if there is easy way to prove it.
😮
what i did was get mod 24. arrived at the same answer
i had a hunch the power would get reduced to 1 but i lacked the skill to do it my self. Nice vid
I must be missing something. Euler's theorem as stated requires gcd(a,n)=1 to obtain a^phi(n)=1 (mod n), but you seem to be using gcd(a,n)=k to obtain a^phi(n)=k (mod n). This doesn't matter for 123 and 789 as 123 and 100 are coprime and 789 is co-prime with 40, but 456 has a GCD of 8 with 16, so it would seem that the condition of gcd(456,16)=1 is not satisfied.
the Euler theorem was used only twice , there is no need to use it a third time , so 456 & 16 dont have to be co-primes
You lost me after you started applying Euler's theorem on the number. I get why you were doing mod 100 in the beginning but why did you do the exponents with phi(100) and phi(40) respectively?
If, for example, we wanted to determine the last two digits of, say, 123^8421, then we can limit ourselves to 23^8421 because 123 ≡ 23 (mod 100) and hence 123^8421 ≡ 23^8421 (mod 100).
But how to proceed from here? Well, according to Euler's formulas, we also know that 23^phi(100) ≡ 1 (mod 100) , and phi(100) = 40, which means
23^40 ≡ 1 (mod 100)
and therefore we can write
23^8421 = 23^(40*210 + 21) = (23^40)^210 * 23^21 ≡ (1)^210 * 23^21 (mod 100) = 23^21 (mod 100).
This means that we've now simplified the expression "123^8421" modulo 100 to "23^21" , by reducing the exponent (8421) congruent to modulo 40.
However, in the video's case, the exponent that we need to reduce modulo 40 isn't 8421 but 789^456 . Well, of course 789 ≡ 29 (mod 40) so 789^456 ≡ 29^456 (mod 40), but how do we deal with the large exponent 456? Simple, by another step of applying Euler's formulas again: this time reducing congruent to modulo phi(40) (in other words: mod 16), applied on the exponent 456 .
So eventually we can write
123^(789^456) =
... reduce 123 congruent to modulo 100 ...
≡ 23^(789^456) (mod 100)
... reduce 789 congruent to modulo 40, because 23^40 ≡ 1 (mod 100) ...
≡ 23^(29^456) (mod 100)
... reduce 456 congruent to modulo 16, because 29^16 ≡ 1 (mod 40) and hence 23^(N * 29^16) ≡ 23^N (mod 100) ...
≡ 23^(29^8) (mod 100)
I hope that helps.
Hello Michael, great video.
When you say last two digits what are you referring to. Because the value we got at the end of our solution is 23?
He's talking about finding the last two digits of the tower ((123)^789)^456), the result of which has 10^1321 digits (according to my calculator). As he says at the end, the fact that the solution to the question asked is "23" is almost happenstance. (With some more arduous work, he could have answered "What are the last *three* digits" and gotten the answer 923, which would have seemed slightly less 'unsatisfying'.)
Anyone want to calculate the odds of a 3 digits number to a 3 digit number to a 3 digit number having the same last two digits as the original number? I suspect it is actually much more than the intuitive answer of 1/100. It's going to depend a lot on the cyclic length of any given mod(x^n).
You mean X^(X^X) , where X is a three-digit number (and not: X^(Y^Z) where X, Y, Z may be three different three-digit numbers), right?
X is a three-digit number, and the last two digits of X^(X^X) must be the same as the last two digits of X ==>
X^(X^X) ≡ X (mod 100)
From the 900 available three-digit numbers (from 100 to 999), it's relatively easy to show that the following values for X do satisfy the equation :
100, 200, 300, 400, 500, 600, 700, 800, 900,
125, 225, 325, 425, 525, 625, 725, 825, 925,
175, 275, 375, 475, 575, 675, 775, 875, 975,
So yes, the probability (not "odds") is more than 1/100 , because it is at least 27/900 = 3/100 (and probably much higher).
(By the way, it can also be relatively easily shown that no other multiples of 5 work.)
I don't understand why you say that "1/100" is an intuitive answer though.
Wait according to φ(100)=40
2⁴¹ mod(100)
41≡1 mod(40)
2⁴¹≡2¹ mod(100)≡2 mod(100)
but i use calculator and get 52
why its happen ?
2 and 100 are not Coprime, use CRT
@@justforfun2238 Thank You very much for your explanation
Maxm power is divisible by 4.so it will become 789 to power 0.this turns out to be 1. And 123 to power 1 is 123 so answer is 23,found it in milliseconds🙂🙃
According to your logic,
3^(2^4) ≡ 3^(2^0) ≡ 3^1 ≡ 3 (mod 100)
which is wrong because
3^(2^4) = 3^16 = 43046721 ≡ 21 (mod 100)
@@yurenchu destroyed in milliseconds 🙂🙃
How would one have done this if the number was 456^123^789?
Use the same principles to express as 56^3^5 mod 100. 3^4=1mod 40 so we have 56^3. Crunch that as 16 mod 100.
@@exacerbated But 456 and 100 are not relatively prime so youncan't use the same principles
Is it just me or does this video feel kinda faster than normal? Almost like it’s very subtly sped up or something
Nah you're just getting old lol
@@Milan_Openfeint dang
This video was hard to understand because Euler's Theorem talks about something being equivalent to 1 (mod n), but nowhere after that do I see anything equal to 1 (mod n).
Don't quite understand how the phi function allows you to reduce the exponents by mod equivalences. But I will rewatch
Looks like my question is answered around 6:10, just gotta think a little more
just the magic of totient function..without it it will be just a hell !!!
No, I used 123 = - 2 (mod 25), 2^20 = 1 (mod 25).
exponent = 789^456=(9^2)^228=1^228=1 (mod 20).
result = (-2)^exponent = - (2^20)^((exponent-1)/20) * 2^ 1 = - 1^something *2 = - 2 (mod 25).
Also result = (-1)^789^456 =-1 (mod 4).
So (by Chinese remainder) we have only one number in [0,99] that is result (mod 100): it's 23 (mod 25) and 3 (mod 4), I. e the solution is 23.
C’est vraiment un roi
We have shown that 123 ^ ( 789 ^ 456 ) mod 100 = 23
Another exercise, 123 ^ ( 456 ^ 789 ) mod 100
- " Another exercise, 123 ^ ( 456 ^ 789 ) mod 100 "
I misread the thumbnail and thought that was the actual question. So before watching the video, I got this:
SOLUTION: Last two digits of 123^456^789 are 61.
Or in other words: 123^(456^789) = 61 (mod 100) .
CALCULATION:
123^(456^789) = 23^(456^789) (mod 100)
23² = 529 = 29 (mod 100)
23³ = 12167 = 67 (mod 100)
23⁴ = 29² (mod 100) = 41 (mod 100)
23⁵ = 41*23 (mod 100) = 43 (mod 100)
23⁶ = 43*23 (mod 100) = 89 (mod 100)
23⁷ = 89*23 (mod 100) = 47 (mod 100)
23⁸ = 47*23 (mod 100) = 81 (mod 100)
23⁹ = 81*23 (mod 100) = 63 (mod 100)
23¹⁰ = 63*23 (mod 100) = 49 (mod 100)
23²⁰ = 49² (mod 100) = 1 (mod 100)
==> 23^(0 (mod 20)) = 1 (mod 100)
Furthermore,
456^789 = 16^789 (mod 20)
and
16² = 256 (mod 20) = 16 (mod 20) ==> 16^N = 16 (mod 20)
therefore,
123^(456^789) =
= 23^(456^789) (mod 100)
... 23²⁰ = 1 (mod 100) ...
= 23^(456^789 (mod 20)) (mod 100)
= 23^(16^789 (mod 20)) (mod 100)
... 16^N = 16 (mod 20) ...
= 23^16 (mod 100)
= (23⁸)² (mod 100)
= 81² (mod 100)
= 61 (mod 100)
Q.E.D.
If we use the video's method (with Euler's formulas):
123^(456^789) =
≡ 23^(456^789) (mod 100)
... use 23^40 ≡ 1 (mod 100) , because gcd(23,100) = 1 ...
≡ 23^(16^789) (mod 100)
... use a^16 ≡ 1 (mod 40) ... wait, that's not right, it doesn't apply for a=16.
... Instead:
... 16^2 = 256 ≡ 16 (mod 40), hence 16^N ≡ 16 (mod 40) for any postive integer N ...
≡ 23^(16) (mod 100)
... 23² = 529 ...
≡ 29^8 (mod 100)
... 29² = 841 ...
≡ 41^4 (mod 100)
... 41² = 1681 ...
≡ 81^2 (mod 100)
... 81² = 6561 ...
≡ 61 (mod 100)
so last two digits of 123^(456^789) are 61 .
61
@@yurenchubrilliant !
Thank you so much
Man you are great !!
Can anyone help me solve the number theory problem: a/b=b.a (the only solution I found for all natural (a,b) is (5,2))
I don't think a formal solution is likely given how messing writing a decimal like b.a is going to be.
A possible start is:
a/b=b.a
b
@@IanXMiller Thank you so much for answering my question, but I didn't understand if there are any other solutions and if not how can I prove this?
Let a a ≥ 5^s, we have s' = s. You will have 2 cases now depending on which of r and 2n+2 is larger. I'll do the case 2n+2≥r as an example.
The equation reduces to d(d+2^(2n+2-r) 5^(2n-s)) = m^2; let u = 2n+2-r, v = 2n-s for simplicity. The factors are relatively prime, so each is a perfect square. Letting d = x^2, we must solve 2^u 5^v = y^2 - x^2 = (y-x)(y+x). Let e = gcd(x,y) = 5^g (x is odd since d is), v' = v-2g, y'=y/e, x'=x/e to get 2^u 5^v' = (y'-x')(y'+x'). The factors are relatively prime (except for possibly a single factor of 2) and y'+x' > y'-x', so we have the cases y'+x' = 2^u 5^v', 5^v', 2^u (for all u) and 2^(u-1) 5^v', 2*5^v', 2^(u-1) (for u>0). If u=0, then y'+x' = 5^v', y'-x' = 1, which has solution (x',y') = ((5^v'-1)/2, (5^v' + 1)/2). But 5^v' - 1 = 1^v' - 1 = 0 mod 4, so x' is even, contradiction. If u=1, then we have y'+x' = 2*5^v', 5^v', which don't work since 2y' = (y'+x')+(y'-x') will be odd. If u > 1, using the fact 2y' is even narrows it down to y'+x' = 2^(u-1) 5^v', 2*5^v', 2^(u-1). We get x' = 2^(u-2) 5^v' - 1, 5^v' - 2^(u-2), 2^(u-2) - 5^v', and u=2 is ruled out since then x' is even. Anyways, unraveling everything gives a = 2^r 5^s (x' 5^g)^2 = 2^r 5^(s+2g) x'^2, and the only thing we need to check is a 10^n, contradiction. The other 2 cases collapse into one when we look at x'^2 (they just have opposite signs on x'), giving x'^2 = (5^(2n-2-2g) - 2^(2n+r))^2 and a = 2^r 5^(s+2g) (5^(2n-2-2g) - 2^(2n+r))^2 < 10^n (*). This case may not be possible to eliminate via size reasons. In fact, tons of choices for the free variables n, g, r, s could lead to a solution. There will be infinitely many if we can show that for most n, there are values of g and r making |5^(2n-2-2g) - 2^(2n+r)| small. To show there are finitely many solutions, you will need to somehow show that the values of g, r making this quantity small makes 2^r 5^(s+2g) too large for (*) to be satisfied. The good news is that we can do better than Ian's blind search since the number of values to try (coefficient pairs (g,r), then solve for how big s can be) is quadratic in n rather than exponential. Try n up to 100 in (*) and tell me if you get any g, r, s through brute force.
Now you can see why the problem is really messy. There are 3 free constants r, s, g for one inequality against 10^n with each choice satisfying the inequality leading to a solution, and we may have to inspect a similar inequality for the other case on r'.
11^2=121=1mod 40
easy
85K
nice one
I used to participate in math olympiads in high school, but my school didn't prepare us. Some of these types of problems I never learnt how to solve. Thanks
Hardly any school does...
this type of problem is generally (in high school maths problems) solved using cyclic patterns
@@followNoxville
Btw, is there any normal school which teaches Number Theory?
I assume at most high schools you have to be near a university where you can find a willing tutor to coach you through the harder Olympiad type problems. I wonder what the experience is of the kids that make the national teams.
@@stephenbeck7222
In India, there is a little exposure to Olympiads for Physics or Math or Biology or any subject's Olympiads. Everyone wants to be an engineer (IIT-JEE) or doctor (NEET,AIIMS).
Wait, but if the 8 was a 3, then 23^(-11^3)=1/23^1331, which a tiny fraction, not an integer. When can you make that substitution and still maintain equivalence?
Euler's theorem tells us we can add and subtract 40 from the exponent as many times as we like as long as we don't go negative. OP found a nonnegative integer different from 29^8 by a multiple of 40, so Euler's theorem says he can use it. It's OK if a negative number showed up in an intermediate step.
In your example we would have to add a multiple of 40 to -1331, say 1440, to get a nonnegative number we can use.
This goes to show how working in a larger number system (the integers) can help us reason about a smaller number system (the natural numbers).
@@martinepstein9826 ok, but I dont believe the steps in between. I dont think its true that 23^-1331 is equivalent to 23^109 modulo any integer.
@@matthartley2471 "I dont think its true that 23^-1331 is equivalent to 23^109 modulo any integer"
Me neither. If you prefer you can write 29 as 40 - 11 and get the same answer the same way with no negative numbers. The point is 29^8 = 1 mod 40.
@@martinepstein9826 ok, so you admit that this reasoning is insufficient to prove that 29^8 is equal to one, since your intermediate step is invalid. You'd have to actually square 29, get 841, and notice that this was 1 mod 40.
Suggestion-Please compile all the Mathematical Olympiad Questions in a separate Playlist. Please it will be very useful
Too easy!! Try more olympiad problems next time...