A number theory problem from Morocco! 

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

15:27 you forgot 6

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

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.

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 want to know how many Moroccans are here ?

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!

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

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

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

coherent, slick, and therefore most enjoyable, thanks

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.

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)

Please, continue with the Rogers-Ramanujan Identities series!

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

There is one divisor for 31 in the range of 1

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.

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

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.

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

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

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.

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

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

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

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

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

Thanks Bro.

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

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

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

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

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 m big fan of you sir. Very smart solution espcially how to show that 60 is the smallsest sollution

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

my beloved country ❤❤❤ my greetings and love

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

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

sir, plz give more interesting problem about number theory

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.

I remember this one !!

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.

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 ?

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

Heey , m a follower from morroco

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.

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.

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 please tell how can we develop this type of mathematical thinking and reasoning

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

6 is a divisor of 60 @15:11

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

what happened to 6? it divides 60 :(

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

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

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

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.

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?

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.

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

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

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.

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

take n=26 it will give smallest multiple of 2015

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

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

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?

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

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

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

Good Place To Start at 2:06

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

this problem with primitive roots and discrete logarithms was so simple

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

Love morocco

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.

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

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.

And 6 is also a divisor of 60

2:03 cool

How old are you?

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.

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

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

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

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)

Good

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

👍👍 from morocco

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.

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.

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?

👍

And that's numberwang!

n=60

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

n = 0 , easily solved /s

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

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