A number theory problem from Morocco!
ฝัง
- เผยแพร่เมื่อ 2 พ.ย. 2020
- We solve a viewer suggested number theory problem from a math contest in Morocco.
Please Subscribe: th-cam.com/users/michaelpennma...
Merch: teespring.com/stores/michael-...
Personal Website: www.michael-penn.net
Randolph College Math: www.randolphcollege.edu/mathem...
Randolph College Math and Science on Facebook: / randolph.science
Research Gate profile: www.researchgate.net/profile/...
Google Scholar profile: scholar.google.com/citations?...
If you are going to use an ad-blocker, considering using brave and tipping me BAT!
brave.com/sdp793
Buy textbooks here and help me out: amzn.to/31Bj9ye
Buy an amazon gift card and help me out: amzn.to/2PComAf
Books I like:
Sacred Mathematics: Japanese Temple Geometry: amzn.to/2ZIadH9
Electricity and Magnetism for Mathematicians: amzn.to/2H8ePzL
Abstract Algebra:
Judson(online): abstract.ups.edu/
Judson(print): amzn.to/2Xg92wD
Dummit and Foote: amzn.to/2zYOrok
Gallian: amzn.to/2zg4YEo
Artin: amzn.to/2LQ8l7C
Differential Forms:
Bachman: amzn.to/2z9wljH
Number Theory:
Crisman(online): math.gordon.edu/ntic/
Strayer: amzn.to/3bXwLah
Andrews: amzn.to/2zWlOZ0
Analysis:
Abbot: amzn.to/3cwYtuF
How to think about Analysis: amzn.to/2AIhwVm
Calculus:
OpenStax(online): openstax.org/subjects/math
OpenStax Vol 1: amzn.to/2zlreN8
OpenStax Vol 2: amzn.to/2TtwoxH
OpenStax Vol 3: amzn.to/3bPJ3Bn
My Filming Equipment:
Camera: amzn.to/3kx2JzE
Lense: amzn.to/2PFxPXA
Audio Recorder: amzn.to/2XLzkaZ
Microphones: amzn.to/3fJED0T
Lights: amzn.to/2XHxRT0
White Chalk: amzn.to/3ipu3Oh
Color Chalk: amzn.to/2XL6eIJ
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
Mee too🤣🤣🤣🤣
Kaynin lmgharba tbarkllah had khona nadi
salam a drari
Ahh wllah
Mgharba everywhere
I gave a thumbs up for your kids stomping around upstairs!!!😁😁😁
Thanks Michael for the heart!
@@aashsyed1277 I can relate
15:27 you forgot 6
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).
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.
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 ?
Ayyyyyy
Me
Yeeeeees.
@Khalil Cheddadi hahaha yeess
@@momomtjiddu3920
AYEEH AKHOYAAAAAA
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.
Thats how I would have approached it and I think this is way more straight forward than his solution
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.
216/7
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
216/7 ,its a pretty easy one,just used basics of infinite gp and got a good place to stop..😁
Quite easy compared to what you usually give
@@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
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
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.
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.
There is one divisor for 31 in the range of 1
coherent, slick, and therefore most enjoyable, thanks
Please, continue with the Rogers-Ramanujan Identities series!
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.
Nice problem from Morocco, my country! . Go on , you're Amazing !👍👌
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)
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
[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.
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.
@@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.
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 .
@@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.
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.
small typo at 15:15: 6 is also a divisor
It's a great work man I'm from morocco too
17:57 aren't 2^4 and 3^4 congruent to 3 (mod 13)? You said they are congruent to 1 (mod 13)
yes you are right
😀
Yes, but the point is that they are congruent to each other and that’s everything needed for the solution.
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 .
Yeaaay! You did one of the most famous problem in my country! Thank you ✌🏻
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 don’t understand why we should show that 60 is the smallest isn’t it obvious.
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.
@@cr1216 that's right. But he use the fact. So it's a little bit unnatural.
well smallest one is actually 28 💀
It's good that you reminded me the fermats theorem.
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 ?
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
he is a very good person i also likes him because he never asks about to subscribe
it was a great problem..and coincidentally,my own solution completely matched with your's!!
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
"ai" are digits?
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
@MichaelPenn , Try Brocard's Problem (aka the Brocard-Ramanujan problem)
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.
Sir please tell how can we develop this type of mathematical thinking and reasoning
We are happy you take time from your busy schedule to teach us. 86K
I m big fan of you sir. Very smart solution espcially how to show that 60 is the smallsest sollution
Morocco! شكرا على الڤيديو
how would u check there are no other integers less than 30 satisfying 2^n = 3^n(mod 31). ?
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.
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.
Thanks Bro.
I am suggesting this twicw now, check out USAMO 2014 problem 6.
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.
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.
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
@@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..)?
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
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?
sir, plz give more interesting problem about number theory
Here all the primes factors were unique, Could we have done the same if there was a prime factor which repeated
my beloved country ❤❤❤ my greetings and love
I gave a like not only because the video was very educational, but also because of 1:56
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.
n = 2/log(1.5) x log {(165+13m)/165-13m)}, where m = multiple of 2015
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
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?
6 is a divisor of 60 @15:11
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
By FLT, 5, 13, 31 => 4, 12, 30|n. Lowest common denominator = 60. Done.
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.
كاين شي مغاربة هنا؟
انا 👋👋 كم كنحماق على هاد خونا واعر بزاف
@ 19:00 2^30 should be congruent to -1 mod 13 and 3^30 should be congruent to 1 mod 13.
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.
At this point, isn't it just easier to list all possible 2^n and 3^n (mod 2015) for n=1..59?
I remember this one !!
what happened to 6? it divides 60 :(
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.
doesn’t 30 not working automatically knock out 1,2,3,5,6,10,15 as well?
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.
Some group theory and introduction of "order of element" and you only have to do first 12 mins of video or so :)
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.
]
I think this problem could solve with theorem Lagrange in theory of groups
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.
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).
As an engineer with no contact with number theory, I had no idea of the importance of modulo analysis everywhere!
I guess it must suit clock engineers!
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.
@@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.
take n=26 it will give smallest multiple of 2015
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.
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.
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)?
We didn't fully prove that there was no number smaller than 30 in the mod 31 case
@@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.
Apparently doubles do not work for programming this in C#. Not sure why but I guess you have to use decimals
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
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)
Writing code is easy; but does it help in gaining more mathematical insights and skills?
@@yurenchu I normally consider python a valid tool in internet problems unless stated otherwise.
@@swordwaker7749 That's not what I asked though.
@@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.
@@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.
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 :)
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.
Love morocco
How old are you?
And 6 is also a divisor of 60
But very great explanation. Thanks for making people smarter !
this problem with primitive roots and discrete logarithms was so simple
Good Place To Start at 2:06
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?
you're absolutely right
30 was eliminated because it's not a multiple of 4.
@@stevenvanhulle7242 That was not an answer to my question.
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?
That simply means that your calculator can't calculate 2^60, which is predictable.
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.
@@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 If your calculator uses binary floating-point arithmetic internally, it can calculate 2^60 just fine. But not 3^60.
@@edwardfanboy Either way, calculators in general are not designed for number theory computations. Rather for scientific calculations where approximations are the goal.
👍👍 from morocco
2:03 cool
Good
👍
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
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 !!!!!!
Oh! Thank you so much! You did read my email :)
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
Wach had chi watani diyal l'arithmétique
@@cauchy2012 laa hada ymkn d olympiades
@@cauchy2012 Non. Olympiade sc. maths. 2015.
www.men.gov.ma/Ar/Documents/C-excellence_ancEpr/S6NMaO2015.pdf
@@dimadima5298 Passe ton email.
3^{15}-2^{15}=0 (mod 31)
No,
3^15=-1 (mod 31)
2^15= 1 (mod 31)
literally 30 sec and 1 line:
print([n for n in range(1,10000) if (3**n - 2**n) % 2015==0][0])
Yeah as long as your modular arithmetic is good, this problem wasn't so bad. The 31 case was the most time-consuming, but it's pretty easy to check.
And that's numberwang!