Binary Exponentiation & Modular Arithmetic

February 06, 2026

From “Why is this confusing?” to “This is obvious now”

Some concepts in computer science don’t feel hard because they are complex —
they feel hard because we try to compute instead of understanding.

Binary exponentiation is one such concept.

This blog captures a real learning journey:
starting with confusion around large exponents and modular arithmetic,
and ending with a clear, reusable mental model you’ll never forget.

1. The Problem That Started It All

We were asked to compute:

2¹⁰¹ mod 7

At first glance, it feels intimidating:

101 is a large exponent
Direct multiplication is impossible
Modulo arithmetic feels tricky

But the key realization is this:

The problem is not “big numbers” — the problem is “wrong approach”.

2. Why Naive Exponentiation Fails

The naive way:

2 × 2 × 2 × … (101 times)

Problems:

Takes O(n) time
Numbers grow extremely large
Completely impractical in real systems

In cryptography, competitive programming, and system algorithms, this approach is unusable.

So the question becomes:

How do we reduce 101 multiplications to just a few?

3. The First Breakthrough: Binary Representation

Instead of working in decimal, we switch to binary.

Convert exponent to binary

101₁₀ = 1100101₂

This means:

101 = 64 + 32 + 4 + 1

So we rewrite:

2¹⁰¹ = 2⁶⁴ × 2³² × 2⁴ × 2¹

This single step changes everything.

4. The Core Idea: Binary Exponentiation

Binary exponentiation works using repeated squaring:

2¹
2² = (2¹)²
2⁴ = (2²)²
2⁸ = (2⁴)²
2¹⁶ = (2⁸)²
2³² = (2¹⁶)²
2⁶⁴ = (2³²)²

Now we only need log₂(101) ≈ 7 squaring operations.

Time Complexity

✅ O(log n)
instead of
❌ O(n)

This is why binary exponentiation is foundational in:

cryptography
RSA
modular arithmetic
competitive programming

5. Why Modulo Makes This Even Better

A critical rule of modular arithmetic:

(a × b) mod m = ((a mod m) × (b mod m)) mod m

This means:

We can reduce at every step
Numbers never become large
Correctness is preserved

This rule was the source of early confusion — and the source of clarity once understood.

6. Watching the Pattern Emerge (mod 7)

Now compute powers of 2 modulo 7:

Power	Value	mod 7
2¹	2	2
2²	4	4
2⁴	16	2
2⁸	4	4
2¹⁶	2	2
2³²	4	4
2⁶⁴	2	2

🔁 Pattern discovered:

Powers of 2 modulo 7 alternate between 2 and 4

This is the “aha moment”.

Now suddenly:

2³² ≡ 4 (mod 7)

makes complete sense.

7. Final Computation: 2¹⁰¹ mod 7

Recall:

2¹⁰¹ = 2⁶⁴ × 2³² × 2⁴ × 2¹

Substitute modulo values:

2⁶⁴ ≡ 2
2³² ≡ 4
2⁴ ≡ 2
2¹ ≡ 2

Multiply:

2 × 4 × 2 × 2 = 32

Reduce:

32 mod 7 = 4

✅ Final Answer

2¹⁰¹ ≡ 4 (mod 7)

That’s why the board confidently ends with:

32 ≡ 4 (mod 7)

8. The Algebra That Explains Everything

Another key clarification came from algebra:

If:

a = d·q₁ + r₁
b = d·q₂ + r₂

Then:

a·b = d·(…) + r₁·r₂

Which means:

(a·b) % d = (r₁·r₂) % d

In plain English:

Only remainders matter in modular multiplication.

This is the mathematical backbone of modular exponentiation.

9. The Mental Model You Should Remember Forever