Quant puzzles, solved step by step

Puzzles
100
Traced to a firm
71
Topics
12
Hard
30
Topic
All topicsLogic and algorithmic reasoning10Conditional probability and Bayes7Counting and combinatorics8Continuous and geometric probability9Correlation, regression and linear algebra9Market making, betting and sizing9Expected value and optimal stopping9Statistics and estimation9Pricing, options and index maths7Games and strategic reasoning8Markov chains and random walks7Mental maths and number sense8
Level
AnyWarm upCoreHard
Source
AnyReported at a firmStandard
Showing 1–1 of 1 · filtered from 100Clear filters
  1. 085What are the last two digits of 4 raised to the power 3000?Mental maths and number senseHardBelvedere TradingNew york · 2021

    Try it first

    Which ending is right?

    Show the worked solution

    76. Split 100 into 4 x 25. Any power of 4 is 0 mod 4. Mod 25, Euler's theorem applies because 4 and 25 share no factor, and 3000 is a multiple of phi(25) = 20, so 4^3000 is 1 mod 25. The numbers below 100 that are 1 mod 25 are 1, 26, 51 and 76, and only 76 is divisible by 4.

    Why does the obvious Euler shortcut fail?

    Euler's theorem says a to the power phi(n) is 1 mod n, and phi(100) = 40, so it is tempting to say 4^3000 = (4^40)^75 ends in 01. The theorem needs the base and the modulus to share no factor, and 4 and 100 share a factor of 4, so it does not apply. A quick sense check kills 01 anyway: every power of 4 is divisible by 4, and a number is divisible by 4 exactly when its last two digits are, which 01 is not.

    How do you split the problem so the theorem does apply?

    Think of a clock with 100 hours as two smaller clocks running together, one with 4 hours and one with 25. Knowing where both small clocks point fixes the big one exactly. Mod 4 the answer is 0, since 4^3000 is a multiple of 4; mod 25 the answer is 1, since 4 and 25 share no factor and 3000 is a multiple of phi(25) = 20. Now list the numbers below 100 that are 1 mod 25: 1, 26, 51, 76. Only 76 is a multiple of 4. This step is the Chinese remainder theorem, and naming it earns credit.

    Powers of 4 cycle every 10 steps, and 3000 lands on 7604n=116n=264n=356n=424n=596n=684n=736n=844n=976n=104^n mod 100repeats every 103000 = 10 x 300, and 76 x 76 = 5,776so 4^3000 = (4^10)^300 ends in 76Check with 100 = 4 x 25:mod 44^3000 is 0mod 25 (phi = 20)4^3000 is 11265176numbers below 100 that are 1 mod 25only 76 is also divisible by 4
    The last two digits of 4^n cycle through ten values and the tenth power ends in 76, so every multiple of 10 as an exponent, including 3000, ends in 76; splitting 100 into 4 and 25 confirms it, because 76 is the only number below 100 that is 0 mod 4 and 1 mod 25.
    The relationship
    43000≡0(mod4),43000=(420)150≡1(mod25)  ⇒  43000≡76(mod100)4^{3000} \equiv 0 \pmod 4, \quad 4^{3000} = (4^{20})^{150} \equiv 1 \pmod{25} \;\Rightarrow\; 4^{3000} \equiv 76 \pmod{100}
    mod 4, mod 25the remainders on division by 4 and by 25
    phi(25) = 20how many numbers below 25 share no factor with 25
    What it says in wordsFind the remainder on each small clock, then find the one number below 100 that matches both.

    What is the fastest check if you have a pencil?

    Just list the endings. Multiply each ending by 4 and keep the last two digits: 04, 16, 64, 56, 24, 96, 84, 36, 44, 76, and then 76 x 4 = 304, which ends in 04, so the cycle has length 10. Because 76 x 76 = 5,776 also ends in 76, every power of 76 ends in 76, and 4^3000 = (4^10)^300 must end in 76. On a multiple-choice test, this listing takes about thirty seconds and needs no theorem at all.

    Where candidates lose it

    The trap is applying Euler's theorem with phi(100) = 40 and answering 01. The theorem requires the base and modulus to share no factor, and 4 and 100 do share one.

    The second loss is listing powers without noticing the cycle and running out of time. Say early that the endings must repeat, find the period of 10, and read the answer from 3000 being a multiple of 10.

    What the interviewer asks next

    • What are the last two digits of 7^2026?
    • What are the last three digits of 4^3000?
    • What is the remainder when 2^100 is divided by 7?

    Asked at Belvedere Trading, Equities, New york, 2021 (Wall Street Oasis): It was a 14 question multiple choice test. Some basic number theory (4^3000 modulo 100)