A number theory problem from Morocco!

[@jgray2718]

You don't have to check all the divisors of 60. If 30 doesn't work then none of its divisors will work, so you only have to check 12 and 20.

[@aminenajjari9292]

Hello sir i'm morrocan i study mathematical analyse of dynamics system and i'm huge fun of you sir you are a good mathematicien.keep it up

[@cauchy2012]

Mee too🤣🤣🤣🤣

[@abderrahmanyousfi5565]

Kaynin lmgharba tbarkllah had khona nadi

[@tahafen5408]

salam a drari

[@cauchy2012]

Ahh wllah

[@abdelkayoumkaddouri9600]

Mgharba everywhere

[@matthewdoughty3268]

Thank you. You're filling a vacuum on youtube. There aren't many number theory youtubers that communicate as clearly as you do. Pleas keep it up.

[@Tehom1]

Great video. I found a slight shortcut: Instead of finding discrete logs of 2 and 3 for each, I computed 3 times the inverse of 2 and checked it for being 1. It's like multiplying 2^n=3^n by 1/2^n on both sides. Since inverse 2 is always (p+1)/2 this computation is easy.

[@srijanbhowmick9570]

I gave a thumbs up for your kids stomping around upstairs!!!😁😁😁

[@srijanbhowmick9570]

Thanks Michael for the heart!

[@particleonazock2246]

@@aashsyed1277 I can relate

[@tensor131]

Another superb presentation - thank you Michael. I especially like the way you fast forward writing copious text .. if only I could have done that when I was teaching on a board to a class!

[@RexxSchneider]

The last part from around 16:50 is simply wrong. We already know that 2^4 == 3 mod 13 (not 1) etc. Although 3^4 == 3 (mod 13), etc. you can't just strike them out when checking 3^30 and 2^30 because that trick only works when the value is congruent to 1. Otherwise you end up claiming that 2^30 == 4 mod 13, when it's actually congruent to 12 mod 13, and so on. The whole thing has a lot of trial and error ("checking"). If a "checking" method is satisfactory, then you might as well observe that 3^n mod 13 = {3, 9, 1} i.e. it has a low order which reduces the amount of checking. So by inspection you find that 3^n == 2^n mod 13 if and only if n = 4a, where a is a natural number. So we can examine 3^4m - 2^4m which is 81^m - 16^m. That has a factor of (81-16), i,e, it is divisible by 65, which immediately shows its divisibility by 5 and 13. Also, it's worth noting that n>6 since 3^6-2^6 = 665, which is too small to be a multiple of 2015. That leaves the divisibility by 31, which by FLT, we know has a solution at n=30 since both 2^30 and 3^30 are congruent to 1 mod 31. It also has solutions at n=30b where b is a natural number. We do need to consider the divisors of 30, i.e. {1, 2, 3, 5, 6, 10, 15}, but since none of them are of the form 4a, they cannot provide a value that also meets the divisibility by 13 requirement and we can discard them as potential solutions. Optionally, you can check all of the multiples of 4 greater than 6 and less than 30 to satisfy yourself that none of them gives the same remainder for 3^n mod 31 as it does for 2^n mod 31. The smallest value of n that gives 3^n == 2^n mod (5, 13, 31) has to satisfy n=4a and n=30b and so is 60.

[@reeeeeplease1178]

Thats how I would have approached it and I think this is way more straight forward than his solution

[@brexolino1024]

You could use the fact that n must be divisible by 4 (which we get from the mod 13 original calculation) and only check 4, 12 and 20 in the last step

[@stephenbeck7222]

And also immediately cross out everything up to 5 since, e.g., 2^5 and 3^5 are both obviously less than 2015 and not equal to each other.

[@GrimAxel]

Not only that, but if you do due diligence you do indeed find that 30 is the smallest exponent that works mod 31 (powers of 2 repeat in the sequence 2=>4=>8=>16=>1, while 3 seems to be a primitive root based on a couple quick calculations), so the end result *must* be divisible by 30, and none of the multiples of 4 in the divisor list are multiples of 30.

[@udic01]

15:27 you forgot 6

[@Evilpengwinz78]

However: 3^n isn't equal to 2^n for any natural number n, so if 3^n - 2^n divides 2015, 3^n has to be greater than 2015. This means 6 2015. This wipes out a bunch of the possible divisors, including 6 which is missing. Alternatively: Finding that n=30 isn't a solution means factors of 30 can't be solutions either. (3^30)mod2015 not being equal to (2^30)mod2015 implies that the divisors of 30 are also not solutions. The proof is a simple contradiction: If n was a solution then every multiple of n would have to be a solution also, since a mod x = b mod x implies (a^p)mod x = (b^p)mod x for any natural number p. Since n=30 isn't a solution, n=10 and n=15 aren't solutions (and nor is n=6). It would then be a case of simply checking divisors of 60 that aren't divisors of 30, i.e. n=12 and n=20 (also n=4 but that's checked automatically when you check either n=12 or n=20 for the reason above).

[@zecareca42]

Got a handful of nice little questions for you. They were in a IMO training test, and unfortunately I don't know the original font, but here we go: Find all functions f:R->R such that for all real numbers x,y the following is true: f(xf(x+y))=f(yf(x))+x² Let "n" be a odd number bigger than 1. Prove that there's not infinite pairs of positive integers r and s such that (s) (r) (n) + (n) is prime (these are combinations)

[@RMaster7]

For the 1st question, he did a video on a kind of similar question. If you want you can check it out, it's Japanese Math Olympiad, 2004 Q2

[@momomtjiddu3920]

I want to know how many Moroccans are here ?

[@ribsgrowback8459]

Ayyyyyy

[@gameoverplz9121]

Me

[@makeitbetter8439]

Yeeeeees.

[@momomtjiddu3920]

@Khalil Cheddadi hahaha yeess

[@ayoubachaq380]

@@momomtjiddu3920 AYEEH AKHOYAAAAAA

[@fmakofmako]

At 13:55 don't you get a contradiction. Your assumption was that there was a smallest m < 60 that satisfied 2^m = 3^m mod 2015, then showed that there is a remainder r < m where 2^r = 3^r mod 2015. Therefore, you've found an even smaller number that satisfies the equation. Maybe I'm missing something, but it does seem like you'd be done once you've found that contradiction.

[@yurenchu]

No, he wasn't yet done. He's merely showing that if there is a smallest m < 60 that satisfies 2^m = 3^m (mod 2015), then that value of m must be a divisor of 60. Because if m isn't a divisor of 60, then we could show that it would imply that there exists a positive r smaller than m that also satisfies 2^r = 3^r (mod 2015), thereby contradicting the presumption that m was the smallest positive solution. Or in other words: it is a contradiction that shows that it's impossible that m _isn't_ a divisor of 60. That's why we/he can limit the rest of the "proof" to only divisors of 60.

[@nabilmaster12]

in the assumption he assumed that m>0 which he added laterone knowing that 0 verifies the assumption , so we could have r=0 without falling in a contradiction

[@duffahtolla]

@@yurenchu Thank you!! That makes sense. But at 14:20 he wrote r!=0 (otherwise it contradicts..). Should he not have wrote r=0 (otherwise it contradicts..)?

[@davidemasi__]

17:57 aren't 2^4 and 3^4 congruent to 3 (mod 13)? You said they are congruent to 1 (mod 13)

[@maosatela]

yes you are right

[@pandas896]

😀

[@cezarygalinski9420]

Yes, but the point is that they are congruent to each other and that’s everything needed for the solution.

[@nabilmaster12]

yes you're absolutely right , but in fact since from 2^12=1 mod13 we get 2^30=2^6=64=-1=12 mod13 and from 3^12=1 mod13 we get 3^30=3^6=(3^3)^2=27^2=1^2=1 mod13 , we conclude indeed that 2^30#3^30 mod13 .

[@alborzalborzi3845]

There is one divisor for 31 in the range of 1

[@abderrahimelouafi1373]

Nice problem from Morocco, my country! . Go on , you're Amazing !👍👌

[@Blabla0124]

small typo at 15:15: 6 is also a divisor

[@kevinmartin7760]

[1-1]At 19:40, doesn't eliminating 30 as a possible solution automatically eliminate all the factors of 30, leaving only 4, 12, and 20 to check (and eliminating 20 eliminates 4 leaving only 12 to check). For example, 6 being a valid solution (it isn't) would imply that all multiples of 6 are also valid solutions, so disproving 30 as a solution automatically eliminates 6 as well. Actually, all the work after showing that a solution smaller than 60 must be a factor of 60 seems pointless to me. Because 60 is the lcm of 2, 4, and 30 (and is not equal to 2, 4, or 30) all the factors of 60 (other than 60 itself) fail to be a multiple of at least one of these three numbers and so fail one of the original three congruence checks (on 5, 13, and 31) and so fail the mod 2015 check as well.

[@MD-pg1fh]

Do all n that make 2^n = 3^n need to be multiples of the smallest such number? If yes, your proof holds, but then you need to prove that.

[@kevinmartin7760]

@@MD-pg1fh That's not necessary for what I said. [2-1]I rely on the fact that any multiple of a smaller solution is also a solution, which is nearly trivial to show. [2-2] If 2^n = 3^n then clearly (2^n)^k = (3^n)^k is also true, and the latter can be rewritten as [2-3] 2^(nk) = 3^(nk) [2-4] and thus nk is also a solution. Back to the specific example, if n=6 were a solution, then n=30 would also be a solution, but we know n=30 is *not* a solution so neither is n=6 (nor any other factor of 30). Whether there are other solutions which are not a multiple of the smallest solution is irrelevant.

[@nabilmaster12]

your first remark is totally on point , but your second remark can be applied only for 3 ,5 &15 which will be eliminated since they're not multiples of any of the numbers 2,4 & 30 , but the same thing can't be said about the other divisors(or factors as you call them) since everyone of them is a multiple of one the numbers 2,4 & 30 except 1 which also can't be eliminated right away like the numbers 3 ,5 &15 since 1 is inferior than all the numbers 2,4 & 30 , eventhough 1 is clearly eliminated (2#3 mod 2015) but i'm talking regarding your approach .

[@kevinmartin7760]

@@nabilmaster12 I'm a bit lost as to what you are calling my "first remark" and "second remark" since I have 2 comments each containing more than one point, especially since your comment does not address the specific example of 6 which I used. For future reference I'll number the statements herein. I'll also see if I can edit my former comments to add numbers. The logic seems straightforward to me: [3-1] (k is a solution) => (mk is a solution) for all k, m elements of N [=> is "implies"] as demonstrated in my second comment (items [2-*]). [3-2] This is of the form p => q which is equivalent to ~q=>~p which in this case is: [3-3] (mk is not a solution) => (k is not a solution) for all k, m elements of N. [3-4] In this specific case I mentioned, mk is 30, k is 6 and m is 5. [3-5] More generally for this particular problem, mk is 30, k is a factor of 30, and m is 30/k which we know is a natural number because k is a factor of 30. [3-6] So 30 being shown not to be a solution eliminates all the other solutions in the list except 4, 12, and 20. [3-7] Eliminating 20 by evaluating the sides of the original formula (2^n#3^n mod 2015) thus also eliminates all the factors of 20, and so removes 4 from the list leaving only 15. [3-8] 15 is eliminated by evaluating the original formula using n=15. There is nothing here which depends on how the prime factors of mk are split between m and k, and in particular whether or not k is a multiple of 2, 4, or 30.

[@chrisbattey]

Once you've established that 2^n = 3^n (mod 31) only when n is a multiple of 30, and 2^n = 3^n (mod 13) only when n is a multiple of 4, you shouldn't have to do any more exhaustive checking to prove that n = lcm(4,30) = 60 is the smallest possible n. If two numbers are congruent modulo some composite number, then they must be congruent modulo each of that composite's factors: a = b (mod pq) => a - b is divisible by pq => a - b is divisible by p => a = b (mod p). So any n < 60 such that 2^n = 3^n (mod 2015) would have to also satisfy the congruence modulo each of its factors, which would mean being a multiple of both 4 and 30 - but there is no such number below lcm(4, 30) = 60, because that's the definition of LCM.

[@toddtrimble2555]

A few notes: one can just compute the order of 3 times 2^{-1} = 3 times 1008 mod 2015, which is 4 mod 5, 8 mod 13, and 17 mod 31. The order will be the lcm of the orders of 4 mod 5, 8 mod 13, and 17 mod 31. The first two are 2 and 4, respectively. For the last, just check that the order of 17 mod 31 isn't 30/5 or 30/3 or 30/2, so it must be 30. The lcm of 2, 4, 30 is 60. Incidentally, some time could have been saved in solving 2^n = 3^n mod 13, since checking just two cases for n suffices: 12/2 and 12/3.

[@goodplacetostop2973]

1:57 👍 20:02 هذا مكان جيد للتوقف Homework... The sum to infinity of a geometric progression is 6. The sum to infinity of the squares of each term in the progression is 12. Find the sum to infinity of the cubes of each term in the progression.

[@noahtaul]

216/7

[@srijanbhowmick9570]

Is is 216/7? Let, First term = a Common ratio = r Since sum to infinity of this G.P. is a finite number , hence |r| < 1 For first G.P. , S(infinity) = a/(1-r) = 6 [Given] => a = 6(1-r) --- (i) For second G.P. , a^2 , (ar)^2 , (a(r^2))^2 , ... => a^2 , (a^2)*(r^2) , (a^2)*(r^4) , ... Thus, First term = a^2 Common ratio = r^2 S(infinity) = (a^2)/(1-(r^2)) = 12 [Given] => {36*(1-r)^2}/{(1-r)(1+r)} = 12 [From (i)] Cancelling (1-r) from both numerator and denominator , we get :-- => {36(1-r)}/(1+r) = 12 [Since "r" isn't equal to 1 hence we can cancel the (1-r) term] => 3-3r = 1+r => 2 = 4r => r = 1/2 Thus, a = 6*(1-0.5) [From (i)] => a = 6*0.5 = 3 Similarly for 3rd G.P. , First term = a^3 = 3^3 = 27 Common ratio = r^3 = (1/2)^3 = 1/8 S(infinity) = (a^3)/(1-(r^3)) = 27/(1-(1/8)) = 27/(7/8) = (27*8)/7 = 216/7

[@shreyamjha3058]

216/7 ,its a pretty easy one,just used basics of infinite gp and got a good place to stop..😁

[@shivanggoyal7280]

Quite easy compared to what you usually give

[@goodplacetostop2973]

@@shivanggoyal7280 Well, it’s not supposed to be hard every day 😛 On top of that, some “hard” exercises were easy to solve for some people and some “easy" were actually hard for others. I’m just posting whatever I feel it could be a good one

[@krisbrandenberger544]

@ 19:00 2^30 should be congruent to -1 mod 13 and 3^30 should be congruent to 1 mod 13.

[@jamieee472]

Consider S, the solution set of n for this problem. in 13:45 we showed that: ∃ m = min(S) < 60 ⟹ 2^r ≡ 3^r (mod 2015) ⟹ r ∈ S where r < m = min(S) ⟹ contradiction. This should be sufficient to argue ∄ m

[@tahirimathscienceonlinetea4273]

It's a great work man I'm from morocco too

[@crazy4hitman755]

I don’t understand why we should show that 60 is the smallest isn’t it obvious.

[@cr1216]

Because he did not formally prove that if 2^m = 3^m (mod p) then m | p-1 in the first part. I agree the whole procedure is kind of ugly, a better way is to prove the above fact in the first part and then prove the LCM is the smallest mod 2015 using the fact.

[@이동의-q5b]

@@cr1216 that's right. But he use the fact. So it's a little bit unnatural.

[@mabdullahkhan4795]

well smallest one is actually 28 💀

[@klausg1843]

A short version: 5 divides f(n)=3^n - 2^n only when n is equal. So n=2m. Then f(n)= (3^m)^2 - (2^m)^2 = (3^m+2^m)•(3^m-2^m). Now by Fermat little 31 divides 3^30 - 2^30. Since 3^30 = (3^4)^7•9=4 mod 5 and 2^30 = (2^4)^7•4=4 mod 5, 5 divides also 3^30 - 2^30. Now 3^30= (3^12)^2•3^6=81•9=27=1mod 13 and 2^30= (2^12)^2•2^6=64=-1 mod 13, so 13 divides the other factor 3^30 +2^30. Conclusion 2015 divides f(60). And the rest follows as shown in the video.

[@nailabenali7488]

Yeaaay! You did one of the most famous problem in my country! Thank you ✌🏻

[@mamatamohanty6417]

sir there is a simple solution 3^n-2^n is always divisible by 3+2 =5 expanding the equation we can know that(bionomial)or 3-2=1

[@lmxqlmxq]

I don’t have time today, but when I saw this new video was up- I clicked and liked it, then I added it to Watch Later and now I’m going back to my other things

[@shalvagang951]

he is a very good person i also likes him because he never asks about to subscribe

[@MTd2]

Please, continue with the Rogers-Ramanujan Identities series!

[@TedHopp]

At 17:58, you say that, from the previous analysis, 2^4 and 3^4 are both congruent to 1 mod 13. That is wrong. The previous analysis only showed that 2^4 is equivalent to 3^4 mod 13, not that they are equivalent to 1 (which they are not). Fortunately for the rest of the analysis, that result is all that's needed to allow cancellation.

[@frozenmoon998]

I gave a like not only because the video was very educational, but also because of 1:56

[@Tiqerboy]

I thought you videoed all these presentations at an educational institution. So, in an earlier video I heard a dog barking, thinking "that's strange" and now you have a comment of your kids stomping around upstairs. Not many of us have a tiger sized blackboard in our home.

[@stephenbeck7222]

Based on the gray cement looking wall, I always thought he films in his basement. There are a few videos where you see his kid running around with his head just popping up on the bottom of the frame, making me really amazed Michael can film a math lesson with a little kid in the same room not making a peep. I am sure he spent at least a couple hundred dollars on the chalkboard installation. I wonder if his university subsidized it for his remote class lectures (which seem to have started a couple years before the pandemic based on his video playlists).

[@vishalmishra3046]

One liner solution scanning a larger search space |> python -c 'print ( [ n for n in range(1000) if (3**n - 2**n) % 2015 == 0 ] )' [0, 60, 120, 180, 240, 300, 360, 420, 480, 540, 600, 660, 720, 780, 840, 900, 960]

[@ciprianburduja8249]

Problem BJ12. The number 𝐵 = 𝑎1𝑎2𝑎3… 𝑎𝑛𝑎1𝑎2𝑎3… 𝑎𝑛 is called the repetition of the natural number nonzero 𝐴 = 𝑎1𝑎2𝑎3… 𝑎𝑛. Show that there are an infinity of natural numbers, whose repetition is a perfect square.It is a Moldovian olympiad problem

[@factorial1059]

"ai" are digits?

[@alikaperdue]

6 is a divisor of 60 @15:11

[@robertgerbicz]

Overcomplicated solution in many ways. Basically the problem asks the order of (2/3) modulo 2015. Because 2^n==3^n mod 2015 if and only if (2/3)^n==1 mod 2015. From this an easy number theory computer solution with Pari-gp: znorder(Mod(2/3,2015)) and it gives 60. Otherwise the paper-pencil solution, find the order modulo the prime(powers) of 2015 what you did. And take the lcm of these orders lcm(2,4,30)=60, that will be the solution in all case, you don't need that lengthy explanation from 11:02.

[@Walczyk]

what happened to 6? it divides 60 :(

[@MrRyanroberson1]

so the trick for checking factors of 60: list its prime factorization and then poke for "which factors can be removed". by testing 30, you know the smallest needs a factor of 4. So next we poke 3, and then 5. once all of those have been tested, it's impossible outright. So: 2^20 ? 3^20, but mod 31 we already know 30 is the smallest value. 2^12 ? 3^12, again 31 thwarts this.

[@robertingliskennedy]

coherent, slick, and therefore most enjoyable, thanks

[@quantabot1165]

We are happy you take time from your busy schedule to teach us. 86K

[@OmarOmar-cj9rk]

Morocco! شكرا على الڤيديو

[@oder4876]

Think you so much but First of all you need to flip the numbers 2^n & 3^n because 3^2 congurent to 2^2 not the opposite and "3^4 & 2^4 congurent to 3 (mod13)" that because 2^4 and 3^4 are not prime to 13 " 3^4 = 13x6 +3 2^4 =13x1+3" but i will give you like for your hard work peace and keep going

[@wesleydeng71]

I don't think the second half is necessary. Because the reminders of powers are cyclic so you just need to show the periods. How long will it take a student to finish this problem in the competition if he were to use the method shown in the video?

[@PavelB123]

There are two nice tricks built into the problem 3 = -2 mod 5 and 9 = -4 mod 13. So 3^n = 2^n mod 5 is just (-2)^n = 2^n mod 5 so n is even. Then 3^(2m)=2^(2m) is (-4)^m=4^m mod 13 so m is even too.

[@vcvartak7111]

It's good that you reminded me the fermats theorem.

[@reeeeeplease1178]

At the very end, since m=30 doesnt work, all of the divisors of 30 dont work either. So we are left with 4, 12 and 20. Same spiel: Check 20, rule it and 4 out Check 12, rule it out Why this works? If 2^n == 3^n then 2^(kn) == 3^(kn), should be fairly obvious with modular arithmetic ( == denotes congruence) Using the contrapositive: If 2^(kn) is not congruent to 3^(kn) then neither are 2^n and 3^n. Now you would just factor 30 and set k and n to the respective factors.

[@jerrymouse3420]

it was a great problem..and coincidentally,my own solution completely matched with your's!!

[@cecilhenry9908]

As an engineer with no contact with number theory, I had no idea of the importance of modulo analysis everywhere!

[@MTd2]

I guess it must suit clock engineers!

[@JM-us3fr]

Modular arithmetic is pretty important in cryptography, but I think it first started being applied in early gear-based computers/calculators. It's also a good intro to group theory, which forms the foundation for all symmetry.

[@cecilhenry9908]

@@JM-us3fr Yeah, its the basis of Diffie-Hellman key exchange. That's the only area I'd ever seen it applied. But its clearly big in number theory.

[@prathikkannan3324]

how would u check there are no other integers less than 30 satisfying 2^n = 3^n(mod 31). ?

[@bridgeon7502]

Fermat had to be trolling when he named that "Fermat's little theorem"

[@youssefeljouhari7418]

I m big fan of you sir. Very smart solution espcially how to show that 60 is the smallsest sollution

[@abusoumaya8469]

my beloved country ❤❤❤ my greetings and love

[@Учимсявместе-т9о]

Why u dont want to say that if n is the smollest number such that 2^n=3^n(mod k) it implise that if 2^m=3^m (k), n|m. If u use that fact more correctly, u dont need to look for all this devides of 60.

[@DavidSavinainen]

You showed that 3^30 is not congruent to 2^30 mod 2015. Now, say for example that 3^10 was congruent to 2^10 mod 2015. That would directly imply that (3^10)^n would be congruent to (2^10)^n for any natural number n, including 3, which would contradict the top claim. Using an argument like this, could I not exclude all divisors of 30 after showing that 30 did not work? Then, I’d only have to check the few that aren’t divisors of 30, like 20 and 12

[@samyachakraborty263]

hello michael , isnt it enough after we see that for some r less than m the condition still holds, and thus its a contradiction and conclude 60 is the smallest such no . am i missing something here ?

[@ChristopherBitti]

We need the smallest n such that 2015 = 5 * 13 * 31 divides 3^n - 2^n which is equivalent to finding the smallest n such that 3^n = 2^n (mod 5) AND (mod 13) AND (mod 31) by the Chinese Remainder Theorem Note that mod 5, 2 and 3 are multiplicative inverses, so the equation 3^n = 2^n can be rewritten as (3^n)^2 = 1 (mod 5), or (-1)^n = 1 (mod 5). Thus, n has to be even. Now we're working mod 13. Note that 7 is the inverse of 2 (mod 13), so we can change 3^n = 2^n (mod 13) to 8^n = 1 (mod 13), or 2^(3n) = 1 (mod 13). The order of 2 mod 13 is 12, so we need 3n to be divisible by 12, or in other words, we need n to be divisible by 4. Now, let's finish this off by working mod 31. The inverse of 2 mod 31 is 16. Thus, solving 3^n = 2^n (mod 31) equates to solving (3*16)^n = 1 (mod 31) or 17^n = 1 (mod 31). The order of 17 mod 31 is 30 (enjoy verifying this), so n needs to be divisible by 30. Thus, we need n to be divisible by 30, 4, and 2. The LCM of these numbers, which is 60, is our answer.

[@OH-pc5jx]

doesn’t 30 not working automatically knock out 1,2,3,5,6,10,15 as well?

[@marshalls36]

n = 2/log(1.5) x log {(165+13m)/165-13m)}, where m = multiple of 2015

[@swordwaker7749]

I got 60 through brute force. Sometimes an ounce of computation is better than a pound of math. i = 1 while pow(3,i,2015)!= pow(2,i,2015): i += 1 print(i)

[@yurenchu]

Writing code is easy; but does it help in gaining more mathematical insights and skills?

[@swordwaker7749]

@@yurenchu I normally consider python a valid tool in internet problems unless stated otherwise.

[@yurenchu]

@@swordwaker7749 That's not what I asked though.

[@swordwaker7749]

@@yurenchu Back to the original question... of course. In fact, when you write code, you will get less distracted by certain computational aspects of humans, such as a "cool trick" where you could test if numbers can be divided by 3 by adding up its digits, when you code, you will realize that this formula is just a gimmick of base-10 arithmetic rather than anything special. When you code, you will understand what matters and what doesn't really matter, for example you wil understand the importance of euclid's algorithm better. I find computer a valid tool to solve online math problems, without it, the brain would be spent on manual computation rather than the actual creative part, and the creativity will be limited due to extremely limited computational capability of human.

[@swordwaker7749]

@@gregorymorse8423 Use fermat's little theorem? I'm not sure about that. I'm not sure if the problem would be difficult cuz I only stumbled upon it. Could've optimized the loop a bit if the number was larger, but it wasn't necessary. I watched the video with a hope of some ingenuity, but the solution described was ultimately another form of trial and error. And yes, I did some programming problems on hackerrank, but I'm ultimately not good at number theory, unlike cryptographers.

[@justacockypersonontheinter6889]

Hi, Great video btw! but I feel like the induction proof at the end that 60 is the smallest n number is one of the proofs that could be given. Perhaps using a logical argument that you have chosen the smallest n1, n2, and n3 for primes of 2015 and therefore the multiple of the minimum exponent (n1,2,3) of each prime is the minimum exponent of 2015. Not sure how the formal proof would look like if this route were chosen instead of by induction approach though :) Also, pretty sure you've said that r has to be equal to zero (r=0) but you wrote on the board r is not equal to zero (I guess it is nitpicking at this point haha). I might be mistaken though. Thanks for the video again, Cheers

[@TheQEDRoom]

I totally forgot LFT. So What I did was calculate the modulo for 5, 13 and 31 starting from n=1.

[@ellenmarch3095]

By FLT, 5, 13, 31 => 4, 12, 30|n. Lowest common denominator = 60. Done.

[@nullplan01]

At this point, isn't it just easier to list all possible 2^n and 3^n (mod 2015) for n=1..59?

[@wolframhuttermann7519]

It is even easier to prove. We know that 2015 = 5 * 13 * 31. By Fermat's theorem, we know that 5 | a^4-1, 13 | a^12 -1 and 31 | a^30-1 if a is coprime to 2015. The least common multiple of 4, 12 and 30 is 60. So if 2015 divides 3^t-2^t, t being minimal, then t is a divisor of 60. This very aribas snippet checks all the possibilities: Divisors60 := (1, 2, 3, 4, 5, 6, 12, 15, 30, 60); for i := 0 to length(Divisors60)-1 do divisor := Divisors60[i]; if 2 ** divisor mod 2015 = 3 ** divisor mod 2015 then writeln(i); end; end. If you run you will get 60.

[@mathboy8188]

A quick way is to show that 3^n = 2^n mod 5 forces n to be even. Then n=2m and 9^m=4^m mod 13 forces m even. Then n = 4k and 81^k=16^k mod 31 forces 7^k = 1 mod 31, which has the smallest positive k that works being k = 15. Thus n = 4(15) = 60 is the smallest that works, making 3^n congruent to 2^n mod 5, and mod 13, and mod 31. Details: 3^n = 2^n mod 5 iff 2^n = (-2)^n mod 5 iff (-1)^n = 1 mod 5 iff n even. (Holds whenever n even... and when n odd says -1 = 1 mod 5, so 2 = 0 mod 5, which is nonsense.) So n = 2m and have 9^m = 4^m mod 2015. Then 9^m = 4^m mod 13 iff (-4)^m = 4^m mod 13 iff (-1)^m = 1 mod 13, iff m even. So m = 2k and have 81^k = 16^k mod 2015. Then 81^k = 16^k mod 31 iff (81-3*31)^k = 16^k mod 31 iff (-12)^k = 16^k mod 31 iff 4^k (-3)^k = 4^k (4^k) mod 31 iff (-3)^k = 4^k mod 31 iff (28)^k = 4^k mod 31 iff 4^k 7^k = 4^k mod 31 iff 7^k = 1 mod 31. Since 7^30 = 1 mod 31, have k > 1 and k divides 30, so k in { 2, 3, 5, 6, 10, 15, 30 }. Checking shows smallest is when k=15, so 7^15 = 1. Thus n = 2m = 2(2k) = 4 k = 4(15) = 60 is the smallest possible, and by this procedure know it will work mod 5, and mod 13, and mod 31, hence it will work mod 2015. [ About testing 7^k mod 31, where k in { 2, 3, 5, 6, 10, 15, 30 }. For modular computing of big powers, knock them down as you go while hunting for small values to exploit. 7^2 = 49 = 18 = -13 mod 31. 7^3 = (-13)(7) = -91 = 93 - 91 = 2 mod 31. Hereafter exploit that nice & small relation 7^3 = 2 mod 31. 7^5 = 7^2 7^3 = 49 (2) = 18(2) = 36 = 5 mod 31. 7^6 = (7^3)^2 = 2^2 = 4 mod 31. 7^10 = 7 (7^3)^3 = 7 (2)^3 = 7(8) = 56 = 56 - 62 = -6 mod 31 7^15 = (7^3)^5 = 2^5 = 32 = 1 mod 31. ]

[@samrubenabraham6979]

@MichaelPenn , Try Brocard's Problem (aka the Brocard-Ramanujan problem)

[@nournote]

Oh! Thank you so much! You did read my email :)

[@BMK5298]

Hi Noureddine . I hope that you are doing well I want to ask you to give some name of books that can improve e my capacity in problem solving

[@cauchy2012]

Wach had chi watani diyal l'arithmétique

[@zaidjanati03]

@@cauchy2012 laa hada ymkn d olympiades

[@nournote]

@@cauchy2012 Non. Olympiade sc. maths. 2015. www.men.gov.ma/Ar/Documents/C-excellence_ancEpr/S6NMaO2015.pdf

[@nournote]

@@BMK5298 Passe ton email.

[@cinedeautor6642]

I think this problem could solve with theorem Lagrange in theory of groups

[@BenfanichAbderrahmane]

Heey , m a follower from morroco

[@noname-jv6hx]

take n=26 it will give smallest multiple of 2015

[@copyrightfreemusicforall5563]

sir, plz give more interesting problem about number theory

[@RexxSchneider]

I should add that there is a deductive proof that 60 satisfies 3^n - 2^n ≡ 0 mod 2015 using primitive roots. 2015 = 5*13*31 and the smallest primitive roots of those primes are 2, 2, 3 respectively. That means that we can always find a power of 2 ≡ any desired integer mod 5 and the same is true for powers of 2 mod 13 and powers of 3 mod 31. We can work out that 3 ≡ 2^3 mod 5, so we can write 3^n mod 5 as 2^3n mod 5, giving 2^3n ≡ 2^n mod 5 and that implies that 3n ≡ n mod 4, so 2n ≡ 0 mod 4, or 2n = 4k, which means n = 2k. Similarly, 3 ≡ 2^4 mod 13, so 3^n mod 13 ≡ 2^4n mod 13, giving 2^4n ≡ 2^n mod 13. That gives 4n ≡ n mod 12, yielding 3n ≡ 0 mod 12, or 3n = 12k, which means n = 4k. Finally, using 3 as the root for mod 31, we find that 3 ≡ 2^24 mod 31, giving 3^n ≡ 3^24n mod 31. So n ≡ 24n mod 30, or 23n ≡ 0 mod 30. That is equivalent to n = 30k. That shows that n has to be a multiple of 2 to satisfy the mod 5 requirement, a multiple of 4 to satisfy the mod 13 requirement, and a multiple of 30 to satisfy the mod 31 requirement. The smallest number that is a multiple of 2, 4, and 30 is their LCM = 60.

[@udic01]

Why cant we argue that since 60 is the lcm of the 2,4,30 bo smaller nunber than it can satisfy all 3 conditions (mod 5,13,31)?

[@thiantromp6607]

We didn't fully prove that there was no number smaller than 30 in the mod 31 case

[@udic01]

@@thiantromp6607 9:04 he said we can prove it by checking in a similar way to the 5 & 13 cases and see that none of it's divisors satisfy the condition. Hence 30 is the smallest for the 31 case.

[@goodplacetostart9099]

Good Place To Start at 2:06

[@Yougottacryforthis]

Some group theory and introduction of "order of element" and you only have to do first 12 mins of video or so :)

[@ufailowell]

Apparently doubles do not work for programming this in C#. Not sure why but I guess you have to use decimals

[@jamieee472]

probably due to floating point precision error

[@arturjorge5607]

this problem with primitive roots and discrete logarithms was so simple

[@mayankrs2016]

Here all the primes factors were unique, Could we have done the same if there was a prime factor which repeated

[@md2perpe]

At the end, if we have eliminated m=30 as a possibility, haven't we then also eliminated all the divisors of 30 as possibilities?

[@nabilmaster12]

you're absolutely right

[@stevenvanhulle7242]

30 was eliminated because it's not a multiple of 4.

[@md2perpe]

@@stevenvanhulle7242 That was not an answer to my question.

[@uditagarwal10]

Sir please tell how can we develop this type of mathematical thinking and reasoning

[@arekkrolak6320]

actually it is very easy to prove 3^n-2^n | 5 n is even and also that n | 4 => 3^n - 2^n | 13, but I couldn't find solution for 31 :)

[@alexander_adnan]

Thanks Bro.

[@treyebillups8602]

I plugged in [(3^60)-(2^60)]/2015 in my calculator and it didn't come out as an integer. Is there something wrong with the calculator?

[@nournote]

That simply means that your calculator can't calculate 2^60, which is predictable.

[@dominickmancine6033]

My calculator handles about 12 significant digits. Once numbers get larger than that it stores them in scientific notation, keeping only the 12 most significant digits. (But even then it can't handle powers of 10 greater than 99.) Since 2^60 has about 20 significant digits, and 3^60 has at least 10 more than that, my calculator would drop many of the least significant digits. That's fine if I'm measuring the distance to Alpha Centauri in millimeters, but not so good for number theory.

[@yurenchu]

@@dominickmancine6033 - "Since 2^60 has about 20 significant digits, and 3^60 has at least 10 more than that" Just for the record: 2^60 is a 19-digit number, and 3^60 is a 29-digit number. By the way, I feel that I should also point out that (for example) 10! = 3628800 has only _five_ significant digits, not seven.

[@nournote]

@id523a Either way, calculators in general are not designed for number theory computations. Rather for scientific calculations where approximations are the goal.

[@heldercomp]

There's another way to prove n = 60 is the minimum. Let p(n) = 3^n - 2^n and suppose the solution is m such that 1 < m < 60. First, we can see that p(30) = 3^6 - 2^6 = 2 (mod 13), so m cannot be 30. Then, clearly 2015 | p(60)-p(m), and since 3^m = 2^m (mod 2015) => 2015 | p(60-m).2^m. That means 2015 | p(60-m) and 60-m is another solution. Since m and 60-m are both solutions, and m is minimum, then m < 30. Now 31 | p(30), but now 31 | p(m). This means that 31 | p(30)-p(m), and by the same argument 31 | p(30-m). At least one of the two (m, 30-m) must be less than 15. All we need to check is if there's k such that 31 | p(k) with k < 15. It's straightforward.

[@maosatela]

the second part is unnecessary because if n1,n2,n3 are the smallest possible numbers that satisfy 2^n1=3^n1mod5 2^n2=3^n2mod13 2^n3=3^n3mod31 then for n=lcm(n1,n2,n3) 2^n=3^nmod(5*13*31) is the smallest solution In fact the proof is similar to the proof you did in this video about checking only the divisors of 60

[@nabilmaster12]

but you have to keep in mind that if it wasnt for the statement proved in the second part , it wouldnt have been easy to determine the least power giving congruation espacially in the case of 30 , in which case we would have needed to check all the powers starting from 1 up to 29 , just imagine that !!!!!!

[@frdjo2065]

And 6 is also a divisor of 60

[@frdjo2065]

But very great explanation. Thanks for making people smarter !

[@samyakmahapatra9154]

Find smallest number such that n divides 2^n-2 but n does not divide 3^n-3 Plz solve this Michael penn sir

[@chhabisarkar9057]

Waah

[@spegee5332]

4? this isn't hard with casework

[@chhabisarkar9057]

@@spegee5332 lol no it says does not divide

[@chhabisarkar9057]

@@spegee5332 16- 2 = 14 and 4 does not divide 14 so it's not gonna work

[@samyakmahapatra9154]

4 will not divide 2⁴-2 , sorry

[@yoyoyo007123]

literally 30 sec and 1 line: print([n for n in range(1,10000) if (3**n - 2**n) % 2015==0][0])

[@wydadiyoun]

كاين شي مغاربة هنا؟

[@gameoverplz9121]

انا 👋👋 كم كنحماق على هاد خونا واعر بزاف

[@seroujghazarian6343]

15:20 is 6 a joke to you?

[@sjoerdo6988]

If N includes 0, then n=0 is the smallest solution.

[@nournote]

That's a definition problem. In the US, they usually define N as {1, 2, 3,...} Where in other countries N is {0, 1, 2, ...} and N without 0 is referred as N*

[@thomasaskew1985]

I ran the function through Excel and got 37. Where did I go wrong?

[@stevenvanhulle7242]

Excel's numeric precision is way too low. Large numbers will be expressed in scientific notation, with something like 15 digits for the mantisse. Truncation causes errors. FYI, 3^60 - 2^60 = 42391158274063282009687586225, which is a 29-digit number. You'll need an arbitrary precision calculator for that or use special math software, like Mathematica, which is what I did.

[@thomasaskew1985]

@@stevenvanhulle7242 Okay. Now I get it. Thanks, Steven. I knew something must be amiss.

[@iamadooddood4331]

Poor 6. Doomed to be forgotten forever.

[@8d_songs]

Why does youtube recomend this to me, just that I'm from morocco 🤔🤔

[@CStrik3r]

The almighty recommendation algorithm a 3shiri

[@yurenchu]

I don't understand why we still have to check the divisors of 60 and prove that 60 is the smallest solution. We've already determined that 3^n - 2^n = 0 (mod 5) requires n = 0 (mod 2) 3^n - 2^n = 0 (mod 13) requires n = 0 (mod 4) 3^n - 2^n = 0 (mod 31) requires n = 0 (mod 30) Don't those three conditions already mean that n must be a multiple of the smallest common multiple of 2, 4 and 30? (In other words, that n must be a multiple of 60?) The divisors of 60 (and hence the possible values of m) are 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30 and 60. But if m < 30, then we cannot have 3^m - 2^m = 0 (mod 31), because any m < 30 isn't a multiple of 30. And if m = 30, then we cannot have 3^m - 2^m = 0 (mod 13), because 30 is not a multiple of 4. In other words, each of the divisors of 60 (other than 60 itself) is going to give a problem with at least one of the three conditions that we've already established; if not, then 60 wouldn't have been the smallest common multiple of 2, 4 and 30. Is there something that I'm missing here? Why couldn't we already conclude at the 11 minute time mark that n = 60 is the smallest solution?

[@cezarygalinski9420]

I am wondering the same thing. For any exponent we can write, for example for division by 31: 2^(30q+r)=2^30q*2^r=2^r (mod 31) and 3^(30q+r)=3^30q*3^r=3^r (mod 31) So if 2^(30q+r)=3^(30q+r) (mod 31) then 3^r=2^r (mod 31). We know that 0

[@nabilmaster12]

if we follow the logic you mentioned regading 30, then since 3^60 - 2^60 = 0 (mod 31) (60 being a multiple of 30) , we cannot have 3^30 - 2^30 = 0 (mod 31) because 30 is not a multiple of 60 , and that is obviously false . in other words , being a multiple here is a sufficient condition not a necessary one . so you have to take advantage of the statement proved laterone to eliminate the powers less than 30 , 4 & 2 , the task that micheal assumed being done at minute 11 ; so the very last part when he was checking the divisors of 60 was really unnecessery . hope I explained it to you

[@cezarygalinski9420]

But we have proven that 30 is indeed the smallest positive natural m that satisfies 3^m=2^m (mod 31) So there can’t be any smaller m’s. The same logic can’t be applied to 60 bacause we haven’t proven that it is the smallest m satisfying congruence above. We cannot prove it, bacause it is not true

[@yurenchu]

@Cezary Galiński Thanks for your replies. Sorry, I don't follow what you're doing in your first reply. Why are you raising to the power of (30q+r)? Why would you require 2^(30q+r) to be equal to 3^(30q+r) (mod 31) ? - "The same can be said for division by 13 and 5" Not really, because for example for division by 13 we can't write 2^(4q+r) = 2^(4q) * 2^r = 2^r (mod 13) and 3^(4q+r) = 3^(4q) * 3^r = 3^r (mod 13) (because those two statements are _false_ unless q is a multiple of 3), and hence we wouldn't (yet) be able to draw the conclusion: "so if 2^(4q+r)=3^(4q+r) (mod 13) then 3^r=2^r (mod 13)." By the way, I'm not the person who created this video or who owns/manages this youtube channel. I'm just another youtube viewer, just like you.

[@yurenchu]

@@nabilmaster12 - "if we follow the logic you mentioned regading 30, then since 3^60 - 2^60 = 0 (mod 31) (60 being a multiple of 30) , we cannot have 3^30 - 2^30 = 0 (mod 31) because 30 is not a multiple of 60 , and that is obviously false " Is this addressed to me, or to the other replier (@Cezary Galiński)? If to me, I don't see how what you're saying here resembles anything that I've previously written in my comment. Each of the following four statements is independently correct: 3^n - 2^n = 0 (mod 5) requires n = 0 (mod 2) 3^n - 2^n = 0 (mod 13) requires n = 0 (mod 4) 3^n - 2^n = 0 (mod 31) requires n = 0 (mod 30) 3^n - 2^n = 0 (mod 2015) requires n = 0 (mod 60) Nowhere have I said or implied that 3^n - 2^n = 0 (mod 31) requires n to be a multiple of 60. So I have no idea where your "30 is not a multiple of 60" statement is coming from. - "so you have to take advantage of the statement proved laterone to eliminate the powers less than 30 , 4 & 2 " Which statement are you referring to? (I assume "laterone" means "later on", but how much later, and later than what?)

[@worldnotworld]

What do you mean, "from Morocco?"

[@MORISENSEIISGOD]

I find it's easier to list out 3^n and 2^n (mod 5) for 1, 2, 3, 4 and find that they are congruent if n is even. Then 3^n and 2^n (mod13) for 1,2,3,...12, and notice they are congruent if n is a multiple of 4. Then for mod 31, I went through n=4,8,12 etc. 2^n (mod31) is a cycle of 16, 8,4,2,1,16,8,4,2,1 etc. For n=4,8,12..., 3^n (mod 31) forms a Fibonacci sequence in mod 31: 19, 20, 8, 28, 5,2,7, etc. In fact all values of n that have the same residue in mod 4, still form a Fibonacci sequence in mod 31. A proof of this: 3^8 is congruent so 20 (mod31) which is congruent to 82. Let a be a positive integer, or 0. therefore 3^(a+8) congruent to 82*3^a=(1+3^4)*3^a = 3^a+3^(a+4) therefore 3^(a+8) is congruent to 3^a+3^(a+4) in mod 31. Then just form the Fibonacci sequence in mod 31 for 3^n for n=4,8,12,... ,60 and observe that 60 is the first value where 3^n is congruent to 2^n mod 31.

[@dneary]

3^{15}-2^{15}=0 (mod 31)

[@jbrabbitoh1122]

No, 3^15=-1 (mod 31) 2^15= 1 (mod 31)

[@mehmeterciyas6844]

How old are you?