Technique

Reduce a large power by the cycle of its base modulo $n$

Arithmetic • Number System • Divisibility

Statement

For a fixed modulus

n

and a base

a

coprime to

n

, the powers

a^{1}, a^{2}, a^{3}, \dots

repeat modulo

n

with some cycle length

L

, where

L

is the smallest exponent with

a^{L} \equiv 1 (mod n)

. Writing

m = q L + r

then gives

a^{m} \equiv a^{r} (mod n)

How to use it

1Reduce the base modulo $n$ first, then compute $a^{1}, a^{2}, a^{3}, \dots$ until $1$ reappears; that exponent is $L$ .
2Divide the exponent $m$ by $L$ and keep only the remainder $r$ ; a remainder of $0$ means $a^{m} \equiv 1$ .
3This works for a composite modulus, where Fermat's little theorem does not apply.

What is the remainder when

2^{100}

is divided by

7

Step-by-step

1
$2^{1} \equiv 2$ , $2^{2} \equiv 4$ , $2^{3} = 8 \equiv 1 (mod 7)$
Why: The cycle closes at the third power, so $L = 3$ .
2
$100 = 3 \times 33 + 1$
Why: Only the remainder of the exponent modulo $L$ matters.
3
$2^{100} \equiv (2^{3})^{33} \times 2^{1} \equiv 1^{33} \times 2 = 2 (mod 7)$

Answer

2

Watch out

The base must be coprime to the modulus; if it shares a factor, the powers never return to

1

and this fails. The cycle length divides Euler's

φ (n)

but is often shorter, so it must be found rather than assumed.

Builds on

Also known as

order modulo n, power cycle mod n, remainder of a large power, cyclicity modulo a composite, reduce the exponent