Elegant solution. I broke it down in a few steps: 1) Last digit of 5^n is 5, so 2^n-n has 5 as Last digit too. Then n has to be odd because 2^n is not. When n is odd, 2^n ends with 2 or 8 (repeats 2, 4, 8, 6...), so n has to end with 7 or 3. If n ends in 7, it has to be kongruent 17 mod 20 (otherwise 2^n ends in 8) Same argument gives n kongr. 3 mod 20. Also we know if n>1 is odd, 5^n ends in 125, so 2^n-n has to end in 875 2) 2^20 ends in 576. 2^3*2^20 ends in 608, you can easy Show (but not in this comments At 4am) that with any multiplication *2^20 the last 3 digits gets +600 So the last 2 digits will always be 08 2^n-n ends in 75 so n ends in 33. But that is not kongr. 3 mod 20. So we eliminate the case n ends in 3. Leaves us with n kongr. 17 mod 20. Similar to the other case we can show that the endings are 072+400k So n is kongr. 97 mod 100. 3) 2^17 ends in 072 and when n gets +20, the ending gets +400 So 2^97 ends in 672. When n gets +100 the ending gets +400 5 times so +0 => 2^n ends in 672 all the time. Then we search for n with 2^n-n ends in 875 So n=k*1000+672-875=797+(k-1)*1000 So the smallest n is 797
@@leif1075 I think it's easier to just explain the first step again. I wanted to use the Last digit first. The Last digit of the sum obv. has to be a 0. The last digit of 5^n is a 5, so the sum of the rest 2^n-n has to be a 5 too. 5 is an odd last digit and 2^n isn't odd, so 2^n-n can only be 5 if n is odd. Also: If the last digit had to be a 5 and 2^n has a last digit repetition (4,8,6,2) an odd n makes the last digit of 2^n an 8 or a 2. (4 or 6 exist when n is even) But the last digit should be a 5 so 2^n-n mod 10 should be 5. If 2^n mod 10 is 8, n mod 10 has to be 3 If 2^n mod 10 is 2, n mod 10 has to be 7. Now I used mod 20. Why? Because then I have mod 10 and mod 4. And then the options for n mod 20 are 3, 7, 13 and 17 (but 7 and 13 are not working because if the 2^n repetition). mod 3 I never used so I don't know what you mean there. Now the 875 part. All of it should end in 000. Let n be odd and bigger than 1. Then we have a repetition of the Last digits again. 125, 625, 3125, 15625,... We can show that: 125*25 mod 1000 is 125 mod 1000. We know n is odd so we know 5^n ends in 125. And if the whole sum ends in 000, the rest of the sum has to end in 875 (because 875+125 is kongr. 0 mod 1000.)
@@triviagames6507 all of the other steps he did were only necessary conditions, while the last step was also sufficient since he reduced modulo 125 and all of his steps were reversible. However going from mod 125 to mod 25 for example is not reversible so that means that we may have not done enough work.
As discussed, 5ⁿ mod 8 repeats on cycles of 2. 2ⁿ mod 125 repeats on cycles of 100 (totient of 125), and n clearly repeats on cycles of 1000. LCM of these is 1000, so the answer remainder modulo 1000 repeats every 1000. This one's small enough you can check it with a spreadsheet as long as you take modulus 1000 every step - and I did check it that way.
@@SlidellRobotics actually the first step (mod 8) and the very last step (the one where we find that c=-1 (mod 5)) only use equivalences, whereas the others use implications. You know that you really get a solution when you use equivalences. As for the implications when dealing with a and b, they ensure that there is no smaller solution. It is very important to always write what you are doing. This proof relies a lot on the use of both implications and equivalences, too bad the video doesn't even mention it
I did the end like this: n = 197 + 200k 2^(197 + 200k) mod 125 = ... = 47 mod 125 So 197 + 200k = 47 + 125h This leads to linear Diophantine equation 5h - 8k = 6 Whose solution is k = -12 + 5v h = -18 + 8v Smallest positive value for k is then choosing v=3 which gives k=3 and thus n = 197 +3*200 = 797. This also gives all values of n so that the expression is divisible by 1000: n = 797 + 1000v
Solved it almost in a similar way. Just difference is that I set 6=5+1 then used binomial theorem, canceled any 5^i term with i>=3 and ended up with a nice quadratic equation: 25k^2+10k+32=0 mod(125)= 25(k^2+1)+2(k+1). Here n=5+6k. Then we can quickly show that k+1 must be 0 mod(25) and after using it in the quadratic equation, we get k=99 mod(125). Finally, n=797 mod(1000) I got stuck in the beginning because I wanted to use little Fermat theorem.
@@leif1075 at some point, we find that n=5mod(8) which means n=5+8k. So mod 5^3, we get 2^n=n mod(5^3) which gives 2^5*2^8k=n mod(5^3). Note thaglt 2^8=6 mod(5^3). Here we use 6=5+1 and expand binomial expression then cancel powers of 5 above 3.
@@riadsouissi well I'd have to go back now obviously I know 6 equals 5 plus 1 but that's not what he wrote there..he had it in some funky mod expression I think..
My Solution: 1000k=2^n + 5^n - n, where k is an integer. 1000k-n=2^n + 5^n, and 1000=2^3*5^3, so (2^3*5^3)k=2^n+5^n. There are 2 cases for n, where n is odd or n is even. If n is even, let n=2p, so 1000k-n=2^2p + 5^2p= 4^p+ 25^p = 1000k- 2p, and if p=2, k=9/25, and if p=4, k=65.something, so for n=2p, it is absurd, so n must be odd. If n is odd, then let n=2p+1, so the only case that works is if n=1000-203=797. The answer must be 797.
Can you provide a solution starting from 2^n - n = 0 mod(125) as opposed to starting from 5^n - n = 0 mod(8) More precisely, how do you parametrize n when starting from 2^n - n = 0 mod(125)
Good morning! Best regards from Brazil. I used more the arms and hands than the brain First n must be odd. So (2^n =2 or 2^n =8) and 5^n=5 (mod10). Then if 2^n =2 (mod10); n=7 (mod10) If 2^n=8 (mod10); n=3 (mod10) As 2^(n+100)=2^n n>=3 because ord 2 (125) =100 as 2 is a primitive root of 5^k, k>1. So we have theese options for n= 7 (mod10): n=17 +100k 2^n=72 (mod1000) n=37 +100k 2^n= 472 (mod1000) n= 57 +100k 2^n= 872 (mod 1000) n= 77 +100 k 2^n= 272 (mod1000) n= 97 + 100 k 2^n = 672 (mod1000) As 2^n=72(100) for those options 2^n+5^n= 97 (mod 100) a d the only option that can correct 97 is n=97+100k 97 +100k - 797=0 (mod1000) k= 7 a d n= 797. For n=3 (mod10) n= 3 + 100k n=8 (mod 1000) n= 23 + 100 k n= 608 (mod1000) n=43 + 100 k n= 208 (mod 1000) n =63 + 100 k n= 808 (mod1000) n= 83 +100k n=408 (mod 1000) As 2^n+ 5^n=33 (mod100) we have no solution for n=3 (mod10) If I did not make any mistake. n=797 is the only solution. I made a big mistake. The equation is modular 97 +100k -797=0 (mod 1000) k=7+10u n= 797 +1000u. And 797 os the smallest solution. Sorry!!!!
@@raj-thecreation4811, Good morning! Note that: 2^1=2 2^2=4 2^3=8 2^4=6 2^5=2 2^6=4 . . . It is easy to se that for n>0 If n=0 mod4 then 2^n=6 mod10 if n=1 mod4 then 2^n=2 mod10 If n=2 mod4 then 2^n=4 mod10 if n=3 mod4 then 2^n=8 mod10 As 127=3 mod4 the last digit of 2^127 is 8, and as the last digit of 5^127 is 5 the last digit of: 2^127 + 5^127 -127 is 6. So it does not work. ___________________________________________________________________________________________ Sorry, my eyes do not see well anymore. I am a old man. I will answer for 157 My solution is correct. The least n is 797. Do not waste your time trying to find another one.
Look up modular arithmetic and I strongly recommend the youtube channel Michael Penn, he does lots of problems involving mod and has an introduction to it
i love how aime problems are getting a lot more straightforward but still difficult
Wow, that took some real perseverance. It takes a lot of confidence just to “keep going” with this sort of question.
Elegant solution.
I broke it down in a few steps:
1) Last digit of 5^n is 5, so 2^n-n has 5 as Last digit too. Then n has to be odd because 2^n is not. When n is odd, 2^n ends with 2 or 8 (repeats 2, 4, 8, 6...), so n has to end with 7 or 3.
If n ends in 7, it has to be kongruent 17 mod 20 (otherwise 2^n ends in 8)
Same argument gives n kongr. 3 mod 20.
Also we know if n>1 is odd, 5^n ends in 125, so 2^n-n has to end in 875
2) 2^20 ends in 576.
2^3*2^20 ends in 608, you can easy Show (but not in this comments At 4am) that with any multiplication *2^20 the last 3 digits gets +600
So the last 2 digits will always be 08
2^n-n ends in 75 so n ends in 33. But that is not kongr. 3 mod 20. So we eliminate the case n ends in 3.
Leaves us with n kongr. 17 mod 20.
Similar to the other case we can show that the endings are 072+400k
So n is kongr. 97 mod 100.
3) 2^17 ends in 072 and when n gets +20, the ending gets +400
So 2^97 ends in 672.
When n gets +100 the ending gets +400 5 times so +0
=> 2^n ends in 672 all the time.
Then we search for n with
2^n-n ends in 875
So n=k*1000+672-875=797+(k-1)*1000
So the smallest n is 797
Where did you get mod 20 and mod 3 from..seems.rsndom you didn't explain why
And what the heck donyou mean 2^n-n..wjat does that mean and how donyou know the 875 thing?
@@leif1075 I think it's easier to just explain the first step again.
I wanted to use the Last digit first.
The Last digit of the sum obv. has to be a 0.
The last digit of 5^n is a 5, so the sum of the rest 2^n-n has to be a 5 too.
5 is an odd last digit and 2^n isn't odd, so 2^n-n can only be 5 if n is odd.
Also: If the last digit had to be a 5 and 2^n has a last digit repetition (4,8,6,2) an odd n makes the last digit of 2^n an 8 or a 2. (4 or 6 exist when n is even)
But the last digit should be a 5 so
2^n-n mod 10 should be 5.
If 2^n mod 10 is 8, n mod 10 has to be 3
If 2^n mod 10 is 2, n mod 10 has to be 7.
Now I used mod 20. Why? Because then I have mod 10 and mod 4.
And then the options for n mod 20 are 3, 7, 13 and 17 (but 7 and 13 are not working because if the 2^n repetition).
mod 3 I never used so I don't know what you mean there.
Now the 875 part.
All of it should end in 000.
Let n be odd and bigger than 1.
Then we have a repetition of the Last digits again.
125, 625, 3125, 15625,...
We can show that:
125*25 mod 1000 is 125 mod 1000.
We know n is odd so we know 5^n ends in 125.
And if the whole sum ends in 000, the rest of the sum has to end in 875 (because 875+125 is kongr. 0 mod 1000.)
@@1Mystery10000 why mod 20 though..why not mod 2 and 5 or 8 and 125..it s random
@@leif1075 What? Like I said. 20 includes the (2,4,8,6)-repetition and the repetition of the last digits.
I actually got as far as the mod 8 and mod 125 bit on my own, before deciding to watch the answer because I thought there might be a simpler method 😂
Ikr
Why didn't you repeat it after 1000d-203?
It's because the question is tell you to solve the *LEAST* n such that n satisfies the condition.
@@TheoSin then why didn't he stop earlier,
@@triviagames6507 all of the other steps he did were only necessary conditions, while the last step was also sufficient since he reduced modulo 125 and all of his steps were reversible. However going from mod 125 to mod 25 for example is not reversible so that means that we may have not done enough work.
@@replicaacliper Ohhh this seems a better explanation, Thank you
At 9:24, why did he change 1600c to 100c?
Thanks for the video!
9:49 if the gcd of the number you want to divide by it with the divisor is bigger then 1 you can not divide !!!!!????
6:08 how did the numbers become smaller?
32 = 30 + 2 = 6*5 + 2 = 0 + 2 (mod 5)
6 = 5 + 1 = 1 (mod 5)
8 = 5 + 3 = 3 (mod 5)
10:47 why you have stop here ?
How did you know that the last equation give you a correct answer !!!!
As discussed, 5ⁿ mod 8 repeats on cycles of 2. 2ⁿ mod 125 repeats on cycles of 100 (totient of 125), and n clearly repeats on cycles of 1000. LCM of these is 1000, so the answer remainder modulo 1000 repeats every 1000. This one's small enough you can check it with a spreadsheet as long as you take modulus 1000 every step - and I did check it that way.
@@SlidellRobotics actually the first step (mod 8) and the very last step (the one where we find that c=-1 (mod 5)) only use equivalences, whereas the others use implications. You know that you really get a solution when you use equivalences. As for the implications when dealing with a and b, they ensure that there is no smaller solution.
It is very important to always write what you are doing. This proof relies a lot on the use of both implications and equivalences, too bad the video doesn't even mention it
9:48 can we divide by 25 in mod125? Doesmt that only work in (mod p) situations where p is prime?
Or does it also work for (mod p^k) situations?
We have also reduced the divisor, we just can't divide LHS AND RHS of congruence by 5 or 25 as it is not coprime to 25
I did the end like this:
n = 197 + 200k
2^(197 + 200k) mod 125 = ... = 47 mod 125
So 197 + 200k = 47 + 125h
This leads to linear Diophantine equation
5h - 8k = 6
Whose solution is
k = -12 + 5v
h = -18 + 8v
Smallest positive value for k is then choosing v=3 which gives k=3 and thus n = 197 +3*200 = 797.
This also gives all values of n so that the expression is divisible by 1000:
n = 797 + 1000v
yooo thanks i was doing this problem in our school's math training last week and I couldn't solve it :( thanks!!!
Solved it almost in a similar way.
Just difference is that I set 6=5+1 then used binomial theorem, canceled any 5^i term with i>=3 and ended up with a nice quadratic equation: 25k^2+10k+32=0 mod(125)= 25(k^2+1)+2(k+1). Here n=5+6k.
Then we can quickly show that k+1 must be 0 mod(25) and after using it in the quadratic equation, we get k=99 mod(125).
Finally, n=797 mod(1000)
I got stuck in the beginning because I wanted to use little Fermat theorem.
Nice solution. I used casework and some induction and contradiction.
What do you mean by 6 equals 5 plus 1..does anyone actually understand what you mean by that sorry?
@@leif1075 at some point, we find that n=5mod(8) which means n=5+8k. So mod 5^3, we get 2^n=n mod(5^3) which gives 2^5*2^8k=n mod(5^3). Note thaglt 2^8=6 mod(5^3). Here we use 6=5+1 and expand binomial expression then cancel powers of 5 above 3.
@@riadsouissi well I'd have to go back now obviously I know 6 equals 5 plus 1 but that's not what he wrote there..he had it in some funky mod expression I think..
How did you get 25k^2 + 10k + 32?
Can show the steps to it?
Thanks
My Solution:
1000k=2^n + 5^n - n, where k is an integer. 1000k-n=2^n + 5^n, and 1000=2^3*5^3, so (2^3*5^3)k=2^n+5^n. There are 2 cases for n, where n is odd or n is even. If n is even, let n=2p, so 1000k-n=2^2p + 5^2p= 4^p+ 25^p = 1000k- 2p, and if p=2, k=9/25, and if p=4, k=65.something, so for n=2p, it is absurd, so n must be odd. If n is odd, then let n=2p+1, so the only case that works is if n=1000-203=797. The answer must be 797.
I was initially stuck with induction. I soon decided to use 2 main cases and find a contradiction.
It took me I think 15-25 minutes to solve this problem. Very interesting number theory problem!
Amazing problem 👍👍
I'm not following one step: If 32 * 6^a = 8a+5 (mod 125), why does that imply 32 * 6^a = 8a+5 (mod 5)?
32*6^a -(8a+5) is a multiple of 125
Therefore it must be a multiple of 5 as well(5 is a factor or 125)
If you want to be more specific,
32.6^a = 125k(8a+5) (k is any integer)
RHS is divisible by 5 so LHS is also divisible by 5
Can you provide a solution starting from
2^n - n = 0 mod(125)
as opposed to starting from
5^n - n = 0 mod(8)
More precisely, how do you parametrize n when starting from 2^n - n = 0 mod(125)
Great trick.
Good morning! Best regards from Brazil. I used more the arms and hands than the brain
First n must be odd.
So (2^n =2 or 2^n =8) and 5^n=5 (mod10).
Then if 2^n =2 (mod10); n=7 (mod10)
If 2^n=8 (mod10); n=3 (mod10)
As 2^(n+100)=2^n n>=3 because
ord 2 (125) =100 as 2 is a primitive root of 5^k, k>1.
So we have theese options for n= 7 (mod10):
n=17 +100k 2^n=72 (mod1000)
n=37 +100k 2^n= 472 (mod1000)
n= 57 +100k 2^n= 872 (mod 1000)
n= 77 +100 k 2^n= 272 (mod1000)
n= 97 + 100 k 2^n = 672 (mod1000)
As 2^n=72(100) for those options 2^n+5^n= 97 (mod 100) a d the only option that can correct 97 is n=97+100k
97 +100k - 797=0 (mod1000)
k= 7 a d n= 797.
For n=3 (mod10)
n= 3 + 100k n=8 (mod 1000)
n= 23 + 100 k n= 608 (mod1000)
n=43 + 100 k n= 208 (mod 1000)
n =63 + 100 k n= 808 (mod1000)
n= 83 +100k n=408 (mod 1000)
As 2^n+ 5^n=33 (mod100) we have no solution for n=3 (mod10)
If I did not make any mistake. n=797 is the only solution.
I made a big mistake.
The equation is modular
97 +100k -797=0 (mod 1000)
k=7+10u
n= 797 +1000u.
And 797 os the smallest solution.
Sorry!!!!
What rubbish! Unit digit of 2⁷⁹⁷ is 2 and that of 5⁷⁹⁷ is 5 , so 5×2=10 and unit digit of 2⁷⁹⁷+5⁷⁹⁷-797 is 3, how possible man?
@@raj-thecreation4811 Good morning! If you pay atention, It is 2^n+5^n and not 2^n*5n=10^n.
@@pedrojose392 yeah! Thanks and good morning!
But 2¹⁵⁷+5¹⁵⁷-157 has last three digit as 000, so divisible by 1000, check the last three digit of 2¹⁵⁷+5¹⁵⁷
@@raj-thecreation4811, Good morning!
Note that:
2^1=2
2^2=4
2^3=8
2^4=6
2^5=2
2^6=4
.
.
.
It is easy to se that for n>0
If n=0 mod4 then 2^n=6 mod10
if n=1 mod4 then 2^n=2 mod10
If n=2 mod4 then 2^n=4 mod10
if n=3 mod4 then 2^n=8 mod10
As 127=3 mod4 the last digit of 2^127 is 8, and as the last digit of 5^127 is 5 the last digit of:
2^127 + 5^127 -127 is 6. So it does not work.
___________________________________________________________________________________________
Sorry, my eyes do not see well anymore. I am a old man.
I will answer for 157
My solution is correct. The least n is 797. Do not waste your time trying to find another one.
Beyond me. I started looking at this mod n.
Thank you very much, sir. I am bowled over. Frankly.
At 9:24, why did he change 1600c to 100c?
Both 1600 and 100 are -25 mod 125, so OK. But was it necessary?
@@bigjazbo9217 It's just to make the numbers smaller and easier to work with. If you can see 1600 is -25 mod 125 immediately feel free to go for it.
That's a very nice approach! ❤️
The solution is very big but easily understandable 🥰🇧🇩
3:50 wrong as if n is odd then remainder totally depends on n pls recheck!
What do you mean
Isn't there a way tonsolve without using mod at all?
idk but using mod is the most efficient way to solve the problem
Best ☝️
What is this "mod" in mathematics, can you explain me that with a video here?! ...
Look up modular arithmetic and I strongly recommend the youtube channel Michael Penn, he does lots of problems involving mod and has an introduction to it
good problem
HELP PLZ! Why 2^200c = 1 mod 125? Explain plz
Look up eulers theorem
At least do a livestream at 50k.
what about some paper livesolve?
@@prithujsarkar2010 also a good idea
Leave him alone
Everyone please help advertise letsthinkcritically so it reaches 100k >_
@@prithujsarkar2010 bro u here!
Some people wont be able to follow u up sometimes..... Nice video though
daily upload streak: 2
Regular AIME NT bash
Can these problems help me preaparing for ioqm ?
I think 40b - 3 is the answer.
Why did he continue?
we have to find what n is in terms of a positive integer. I got n=797 when I solved this.