2^{100} is a number with 31 digits — 1{,}267{,}650{,}600{,}228{,}229{,}401{,}496{,}703{,}205{,}376, to be precise. No Indian board exam is going to ask you to compute that. But an exam might ask what is 2^{100} \bmod 7? and expect a single-digit answer in under a minute. The method that gets you there is the backbone of every "large-power-mod-small-number" problem, and it relies on a single key observation: the powers of a mod n always eventually cycle.

Once you see the cycle, the exponent 100 reduces to a small number — and the rest is a peek at a tiny table.

Step 1: Compute a few powers of 2 mod 7

Start writing out the powers one by one. At every step, multiply the previous remainder by 2 and reduce mod 7.

2^1 \equiv 2, \quad 2^2 \equiv 4, \quad 2^3 \equiv 8 \equiv 1 \pmod 7.

Stop. You hit 1 at k = 3. The moment a power hits 1, the next one is 2^1 = 2 again, and the whole sequence repeats.

Why: if 2^k \equiv 1 \pmod 7, then 2^{k+1} = 2^k \cdot 2 \equiv 1 \cdot 2 = 2 \pmod 7, which matches 2^1. The sequence has looped back to its start.

So the cycle of powers of 2 modulo 7 is

2, \; 4, \; 1, \; 2, \; 4, \; 1, \; 2, \; 4, \; 1, \; \dots

with period 3.

Cycle of powers of 2 modulo 7Three boxes in a circle labelled 2 to the 1 equivalent to 2, 2 squared equivalent to 4, and 2 cubed equivalent to 1. Arrows connect them in a cycle. A note says the cycle length is 3 and that the exponent 100 reduces modulo 3. 2¹ ≡ 2 position 1 2² ≡ 4 position 2 2³ ≡ 1 position 3 (loop back) cycle length: 3
The powers of $2$ modulo $7$ cycle with period $3$. To find $2^{100} \bmod 7$, you only need to know where $100$ lands in this three-step cycle — which is the same as knowing $100 \bmod 3$.

Step 2: Reduce the exponent modulo the cycle length

The sequence 2^k \bmod 7 depends only on k \bmod 3 (the cycle length). So

2^{100} \equiv 2^{100 \bmod 3} \pmod 7.

Compute 100 \bmod 3: 100 = 3 \cdot 33 + 1, so 100 \bmod 3 = 1. That is it. The exponent 100 is equivalent to 1 in the cycle.

Why: 2^{100} = (2^3)^{33} \cdot 2^1 \equiv 1^{33} \cdot 2 = 2 \pmod 7. The 2^3 \equiv 1 fact chews up 99 of the 100 powers, leaving a single leftover factor of 2.

Step 3: Look up the answer in your tiny table

Position 1 in the cycle is 2^1 \equiv 2 \pmod 7. So

\boxed{2^{100} \equiv 2 \pmod 7.}

The remainder when the 31-digit number 2^{100} is divided by 7 is 2. You did it using single-digit arithmetic and one short division of 100 by 3.

The general recipe

This pattern solves any problem of the form "a^N \bmod n" for large N.

  1. Compute successive powers a, a^2, a^3, \dots \pmod n, reducing at each step. Stop the first time you hit 1.
  2. Let c be the cycle length — the exponent at which you hit 1. (You are guaranteed to hit 1 as long as \gcd(a, n) = 1.)
  3. Compute r = N \bmod c.
  4. Look up a^r \pmod n in your short table. That is the answer.

Caveat: if r = 0, the answer is a^c \equiv 1 \pmod n, not a^0 = 1 by accident — but they happen to be the same thing, so "use a^c" and "use a^0 = 1" both produce 1. This is a nice invariant, not a trap.

Why does the cycle exist?

There are only n possible remainders mod n, but infinitely many powers. By the pigeonhole principle, some two powers a^i and a^j with i < j must give the same remainder. When \gcd(a, n) = 1, you can multiply both sides by a^{-i} to get 1 \equiv a^{j - i} \pmod n. So some positive exponent j - i makes a give remainder 1, and from that point on the powers cycle.

The smallest such exponent is called the order of a modulo n, and a classical result (Fermat's little theorem for prime n) tells you the order always divides n - 1. For n = 7, that means the order of 2 divides 6. It turned out to be 3, which divides 6 — no accident.

Two more worked problems, same method

Compute $3^{50} \bmod 11$.

Cycle. 3^1 \equiv 3, 3^2 \equiv 9, 3^3 \equiv 27 \equiv 5, 3^4 \equiv 15 \equiv 4, 3^5 \equiv 12 \equiv 1 \pmod{11}.

Cycle length: 5.

Reduce. 50 \bmod 5 = 0, so 3^{50} \equiv (3^5)^{10} \equiv 1^{10} \equiv 1 \pmod{11}.

Answer. 3^{50} \equiv 1 \pmod{11}.

Compute $7^{100} \bmod 13$.

Cycle. 7^1 \equiv 7, 7^2 \equiv 49 \equiv 10, 7^3 \equiv 70 \equiv 5, 7^4 \equiv 35 \equiv 9, 7^5 \equiv 63 \equiv 11, 7^6 \equiv 77 \equiv 12, 7^7 \equiv 84 \equiv 6, 7^8 \equiv 42 \equiv 3, 7^9 \equiv 21 \equiv 8, 7^{10} \equiv 56 \equiv 4, 7^{11} \equiv 28 \equiv 2, 7^{12} \equiv 14 \equiv 1 \pmod{13}.

Cycle length: 12. (Consistent with Fermat: the order of 7 mod 13 divides 12, and here it equals 12.)

Reduce. 100 \bmod 12 = 4, so 7^{100} \equiv 7^4 \equiv 9 \pmod{13}.

Answer. 7^{100} \equiv 9 \pmod{13}.

Faster: repeated squaring when the cycle is long

For a modulus like 13 whose cycle can be 12 long, writing out all 12 powers is tolerable but tedious. A faster alternative is repeated squaring: compute a^2, a^4, a^8, a^{16}, \dots by squaring the previous term, then combine them according to the binary expansion of the exponent.

To compute 7^{100} \bmod 13 with squaring: 100 = 64 + 32 + 4 = 2^6 + 2^5 + 2^2.

7^1 = 7, \; 7^2 = 49 \equiv 10, \; 7^4 \equiv 10^2 = 100 \equiv 9, \; 7^8 \equiv 9^2 = 81 \equiv 3,
7^{16} \equiv 3^2 = 9, \; 7^{32} \equiv 9^2 = 81 \equiv 3, \; 7^{64} \equiv 3^2 = 9.

So 7^{100} = 7^{64} \cdot 7^{32} \cdot 7^4 \equiv 9 \cdot 3 \cdot 9 = 243 \equiv 9 \pmod{13}. Same answer as before, reached in a different way.

For exam-sized exponents (anything below a few hundred) the cycle method is usually faster. For exponents in the thousands or for very large moduli, repeated squaring is the industrial-strength tool. Both are manual, both use only single-digit arithmetic, and neither needs a calculator.

The takeaway

To compute a^N \bmod n by hand:

  1. Find the cycle of powers of a modulo n.
  2. Reduce N modulo the cycle length.
  3. Look up the answer.

The gigantic exponent collapses to a small one because every cycle of powers resets at 1. That resetting is what makes modular exponentiation efficient both by hand and, in modified form, inside every RSA computation on the internet.

Related: Modular Arithmetic · Last-Digit Problems: Switch to Mod 10 · mod Operator vs Congruence Relation · Chinese Remainder Theorem — One Sentence