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.

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

3 жыл бұрын

Mee too🤣🤣🤣🤣

@abderrahmanyousfi5565

3 жыл бұрын

Kaynin lmgharba tbarkllah had khona nadi

@tahafen5408

3 жыл бұрын

salam a drari

@cauchy2012

3 жыл бұрын

Ahh wllah

@abdelkayoumkaddouri9600

3 жыл бұрын

Mgharba everywhere

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.

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

@srijanbhowmick9570

3 жыл бұрын

Thanks Michael for the heart!

@particleonazock2246

2 жыл бұрын

@@aashsyed1277 I can relate

15:27 you forgot 6

@Evilpengwinz78

3 жыл бұрын

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).

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.

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!

I want to know how many Moroccans are here ?

@ribsgrowback8459

3 жыл бұрын

Ayyyyyy

@gameoverplz9121

3 жыл бұрын

Me

@makeitbetter8439

3 жыл бұрын

Yeeeeees.

@momomtjiddu3920

3 жыл бұрын

@Khalil Cheddadi hahaha yeess

@ayoubachaq380

3 жыл бұрын

@@momomtjiddu3920 AYEEH AKHOYAAAAAA

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

@cr1216

3 жыл бұрын

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.

@user-rf4yj5mq3g

3 жыл бұрын

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

@mabdullahkhan4795

2 жыл бұрын

well smallest one is actually 28 💀

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

3 жыл бұрын

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

2 жыл бұрын

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.

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

coherent, slick, and therefore most enjoyable, thanks

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

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

2 жыл бұрын

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

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

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

3 жыл бұрын

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

Please, continue with the Rogers-Ramanujan Identities series!

[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

3 жыл бұрын

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

3 жыл бұрын

@@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

3 жыл бұрын

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

3 жыл бұрын

@@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.

There is one divisor for 31 in the range of 1

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

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.

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

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

@maosatela

3 жыл бұрын

yes you are right

@pandas896

3 жыл бұрын

😀

@cezarygalinski9420

3 жыл бұрын

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

@nabilmaster12

3 жыл бұрын

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 .

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

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

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

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

3 жыл бұрын

216/7

@srijanbhowmick9570

3 жыл бұрын

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| 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

3 жыл бұрын

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

@shivanggoyal7280

3 жыл бұрын

Quite easy compared to what you usually give

@goodplacetostop2973

3 жыл бұрын

@@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

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

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.

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

Thanks Bro.

my beloved country ❤❤❤ my greetings and love

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

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

@gameoverplz9121

3 жыл бұрын

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

Heey , m a follower from morroco

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

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

what happened to 6? it divides 60 :(

sir, plz give more interesting problem about number theory

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 ?

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

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.

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

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

3 жыл бұрын

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).

I am confused as to why we need to check the divisors of 60? If 60 is the lcm of the smallest cases for the factors of 2015, wouldn't having anything lower imply that one of the factors has a case apart from a multiple of their smallest n?

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]

I am suggesting this twicw now, check out USAMO 2014 problem 6.

I remember this one !!

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

3 жыл бұрын

"ai" are digits?

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?

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

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

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.

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.

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

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

3 жыл бұрын

No, he wasn't yet done. He's merely showing that if there is a smallest m 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

3 жыл бұрын

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

3 жыл бұрын

@@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..)?

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

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.

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

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

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

@MTd2

3 жыл бұрын

I guess it must suit clock engineers!

@JM-us3fr

3 жыл бұрын

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

3 жыл бұрын

@@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.

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

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.

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

take n=26 it will give smallest multiple of 2015

6 is a divisor of 60 @15:11

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

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.

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

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

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

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

this problem with primitive roots and discrete logarithms was so simple

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.

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.

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. ]

Good Place To Start at 2:06

Love morocco

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.

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

3 жыл бұрын

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

@udic01

3 жыл бұрын

@@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.

And 6 is also a divisor of 60

@frdjo2065

3 жыл бұрын

But very great explanation. Thanks for making people smarter !

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

@dimadima5298

3 жыл бұрын

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

3 жыл бұрын

Wach had chi watani diyal l'arithmétique

@zaidjanati03

3 жыл бұрын

@@cauchy2012 laa hada ymkn d olympiades

@nournote

3 жыл бұрын

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

@nournote

3 жыл бұрын

@@dimadima5298 Passe ton email.

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

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

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 :)

How old are you?

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

3 жыл бұрын

you're absolutely right

@stevenvanhulle7242

3 жыл бұрын

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

@md2perpe

3 жыл бұрын

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

And that's numberwang!

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

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 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 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.

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

3 жыл бұрын

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

@dominickmancine6033

3 жыл бұрын

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

3 жыл бұрын

@@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.

@edwardfanboy

3 жыл бұрын

@@nournote If your calculator uses binary floating-point arithmetic internally, it can calculate 2^60 just fine. But not 3^60.

@nournote

3 жыл бұрын

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

👍👍 from morocco

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

3 жыл бұрын

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

@swordwaker7749

3 жыл бұрын

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

@yurenchu

3 жыл бұрын

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

@swordwaker7749

3 жыл бұрын

@@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

3 жыл бұрын

@@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.

2:03 cool

You forgot 6, when you listed all the divisors of 60.

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.

Good

👍

wait a sec.. i want that technical trick !!!

Poor 6. Doomed to be forgotten forever.