finding the last two digits

Поділитися
Вставка
  • Опубліковано 18 січ 2025

КОМЕНТАРІ • 58

  • @Bodyknock
    @Bodyknock 18 днів тому +16

    He didn't mention it in the video for some reason, but φ(n) has a pretty easy to use formula, it's just n ( 1- 1/p₁)(1- 1/p₂)...(1- 1/pₖ) for all the prime factors of n. So for instance, the prime factors of 100 are 2 and 5, so φ(n) = 100 (1/2) (4/5) = 40. Similarly φ(40) = 40 (1/2) (4/5) = 16 .

  • @mapwiz-sf5yt
    @mapwiz-sf5yt 18 днів тому +4

    There's another way to do it-- if you take powers of 97 (or -3) mod 100, you'll see it repeats after a cycle of 20. If you take powers of 98 (or -2) mod 20, it has a cycle of 4. 99 is congruent to 3 mod 4, and the mod 3 entry in the cycle of powers of 98 mod 20 is 12. The mod 12 entry in the cycle of powers of 97 mod 100 is 41.

  • @MichaelRothwell1
    @MichaelRothwell1 17 днів тому +3

    This is the solution I wrote before watching the video, and avoids the "handwaving" about gcd(1998, 40)≠1.
    This looks like a job for the Carmichael λ-function we saw in Michael Penn's video "this number is "super divisible"".
    1997ⁿ≡(-3)ⁿ (mod 100) will have a certain period mod 100, and we can take the residue of the exponent mod this period without changing the residue mod 100.
    Let's work out this period (but for 3, instead of -3)
    Powers of 3 reduced mod 100:
    1: 3
    2: 9
    3: 27
    4: 81
    5: 43
    6: 29
    7: 87
    8: 61
    9: 83
    10: 49≡-51 (mod 100)
    11: -53 (mod 100)
    Clearly the pattern repeats but with 50 less the original value, so at 20 we'll get to 1.
    We can save doing this work - and in fact we shall solve the problem as if we hadn't done this - as we know (since 1997 is comprime to 100) this period is a divisor of φ(100)=φ(2²5²)=2×(5×4)=40, and, potentially, better still, using the Carmichael λ-function, a divisor of λ(100)=λ(2²5²)=2×(5×4)=40.
    However, both are suboptimal in this case.
    So we can reduce 1998^1999 mod 40 (or 20) without changing the value of 1997^1998^1999 (mod 100)
    In particular, we get 1998≡-2 (mod 40), so
    1998^1999≡(-2)^1999 (mod 40)≡-2^1999 (mod 40)
    In this case, as 2 is not coprime to 40, we can't use φ or λ to reduce the exponent 1999 directly. However, as 40=2³5, we note that 2⁴≡1 (mod 5), as guaranteed by φ & FLT. So we get, for m, n≥3, if m≡n (mod 4) then 2ᵐ≡2ⁿ[≡0] (mod 8) and 2ᵐ≡2ⁿ (mod 5) so 2ᵐ≡2ⁿ (mod 40).
    So we can reduce 2ⁿ mod 40 by reducing n mod 4, as long as the reduced power ≥3
    So
    2^1999≡2³≡8 (mod 40)
    So
    1998^1999≡-2^1999≡-8≡32 (mod 40)
    So 1997^1998^1999≡1997^32 (mod 100)
    ≡(-3)^32 (mod 100)
    ≡3^32 (mod 100)
    [from the initial work with powers of 3 we see this is same as 3^12≡-59≡41 (mod 100)]
    ≡9^16 (mod 100)
    Powers of 9 reduced mod 100:
    1: 9
    2: 81
    3: 29
    4: 61
    5: 49=50-1
    6: 41=50-9
    Clearly the pattern repeats after 5 steps but with 50 less the original value, so at 10 we'll get to 1, and the pattern will repeat.
    [As expected based on what we saw earlier for powers of 3]
    So 9^16≡9^6 (mod 100)
    ≡41 (mod 100)
    So the last two digits of 1997^1998^1999 are 41

  • @alre9766
    @alre9766 18 днів тому +21

    I understood nothing

    • @theupson
      @theupson 18 днів тому

      pick a starting base (b), pick a modular power (m, greater than b if you please)
      if you calculate powers of b mod m, it eventually starts to cycle:
      powers of 2 mod 10: 2;4;8;6;2;4;8;6;2 etc ad infinitum
      that loop repeats itself every 4 units, so if you needed to calculate 2^400000000001, its gotta be 2^1 = 2.
      now. different bases will have different loop lengths (powers of 9 mod 10 are 9;1;9;1 etc), BUT for all bases a sequence of length phi(m) is guaranteed to be a loop. phi(m) is euler's totient function- in this video phi(100) = 40 and phi(40) = 16 were both facts that made an appearance. why this works and more importantly the properties that let you compute phi are unpleasant to type in the comments section, but probably if you google it you can get a reasonable handle on phi(n) within ten minutes. hard to read, easy to understand; the mark of pure math everywhere and always.
      the way this stuff works is closely allied with RSA encryption, which is a standard unit in discrete math (first university proofs course). RSA is genuinely important so this all provides a lot of motivation to include this variety of problem in math competitions
      edit! if you're lost at a more basic level, you want to look up "what is modular arithmetic"; this problem is summarized as "calculate the value of [preposterously huge number] mod 100"

  • @jursamaj
    @jursamaj 17 днів тому +1

    My reasoning was simpler (to me):
    97^20≡1 mod 100, so the exponent of 1997 can be reduced mod 20. Since 100 is a multiple of 20, and reducing mod 100 is easier, I went with that. No power of 98 is going to be congruent 1 mod 100 (except the 0th power), but after the 1st 2 powers, every 20 powers gets you back to the same result. Since 1999>2, this works. 1999≡19 mod 20. 98^19≡12 mod 100. 97^12≡41 mod 100.

    • @jursamaj
      @jursamaj 13 днів тому +1

      @@akifbaysal9141 No, the standard for power towers is to evaluate the exponents from the top down. It does **not** simplify to multiplying the exponents.

    • @akifbaysal9141
      @akifbaysal9141 13 днів тому

      @@jursamaj thx for clarification, I noticed I misunderstood the reply I received. I was looking to delete my previous note postef here but was not able locate it before you posted, I deleted now..

  • @zygoloid
    @zygoloid 18 днів тому +2

    38 and 40 are not coprime, so it's not correct to apply Euler's theorem when reducing 38¹⁹⁹⁹ mod 40 (though it does seem to work in this case). If this reduction were correct in general, then we could equally argue that 38²⁰⁰⁰ = 38⁰ = 1 mod 40, because 2000 = 0 mod 16. But that's clearly wrong because 38²⁰⁰⁰ is even, as is its residue mod 40.
    Powers of -2 mod 40:
    1, -2, 4, -8, 16, 8, -16, -8, 16, 8, -16, ...
    So (-2)¹⁹⁹⁹ = -8 = 32 because 1999 = 3(4) and 1999 > 2.
    I *think* the reduction will always work for a^b mod n if the exponent is reduced to no less than phi(n)/gcd(a,n) (because that guarantees we stay within the eventual cyclic portion of a^b mod n) which is why it works here but not for 38²⁰⁰⁰, but I'm not sure that's the right condition.
    Is there a general result for when we can "use Euler's theorem" even though its precondition is not satisfied?

    • @TobyBW
      @TobyBW 18 днів тому +3

      The general result is that we can reduce down to the least power r such that a^r shares no prime factors with m that have a lesser exponent in the factorization of a^r than in the factorization of m. So, to get a statement true for all a, choose r at least as large as the largest exponent in the prima factorization of m. Which is 3 in this case.

    • @shirou9790
      @shirou9790 18 днів тому +1

      Yeah for 38^2000 you can then reduce to 38^16, which gives (-2)^16 = 2^16 = 65536 = 16, which is the correct result. (In fact, in the group of multiples of 8 mod 40, 16 is the neutral element, since it reduces to 1 mod 5--and indeed 16*8=128 reduces to 8 mod 40, etc.)

    • @MichaelRothwell1
      @MichaelRothwell1 17 днів тому +1

      I suggest see my comment for a solution that doesn't make this assumption. This illustrates the general rule stated by @TobyBW

  • @miraj2264
    @miraj2264 18 днів тому +2

    I had a question at 3:40. I thought that since 1999 mod(16) = 15, you could also use -1. But then you're left with 38^-1 mod(40). In other words, you need some number x s.t. 38x = 1 mod(40), but this is impossible since 38 is even so 38x is even. Is the general rule of thumb that you don't want to mess around with negative integers in the exponent and only the base?

    • @bro_vega_1412
      @bro_vega_1412 18 днів тому +2

      The theorem may fail when gcd(a,n) is not 1 (here gcd(38,40)=2). I think he just choose a specific expression that keep it working.

    • @MichaelRothwell1
      @MichaelRothwell1 17 днів тому

      I suggest see my comment for a solution that doesn't make this assumption.

  • @RSTATHER
    @RSTATHER 18 днів тому

    I have an interesting question:
    Prove whether or not there exists a constant ‘p’ s.t.
    the limit as n tends towards infinity of:
    (n!)^(1/n) - n/p converges

  • @psioniC_MS
    @psioniC_MS 18 днів тому +9

    Why can we reduce mod 16 in the exponent when gcd(38, 40) = 2 != 1?

    • @DrR0BERT
      @DrR0BERT 18 днів тому +1

      He addresses at 5:28 it with a lot of hand waving. I would like to have had a discussion on that.

    • @TobyBW
      @TobyBW 18 днів тому +5

      @@DrR0BERTyou can find some justification on the Wikipedia page for the Carmichael function (though without proof) that modular powers must loop starting at r = the largest exponent in the prime factorization of the modulus. In this case, m = 40, the highest power is 3, so you can reduce powers mod 16 down to 3 but not necessarily lower. This case reduces to 15 so it's ok.

    • @TobyBW
      @TobyBW 18 днів тому

      I won't write a full proof, but the reason for this is that once you take the r power, any prime factors that the base and the modulus shared are now have at least as large an exponent as in the modulus. Thus, we can reduce it all mod p_i^r_i. In this case, we could go from looking mod 40 to mod 5, since once the exponent of -2 reaches 3, every subsequent power will be divisible by 8, and we can reduce the whole modular equation down to modulo 5

    • @shirou9790
      @shirou9790 18 днів тому +3

      Yeah the way I did it is with CRT. Since we want to eventually reduce 1998^1999 mod 40, let's separate the prime factors of 40 = 2³ · 5 and look at 1998^1999 mod 8, which is clearly 0 since it contains a factor of 2^1999, and 1998^1999 mod 5, which reduces to 3^3 = 27 reduces again to 2 (1998 = 3 mod 5, phi(5) = 4 and the exponent 1999 = 3 mod 4)
      so we have 1998^1999 = 0 mod 8, and 2 mod 5, which must mean it reduces to 32 mod 40 (one can quickly look through the multiples of 8 to see which one reduces to 2 mod 5).

    • @DrR0BERT
      @DrR0BERT 17 днів тому

      @@TobyBW I understand that. My comment was for those who aren't number theorists. As an educator, I saw this was a missed opportunity.

  • @david-melekh-ysroel
    @david-melekh-ysroel 18 днів тому +3

    Happy new abundant odd year
    Note that Abundant odd numbers are very rare

    • @RecreationallyCynical
      @RecreationallyCynical 18 днів тому +2

      Also a square year, and probably the only square year in our lifetime (next one is 2116).

    • @david-melekh-ysroel
      @david-melekh-ysroel 18 днів тому

      @RecreationallyCynical I know, but I am more interested in abundant numbers

  • @Demo-critus
    @Demo-critus 18 днів тому +1

    I was hoping the answer would be 42.

  • @Alan-zf2tt
    @Alan-zf2tt 18 днів тому

    And! Before it ends: A Happy Old Year to everyone 🙂

  • @JR13751
    @JR13751 17 днів тому

    Carmichael function would have worked better here.

  • @randomjin9392
    @randomjin9392 18 днів тому

    Basics only: we have 2⁵ = 32 ≡ 2 mod 20, thus if k = 1998¹⁹⁹⁹ then k is even and k ≡ (-1)¹⁹⁹⁹∙2¹⁹⁹⁵∙2⁴ = -1∙2³⁹⁹∙2⁴ = -1∙2⁴⁰⁰∙2³ ≡ -1∙2¹⁶∙2³ = -1∙2¹⁵∙2⁴ ≡ -1∙2³∙2⁴ = -1∙2⁵∙2² ≡ -1∙2∙2² = -8 ≡ 12 mod 20. Next, 1997ᵏ ≡ (-3)ᵏ = 3ᵏ mod 100 (k is even). But then 3ᵏ = (3²⁰)ᵐ∙3ʳ where k = 20k + r, so r is a remainder which we've just found, meaning 3ᵏ = (3²⁰)ᵐ∙3¹² ≡ 1ᵐ∙3¹² mod 100 = 3¹² mod 100 = 41. And this is because 3²⁰ = ((3⁵)²)² = (343²)² ≡ (43²)² = 1849² ≡ 49² = 2401 ≡ 1 mod 100 and similarly, 3¹² = ((3³)²)² = (27²)² = 729² ≡ 29² = 841 ≡ 41 mod 100.

  • @MrRyanroberson1
    @MrRyanroberson1 18 днів тому

    So (10a+b)^big will always end in some combination of 10a b^(n-1) + b^n, since all higher terms become irrelevant. Therefore we're looking at 97^1998^1999. If we work mod 100, we can actually count 97 as -3; since 1998 is even, the power is even and the minus sign vanishes; we're looking at 3^1998^1999. The even powers of 3, mod 100, progress... 9, 81, 29, 67, 3, 27, 43, 87, ... that's a lot, i quit

  • @Zebinify
    @Zebinify 18 днів тому +2

    Humm, i need a bit help here. Why could we reduce 1998^1999 mod 40? To do this, didn't we need gcd(1998,40)=1?

    • @eu7059
      @eu7059 18 днів тому +1

      5:29

    • @Zebinify
      @Zebinify 18 днів тому +1

      @@eu7059 Thanks!

    • @MichaelRothwell1
      @MichaelRothwell1 17 днів тому

      I suggest see my comment for a solution that doesn't make this assumption.

  • @keithmasumoto9698
    @keithmasumoto9698 18 днів тому

    I love these. So if this determination can only be made when phi(a,n)=1 then are there towers of powers that are impossible to find the last digits of?

    • @minamagdy4126
      @minamagdy4126 18 днів тому

      Not impossible, you'll just need an even more general theorem. In fact, the tower in the video is such a harder tower (Michael didn't take this into account, though)

    • @MichaelRothwell1
      @MichaelRothwell1 17 днів тому

      I suggest see my comment for a solution that doesn't make this assumption.

  • @akifbaysal9141
    @akifbaysal9141 14 днів тому

    Should we consider the thumbnail expression is for last two decimal digits of umber A = (1997)^(1998^1999).. When different interpretation is made to power of power, the result may come out diferent.

    • @txikitofandango
      @txikitofandango 14 днів тому

      The standard interpretation of the power tower is from the top down, so x^y^z means x^(y^z)

    • @akifbaysal9141
      @akifbaysal9141 13 днів тому

      Thx.. Even there may be some accepted convention, I hit different ways of power tower interpretations.

  • @charleyhoward4594
    @charleyhoward4594 17 днів тому

    dont understand - but good presentation

  • @petermeuris9522
    @petermeuris9522 18 днів тому +5

    There is an error in phi(40), it contains 5.

    • @bernarddabomb2837
      @bernarddabomb2837 18 днів тому +3

      i think it's fine because he forgot the 9 so it acts as a replacement

    • @theupson
      @theupson 18 днів тому +1

      phi(40) = phi(8)*phi(5) = (8-4)*(5-1). attempting to list the relatively prime integers was an idiosyncratic approach

    • @damyankorena
      @damyankorena 18 днів тому +1

      phi(n) is multiplicative so phi(n) can be represented as the product of the prime powers in the canonical representation of n.

    • @RexxSchneider
      @RexxSchneider 18 днів тому

      @@theupson But it's quicker than explaining how to calculate φ(n). Optionally, he could have said that 2 and 5 are the only primes that divide 40, and every other number is even so we can remove 20 numbers from the 1-40 list, so we have 1/2 of 40 = 20 left. Then every fifth number in the 1-40 list is divisible by 5, so we have 4/5 of 20 = 16 left. So φ(40) = 16.
      Similarly, φ(100) = 100 x 1/2 x 4/5 = 40. I still think writing out the lists as he did makes it easier to understand for anyone who has little number theory.

  • @StaR-uw3dc
    @StaR-uw3dc 18 днів тому +2

    Happy New Year ! 2025=(20+25)(20+25)

    • @rainerzufall42
      @rainerzufall42 18 днів тому +4

      2025 = (0³ +) 1³ + 2³ + 3³ + 4³ + 5³ + 6³ + 7³ + 8³ + 9³ = ( (0 +) 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 )²

    • @xinpingdonohoe3978
      @xinpingdonohoe3978 18 днів тому +3

      ​@rainerzufall42 beat me to it. I guess that's the benefit of squaring a triangle number.

    • @rainerzufall42
      @rainerzufall42 18 днів тому +4

      @@xinpingdonohoe3978 You know, sum n³ = (sum n)² is always right, but I find it fascinating, that in this case, it's all the digits!

  • @Alan-zf2tt
    @Alan-zf2tt 18 днів тому +1

    Thank you for giving interesting applications of number theory

  • @GIFPES
    @GIFPES 18 днів тому

    I would use patterns of powers, not to use number theory mambojambo.

    • @DrR0BERT
      @DrR0BERT 18 днів тому

      They are the same thing.

  • @barisdemir7896
    @barisdemir7896 5 днів тому

    We follow Mr. Michael Penn's videos. I wondered what it would be like if he spoke in Turkish. let's see how he reacts. by the way, he has a lot of followers in Turkey, I wonder if we could somehow publish his translated videos online. would he be interested?
    ua-cam.com/video/1UB14Mm5TMM/v-deo.html