A number theory problem from Morocco!

Поделиться
HTML-код
  • Опубликовано: 23 дек 2024
  • We solve a viewer suggested number theory problem from a math contest in Morocco.
    Please Subscribe: www.youtube.co...
    Merch: teespring.com/...
    Personal Website: www.michael-pen...
    Randolph College Math: www.randolphcol...
    Randolph College Math and Science on Facebook: / randolph.science
    Research Gate profile: www.researchga...
    Google Scholar profile: scholar.google...
    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...
    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/s...
    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

Комментарии • 252

  • @jgray2718
    @jgray2718 4 года назад +49

    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
    @aminenajjari9292 4 года назад +137

    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

  • @matthewdoughty3268
    @matthewdoughty3268 3 года назад +14

    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
    @Tehom1 4 года назад +15

    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.

  • @udic01
    @udic01 4 года назад +47

    15:27 you forgot 6

    • @Evilpengwinz78
      @Evilpengwinz78 4 года назад +2

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

  • @RexxSchneider
    @RexxSchneider 3 года назад +3

    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
      @reeeeeplease1178 2 года назад

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

  • @srijanbhowmick9570
    @srijanbhowmick9570 4 года назад +71

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

  • @Blabla0124
    @Blabla0124 4 года назад +8

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

  • @tensor131
    @tensor131 2 года назад +1

    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!

  • @brexolino1024
    @brexolino1024 4 года назад +8

    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
      @stephenbeck7222 4 года назад +1

      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
      @GrimAxel 3 года назад +1

      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.

  • @davidemasi__
    @davidemasi__ 4 года назад +21

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

    • @maosatela
      @maosatela 4 года назад +2

      yes you are right

    • @pandas896
      @pandas896 4 года назад +4

      😀

    • @cezarygalinski9420
      @cezarygalinski9420 4 года назад +5

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

    • @nabilmaster12
      @nabilmaster12 4 года назад +1

      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 .

  • @kevinmartin7760
    @kevinmartin7760 4 года назад +18

    [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
      @MD-pg1fh 4 года назад

      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
      @kevinmartin7760 4 года назад +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
      @nabilmaster12 4 года назад

      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
      @kevinmartin7760 4 года назад +1

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

  • @zecareca42
    @zecareca42 4 года назад +5

    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
      @RMaster7 4 года назад +2

      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

  • @goodplacetostop2973
    @goodplacetostop2973 4 года назад +26

    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
      @noahtaul 4 года назад +1

      216/7

    • @srijanbhowmick9570
      @srijanbhowmick9570 4 года назад +8

      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
      @shreyamjha3058 4 года назад +1

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

    • @shivanggoyal7280
      @shivanggoyal7280 4 года назад +3

      Quite easy compared to what you usually give

    • @goodplacetostop2973
      @goodplacetostop2973 4 года назад +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

  • @fmakofmako
    @fmakofmako 4 года назад

    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
      @yurenchu 4 года назад

      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
      @nabilmaster12 4 года назад +1

      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
      @duffahtolla 4 года назад

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

  • @chrisbattey
    @chrisbattey 3 года назад +3

    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.

  • @krisbrandenberger544
    @krisbrandenberger544 Год назад

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

  • @alborzalborzi3845
    @alborzalborzi3845 4 года назад +1

    There is one divisor for 31 in the range of 1

  • @toddtrimble2555
    @toddtrimble2555 2 года назад

    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.

  • @momomtjiddu3920
    @momomtjiddu3920 4 года назад +49

    I want to know how many Moroccans are here ?

  • @abderrahimelouafi1373
    @abderrahimelouafi1373 4 года назад +1

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

  • @klausg1843
    @klausg1843 4 года назад +3

    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.

  • @MTd2
    @MTd2 4 года назад +27

    Please, continue with the Rogers-Ramanujan Identities series!

  • @tahirimathscienceonlinetea4273
    @tahirimathscienceonlinetea4273 4 года назад +2

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

  • @OmarOmar-cj9rk
    @OmarOmar-cj9rk 4 года назад +5

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

  • @TedHopp
    @TedHopp 4 года назад +2

    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.

  • @alikaperdue
    @alikaperdue 7 месяцев назад

    6 is a divisor of 60 @15:11

  • @jamieee472
    @jamieee472 2 года назад

    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

  • @robertgerbicz
    @robertgerbicz 4 года назад +4

    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.

  • @mamatamohanty6417
    @mamatamohanty6417 2 года назад

    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

  • @crazy4hitman755
    @crazy4hitman755 4 года назад +20

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

    • @cr1216
      @cr1216 4 года назад +7

      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
      @이동의-q5b 3 года назад +1

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

    • @mabdullahkhan4795
      @mabdullahkhan4795 3 года назад

      well smallest one is actually 28 💀

  • @vishalmishra3046
    @vishalmishra3046 4 года назад +2

    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]

  • @Tiqerboy
    @Tiqerboy 4 года назад +3

    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
      @stephenbeck7222 4 года назад

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

  • @ciprianburduja8249
    @ciprianburduja8249 4 года назад +1

    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

  • @samrubenabraham6979
    @samrubenabraham6979 4 года назад

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

  • @nailabenali7488
    @nailabenali7488 4 года назад +3

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

  • @wesleydeng71
    @wesleydeng71 4 года назад

    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?

  • @lmxqlmxq
    @lmxqlmxq 4 года назад

    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

  • @vcvartak7111
    @vcvartak7111 3 года назад +1

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

  • @youssefeljouhari7418
    @youssefeljouhari7418 2 года назад

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

  • @abusoumaya8469
    @abusoumaya8469 4 года назад +3

    my beloved country ❤❤❤ my greetings and love

  • @shalvagang951
    @shalvagang951 3 года назад

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

  • @PavelB123
    @PavelB123 3 года назад +1

    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.

  • @oder4876
    @oder4876 4 года назад +1

    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

  • @DavidSavinainen
    @DavidSavinainen 4 года назад

    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

  • @frozenmoon998
    @frozenmoon998 4 года назад

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

  • @prathikkannan3324
    @prathikkannan3324 3 года назад

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

  • @robertingliskennedy
    @robertingliskennedy 4 года назад

    coherent, slick, and therefore most enjoyable, thanks

  • @OH-pc5jx
    @OH-pc5jx 3 года назад

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

  • @MrRyanroberson1
    @MrRyanroberson1 4 года назад

    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.

  • @reeeeeplease1178
    @reeeeeplease1178 2 года назад

    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.

  • @Walczyk
    @Walczyk 3 года назад +1

    what happened to 6? it divides 60 :(

  • @samyachakraborty263
    @samyachakraborty263 4 года назад +1

    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 ?

  • @copyrightfreemusicforall5563
    @copyrightfreemusicforall5563 4 года назад +1

    sir, plz give more interesting problem about number theory

  • @Учимсявместе-т9о
    @Учимсявместе-т9о 4 года назад +1

    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.

  • @cecilhenry9908
    @cecilhenry9908 4 года назад +2

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

    • @MTd2
      @MTd2 4 года назад

      I guess it must suit clock engineers!

    • @JM-us3fr
      @JM-us3fr 4 года назад +1

      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
      @cecilhenry9908 4 года назад

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

  • @quantabot1165
    @quantabot1165 4 года назад

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

  • @jerrymouse3420
    @jerrymouse3420 4 года назад +1

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

  • @marshalls36
    @marshalls36 3 года назад

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

  • @swordwaker7749
    @swordwaker7749 4 года назад +1

    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
      @yurenchu 4 года назад +1

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

    • @swordwaker7749
      @swordwaker7749 4 года назад

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

    • @yurenchu
      @yurenchu 4 года назад

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

    • @swordwaker7749
      @swordwaker7749 4 года назад

      @@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
      @swordwaker7749 4 года назад +1

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

  • @nullplan01
    @nullplan01 4 года назад

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

  • @ChristopherBitti
    @ChristopherBitti 3 месяца назад

    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.

  • @justacockypersonontheinter6889
    @justacockypersonontheinter6889 4 года назад

    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

  • @udic01
    @udic01 4 года назад

    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
      @thiantromp6607 4 года назад

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

    • @udic01
      @udic01 4 года назад

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

  • @mayankrs2016
    @mayankrs2016 4 года назад

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

  • @bridgeon7502
    @bridgeon7502 4 месяца назад

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

  • @ellenmarch3095
    @ellenmarch3095 2 года назад

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

  • @ufailowell
    @ufailowell 3 года назад

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

    • @jamieee472
      @jamieee472 2 года назад

      probably due to floating point precision error

  • @wolframhuttermann7519
    @wolframhuttermann7519 4 года назад

    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
    @mathboy8188 3 года назад

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

  • @Yougottacryforthis
    @Yougottacryforthis 2 года назад

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

  • @cinedeautor6642
    @cinedeautor6642 3 года назад

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

  • @goodplacetostart9099
    @goodplacetostart9099 3 года назад

    Good Place To Start at 2:06

  • @wydadiyoun
    @wydadiyoun 4 года назад +11

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

    • @gameoverplz9121
      @gameoverplz9121 4 года назад +2

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

  • @md2perpe
    @md2perpe 4 года назад

    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
      @nabilmaster12 4 года назад

      you're absolutely right

    • @stevenvanhulle7242
      @stevenvanhulle7242 4 года назад

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

    • @md2perpe
      @md2perpe 4 года назад

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

  • @BenfanichAbderrahmane
    @BenfanichAbderrahmane 4 года назад +1

    Heey , m a follower from morroco

  • @alexander_adnan
    @alexander_adnan 3 года назад

    Thanks Bro.

  • @treyebillups8602
    @treyebillups8602 4 года назад

    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
      @nournote 4 года назад

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

    • @dominickmancine6033
      @dominickmancine6033 4 года назад

      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
      @yurenchu 4 года назад

      @@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
      @nournote 4 года назад

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

  • @nournote
    @nournote 4 года назад +5

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

    • @BMK5298
      @BMK5298 4 года назад +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
      @cauchy2012 4 года назад

      Wach had chi watani diyal l'arithmétique

    • @zaidjanati03
      @zaidjanati03 4 года назад

      @@cauchy2012 laa hada ymkn d olympiades

    • @nournote
      @nournote 4 года назад +1

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

    • @nournote
      @nournote 4 года назад +1

      @@BMK5298 Passe ton email.

  • @uditagarwal10
    @uditagarwal10 4 года назад

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

  • @TheQEDRoom
    @TheQEDRoom 4 года назад

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

  • @RexxSchneider
    @RexxSchneider 3 года назад

    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.

  • @noname-jv6hx
    @noname-jv6hx 2 года назад +1

    take n=26 it will give smallest multiple of 2015

  • @samyakmahapatra9154
    @samyakmahapatra9154 4 года назад +2

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

  • @heldercomp
    @heldercomp 3 года назад +1

    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
    @maosatela 4 года назад

    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
      @nabilmaster12 4 года назад

      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
    @frdjo2065 4 года назад +1

    And 6 is also a divisor of 60

    • @frdjo2065
      @frdjo2065 4 года назад

      But very great explanation. Thanks for making people smarter !

  • @arekkrolak6320
    @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 :)

  • @seroujghazarian6343
    @seroujghazarian6343 3 года назад

    15:20 is 6 a joke to you?

  • @arturjorge5607
    @arturjorge5607 4 года назад

    this problem with primitive roots and discrete logarithms was so simple

  • @thomasaskew1985
    @thomasaskew1985 4 года назад

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

    • @stevenvanhulle7242
      @stevenvanhulle7242 4 года назад

      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
      @thomasaskew1985 4 года назад

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

  • @مطبخوهيبةالعروسي
    @مطبخوهيبةالعروسي 3 года назад +1

    Love morocco

  • @yurenchu
    @yurenchu 4 года назад

    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
      @cezarygalinski9420 4 года назад +1

      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
      @nabilmaster12 4 года назад

      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
      @cezarygalinski9420 4 года назад

      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
      @yurenchu 4 года назад

      @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
      @yurenchu 4 года назад

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

  • @yoyoyo007123
    @yoyoyo007123 3 года назад

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

  • @MORISENSEIISGOD
    @MORISENSEIISGOD 4 года назад +2

    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.

  • @mehmeterciyas6844
    @mehmeterciyas6844 4 года назад

    How old are you?

  • @Elouard
    @Elouard 4 года назад +1

    👍👍 from morocco

  • @AlexandrBorschchev
    @AlexandrBorschchev 4 года назад

    2:03 cool

  • @aubium2992
    @aubium2992 4 года назад

    I remember this one !!

  • @DeadlyBlaze
    @DeadlyBlaze Год назад

    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?