Course contentsShow
← Mathematics
Lesson 2734 of 3,12154. Number TheoryFree lesson

Powers in Modular Arithmetic

Compute large powers efficiently using repeated squaring and modular reduction techniques.

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:

  1. 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
  2. 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.