To establish the fact that n is even and not multiple of 5 you can just notice that an odd number to any power ends with an odd digit, and a multiple of 5 to any power ends with 5 or 0
12:21 the third term from the end is also congruent to 0 mod 1000, but it isn't as obvious as the preceding ones with powers of 10 that are ≥3. The exponent on 10 is 2, and the coefficient is 50·99.
I don't think we actually need to check the two cases though? Because we are only dealing with equivalencies. n^100 = 376 (mod 1000) n^100 = 0 (mod 8) & n^100 = 1 (mod 125). The first one is equivalent to n being even and the second one is equivalent to n = 1,2,3,4 (mod 5). So saying n = 2,4,6,8 (mod 10) is equivalent to our original system of equations.
I’m confused about invoking Eulers theorem at around 6:57. It seems that we are going on the opposite direction of the implication i.e.; we are saying since the congruence condition is met that implies that n is relatively prime to 5. However, Eulers theorem is not biconditional and this seems to be in the wrong direction
Another way to argue instead of explicitly raising a number to the hundredth power modulo 1000 is that any number n prime to 5 represents a unit modulo 125; since the order of the group of units is \phi(125) = 100, the order of any unit divides 100, hence n^100 = 1 modulo 125. If n is additionally divisible by 2, then n^100 = 0 mod 8. But there is only one solution mod 1000 to x = 1 mod 125 and x = 0 mod 8, and that is x = 376. Probably is it much better known that if n is prime to 2 (i.e., odd) and divisible by 5, then n^m = 625 mod 1000 if m is even and greater than 2. It is no accident that 376 and 625 are the nontrivial idempotents mod 1000. Simple tools like the Chinese Remainder Theorem are key to this type of problem. The CRT itself is quite powerful and shows up in all sorts of contexts.
@@stephenhamer8192You were quite right in the first place. Any n which is even and a multiple of 5 must end in 0, and raising it to the power 100 will have the last three digits 000. So n can't be both even and a multiple of 5. Since powers of odd numbers are odd, n must be even if one of its powers ends in 2, therefore we must conclude that n can't be a multiple of 5. No Euler/Fermat required.
For some reason I though the problem said n³ (I had only seen the thumbnail) and solved it completely before realizing it was actually n^100. If people would like to solve it themselves and/or check my solution, I had n³ = 376 (mod 1000) n = 126 (mod 250).
Not really. It's using the fact that if k = 376 mod 1000, then k = 0 mod 8 and k = 1 mod 125. That's pretty obvious and doesn't rely on 8 and 125 being coprime. A general statement would be "if k = a mod n, and m divides n, then k = a mod m."
In fact, he had. This generalisation is called the Euler's hypothesis. It says that no n-1 perfect n-powers sum to perfect n-power. Like, there's no such x, y, z, u, v such that x⁵ + y⁵ + z⁵ + u⁵ = v⁵. Disproven in 1966 by L. J. Lander and T. R. Parkin (actually by supercomputer). Here is some counterexamples. n = 5: 27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵ n = 8: 90⁸ + 223⁸ + 478⁸ + 524⁸ + 748⁸ + 1088⁸ + 1190⁸ + 1324⁸ = 1409⁸ Euler indeed was a genius. Ridiculously, an only fact he couldn't prove is the false hypothesis, that actually nobody really disproven analytically, only by counterexamples that nobody couldn't come up with until computers was invented. One person already mentioned it right before me.
Equation: n^m = X + Y with X ≥ 1000, Y < 1000 and m > 1 Question: Find all possible n ∈ N for given Y! n = a * 10² + b * 10 + c with a, b, c ∈ N n^m = (100a + 10b + c)^m = c^m + m * { 100a + 10b } * c^(m-1) + m(m-1)/2 * { 100b² } * c^(m-2) + Z with Z mod 1000 = 0 A = n^m - Z = c^m + 10 * { mb * c^(m-1) } + 100 * { ma * c^(m-1) + m(m-1)/2 * b² * c^(m-2) } With m = 100: Throw out all terms with O(1000) => A[new] = c^m With Y = 376 we get, that c^m has to be even, so c is even: c = 2,4,6,8 (no zero, because then ...6 in 376 not possible) 2^(100) = 1024^(10) = ... = ...376 4^(100) = (2^(100))^2 = (...376)^2 = ...376 8^(100) = (2^(100))^3 = (...376)^3 = ...376 3^(100) = 59049^(10) = ... = ...001 6^(100) = 2^100 * 3^100 = ...376 * ...001 = ..376 Solution: All n with n mod 10 = {2,4,6,8}.
To establish the fact that n is even and not multiple of 5 you can just notice that an odd number to any power ends with an odd digit, and a multiple of 5 to any power ends with 5 or 0
“Vibes of Euler’s theorem” is such an amazing statement
12:21 the third term from the end is also congruent to 0 mod 1000, but it isn't as obvious as the preceding ones with powers of 10 that are ≥3. The exponent on 10 is 2, and the coefficient is 50·99.
1:43 To Fermat's little theorem*
I don't think we actually need to check the two cases though? Because we are only dealing with equivalencies.
n^100 = 376 (mod 1000) n^100 = 0 (mod 8) & n^100 = 1 (mod 125). The first one is equivalent to n being even and the second one is equivalent to n = 1,2,3,4 (mod 5).
So saying n = 2,4,6,8 (mod 10) is equivalent to our original system of equations.
I’m confused about invoking Eulers theorem at around 6:57. It seems that we are going on the opposite direction of the implication i.e.; we are saying since the congruence condition is met that implies that n is relatively prime to 5. However, Eulers theorem is not biconditional and this seems to be in the wrong direction
Another way to argue instead of explicitly raising a number to the hundredth power modulo 1000 is that any number n prime to 5 represents a unit modulo 125; since the order of the group of units is \phi(125) = 100, the order of any unit divides 100, hence n^100 = 1 modulo 125. If n is additionally divisible by 2, then n^100 = 0 mod 8. But there is only one solution mod 1000 to x = 1 mod 125 and x = 0 mod 8, and that is x = 376.
Probably is it much better known that if n is prime to 2 (i.e., odd) and divisible by 5, then n^m = 625 mod 1000 if m is even and greater than 2. It is no accident that 376 and 625 are the nontrivial idempotents mod 1000.
Simple tools like the Chinese Remainder Theorem are key to this type of problem. The CRT itself is quite powerful and shows up in all sorts of contexts.
Do we need Euler's theorem at all? It is obvious that n must be even and not a multiple of 5.
it's obvious that this is a necessary condition.
it's less obvious that this is a sufficient condition.
Twice you said "modulo 1000" but wrote "mod 100" in the lower right toward the end.
When I saw the thumbnail I worked it out for myself and thought I must have made a mistake, but no the solution set really is all those values.
It's not all those values. 6 is a counterexample. ends in 232.
@@wellcubed9626 6 is not a counterexample, I just plugged it into wolframalpha and it indeed ends in 376
@@wellcubed9626 I think you did something wrong, because 6^100 definitely ends in 376. In fact, every positive power of 6 ends in 6.
@@ConManAU Thx for pointing it out. I was so confused tryna figure out where the mistake was. But why does maple say it ends in 232 though..?
@@ConManAU ok i figured out it was a bug with maple's tech.
Once we have established that n is even, do we really need Euler's thm to show that n cannot be a multiple of 5?
yes . 10 is even and it is a multiple of 5, 12 is not , for example
Sorry, my Smart Alec-ry. Euler's Thm could have yielded something less obvious
@@stephenhamer8192You were quite right in the first place. Any n which is even and a multiple of 5 must end in 0, and raising it to the power 100 will have the last three digits 000. So n can't be both even and a multiple of 5. Since powers of odd numbers are odd, n must be even if one of its powers ends in 2, therefore we must conclude that n can't be a multiple of 5. No Euler/Fermat required.
For some reason I though the problem said n³ (I had only seen the thumbnail) and solved it completely before realizing it was actually n^100.
If people would like to solve it themselves and/or check my solution, I had
n³ = 376 (mod 1000) n = 126 (mod 250).
7:16 Isn't the note using the CRT already?
Not really. It's using the fact that if k = 376 mod 1000, then k = 0 mod 8 and k = 1 mod 125. That's pretty obvious and doesn't rely on 8 and 125 being coprime.
A general statement would be "if k = a mod n, and m divides n, then k = a mod m."
@@owenbechtel Thanks, CRT mentions the uniqueness of the solution also. I thought the pretty obvious part was the CRT, not the unique solution part
So Euler recognised set theory before Galois? or is that a later interpretation of what Euler proved?
Nice video :)
Once you have totient(125) = 100...
you have 126, 376, 626, 876 as possibilities.
And only 376 is divisible by 8.
11:46
Oh my god, you are still at it? Has been a long time since I visited...
May favorite number 376
Fact: 376 is an idempotent of 1000
euler had a generalisation of fermat’s last theorem?? 😱😱😱
He meant to say Fermat's *Little* Theorem.
Yes but the proof didn't fit into the narrow margin of the page
He did conjecture a generalization of FLT ("Euler's sum of powers conjecture") but it was disproven in 1966.
In fact, he had. This generalisation is called the Euler's hypothesis. It says that no n-1 perfect n-powers sum to perfect n-power. Like, there's no such x, y, z, u, v such that x⁵ + y⁵ + z⁵ + u⁵ = v⁵. Disproven in 1966 by L. J. Lander and T. R. Parkin (actually by supercomputer).
Here is some counterexamples.
n = 5: 27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵
n = 8: 90⁸ + 223⁸ + 478⁸ + 524⁸ + 748⁸ + 1088⁸ + 1190⁸ + 1324⁸ = 1409⁸
Euler indeed was a genius. Ridiculously, an only fact he couldn't prove is the false hypothesis, that actually nobody really disproven analytically, only by counterexamples that nobody couldn't come up with until computers was invented.
One person already mentioned it right before me.
* Euler
* Fermat's
First comment.
Last comment.
I worked that myself and only got one solution n = 188. good problem
Equation: n^m = X + Y with X ≥ 1000, Y < 1000 and m > 1
Question: Find all possible n ∈ N for given Y!
n = a * 10² + b * 10 + c with a, b, c ∈ N
n^m = (100a + 10b + c)^m
= c^m
+ m * { 100a + 10b } * c^(m-1)
+ m(m-1)/2 * { 100b² } * c^(m-2)
+ Z
with Z mod 1000 = 0
A = n^m - Z = c^m + 10 * { mb * c^(m-1) } + 100 * { ma * c^(m-1) + m(m-1)/2 * b² * c^(m-2) }
With m = 100: Throw out all terms with O(1000)
=> A[new] = c^m
With Y = 376 we get, that c^m has to be even, so c is even: c = 2,4,6,8 (no zero, because then ...6 in 376 not possible)
2^(100) = 1024^(10) = ... = ...376
4^(100) = (2^(100))^2 = (...376)^2 = ...376
8^(100) = (2^(100))^3 = (...376)^3 = ...376
3^(100) = 59049^(10) = ... = ...001
6^(100) = 2^100 * 3^100 = ...376 * ...001 = ..376
Solution: All n with n mod 10 = {2,4,6,8}.