Powers in Modular Arithmetic
You'll learn how to compute massive powers like 7^1000 mod 13 without actually calculating the trillion-digit number first.
The Challenge
Computing something like 3^500 mod 11 directly is impractical—3^500 is an astronomically large number. But we don't need its exact value, just its remainder when divided by 11. The trick is to never let intermediate results grow large by reducing modulo n at every step.
Core Strategy: Repeated Squaring
The key insight combines two ideas:
- Reduce early and often: Since (a · b) mod n = [(a mod n) · (b mod n)] mod n, we can take the modulus after each multiplication
- Repeated squaring: Express the exponent in binary to minimize multiplications
How It Works
To compute a^k mod n:
Step 1: Write k in binary (e.g., 13 = 1101₂ = 8 + 4 + 1)
Step 2: Build powers by repeated squaring: a¹, a², a⁴, a⁸, ... (each is the square of the previous, reduced mod n)
Step 3: Multiply only the powers corresponding to 1-bits in k's binary representation
Example: 7^13 mod 11
- 13 = 8 + 4 + 1 (binary: 1101)
- 7¹ mod 11 = 7
- 7² mod 11 = 49 mod 11 = 5
- 7⁴ mod 11 = 5² mod 11 = 25 mod 11 = 3
- 7⁸ mod 11 = 3² mod 11 = 9
Now multiply the needed powers: 7^13 = 7⁸ · 7⁴ · 7¹
(9 · 3 · 7) mod 11 = (27 · 7) mod 11 = (5 · 7) mod 11 = 35 mod 11 = 2
This requires only ~log₂(k) squarings and at most that many multiplications—incredibly efficient even for exponents with hundreds of digits.
Key Takeaway: Use repeated squaring with modular reduction at each step to compute a^k mod n efficiently, transforming an impossible calculation into a manageable one with logarithmic complexity.