如何利用模运算计算大数末尾数字？求算9^(9^(9^9))最后两位

Hey folks! Let's start with the basics of using modular arithmetic to crack those massive number last-digit problems, then dive into that beast of an exponent: 9⁽⁹(9^9)).

The Fundamental Trick #

To find the last n digits of a number, you just need to compute that number modulo 10^n. For example:

• Last 1 digit → compute modulo 10
• Last 2 digits → compute modulo 100
  This works because 10^n divides all the higher place values, so they don't affect the last n digits at all.

Key Tool: Euler's Theorem #

When dealing with huge exponents, Euler's Theorem is your secret weapon. It states that if a and m are coprime (no common factors other than 1), then:
a^φ(m) ≡ 1 mod m
where φ(m) is Euler's totient function—it counts how many numbers ≤ m are coprime to m.

This lets us shrink massive exponents by taking them modulo φ(m) (we only need to adjust if the exponent is smaller than φ(m), which isn't the case here).

Solving 9⁽⁹(9^9)): Last Two Digits #

We need to compute 9^(9^(9^9)) mod 100. Let's break this down step by step to avoid getting overwhelmed.

Step 1: Simplify the exponent using φ(100) #

First, 9 and 100 are coprime (their greatest common divisor is 1). Let's calculate φ(100):
φ(100) = φ(4 * 25) = φ(4) * φ(25) = 2 * 20 = 40
By Euler's Theorem, 9^40 ≡ 1 mod 100. That means we can rewrite our problem as:
9^(k) mod 100 where k = 9^(9^9) mod 40 (since the exponent cycles every 40 here)

Step 2: Compute k = 9⁽⁹9) mod 40 #

Now we need to find 9^(9^9) mod 40. Let's spot a cycle in 9's powers modulo 40:

• 9^1 = 9 mod 40
• 9^2 = 81 ≡ 1 mod 40
  Wow, the cycle length is just 2! So:
• If the exponent is even: 9^even ≡ 1 mod 40
• If the exponent is odd: 9^odd ≡ 9 mod 40

Is 9^9 even or odd? 9 is odd, and any power of an odd number stays odd. So 9^9 is odd, which means:
9^(9^9) ≡ 9 mod 40 → so k=9

Step 3: Compute 9^9 mod 100 #

Now we just need to calculate 9^9 and take modulo 100. Let's compute step by step to keep numbers small:

• 9^2 = 81 mod 100
• 9^4 = (9^2)^2 = 81^2 = 6561 ≡ 61 mod 100
• 9^8 = (9^4)^2 = 61^2 = 3721 ≡ 21 mod 100
• 9^9 = 9^8 * 9 = 21 * 9 = 189 ≡ 89 mod 100

Final Result #

The last two digits of 9⁽⁹(9^9)) are 89.

内容的提问来源于stack exchange，提问作者tigerustin