math.wiki
Logic, proof and discrete math › Introductory number theory › Modular arithmetic › Powers modulo n
Open on the map
Discrete Mathematics and Proof

Powers modulo n

The number 11 to the 53rd power has 56 digits, yet its remainder on division by 97 is a number below 97. Can we find that remainder without ever writing the power down?

You need
Congruence modulo n and its arithmeticDiscrete Mathematics and ProofLaws of exponentsGrade 8
Unlocks
Fermat's little theoremDiscrete Mathematics and Proof
Where you are 7 in Modular arithmetic
Logic, proof and discrete math6
Introductory number theory8
Modular arithmetic7
Congruence modulo n and its arithmetic
Powers modulo n
Where the divisibility tests come fromFermat's little theoremModular inverses and linear congruences▾ Show all 7 (2 more)

When you reach for it

Reach for this move whenever a question asks for a power a^k only up to a remainder: the last digit of 3^{2026}, the weekday a huge number of days from now, whether 23 divides 2^k - 1. The power itself is usually far too large to write. The remainder is small, and two facts get to it in a few lines. First, by Congruence modulo n and its arithmetic a number may be replaced by its remainder after every multiplication, so no number in the work ever exceeds (n - 1)^2. Second, squaring over and over, guided by the binary digits of k, reaches a^k in about 2 \log_2 k multiplications instead of k - 1. A third idea often finishes the job by hand: the remainders of a^0, a^1, a^2, \dots eventually repeat in a cycle, and a cycle turns a huge exponent into a small one.

The procedure

Reducing after every multiplication. Since a^{k+1} = a^k \cdot a, suppose a^k \equiv r \pmod{n}. The multiplication rule (Theorem 3 of Congruence modulo n and its arithmetic), applied to a^k \equiv r and a \equiv a, gives

a^{k+1} \equiv r \cdot a \pmod{n}.

So each new power comes from the previous remainder, and r \cdot a may be reduced at once. If a is first replaced by its remainder too (Corollary 4 there), every product in the work is of two numbers below n.

Repeated squaring. One step at a time still takes k - 1 multiplications for a^k. Squaring is faster: by the power-of-a-power law (Laws of exponents), (a^{2^j})^2 = a^{2^{j+1}}, so the list

a,\ a^2,\ a^4,\ a^8,\ \dots,\ a^{2^L}

takes L squarings, each reduced modulo n. To reach any exponent, write k in base 2. By the base-b theorem of Numbers in other bases with b = 2, every positive integer has exactly one binary expansion k = (d_L \cdots d_1 d_0)_2 with d_L = 1, meaning

\begin{aligned} k &= d_L 2^L + \dots + d_1 2^1 + d_0 2^0, \\ d_i &\in \{0, 1\}. \end{aligned}

The product-of-powers law, a^{x + y} = a^x a^y, turns that sum into a product:

a^k = \prod_{d_i = 1} a^{2^i}.

So a^k is the product of those squares whose binary digit is 1, reduced after each multiplication.

Counting the multiplications. If k has L + 1 binary digits, then 2^L \le k, so L \le \log_2 k. The squarings number L. If s of the digits are 1, combining the chosen squares takes s - 1 \le L multiplications. In total at most 2L \le 2 \log_2 k, against k - 1 one step at a time. For k = 2026 that is at most 20 against 2{,}025.

Cycles of powers. Fix a and n \ge 2. The remainders of a^0, a^1, \dots, a^n are n + 1 values in a set of n, so by the pigeonhole principle two agree: a^i \equiv a^j \pmod{n} for some 0 \le i < j \le n. Multiplying both sides by a^m gives a^{i+m} \equiv a^{j+m} for every m \ge 0. So from a^i on, the remainders repeat with period j - i. The powers before the cycle are its tail.

When a power hits 1. Suppose t is the smallest positive integer with a^t \equiv 1 \pmod{n}. It is called the order of a modulo n, and three things follow.

  • There is no tail. For k \ge 0 write k = qt + r with 0 \le r < t (The division algorithm). Then a^k = (a^t)^q a^r \equiv 1^q a^r = a^r, that is, a^k \equiv a^{k \bmod t} \pmod{n}.
  • The cycle has length exactly t. If a^i \equiv a^j with 0 \le i < j < t, multiply both sides by a^{t-i}: the left side becomes a^t \equiv 1 and the right side a^{t + (j - i)} \equiv a^{j-i}. Then a^{j-i} \equiv 1 with 0 < j - i < t, against the choice of t. So a^0, \dots, a^{t-1} are all different modulo n.
  • The exponents giving 1 are exactly the multiples of t. If a^e \equiv 1, the first point gives a^{e \bmod t} \equiv 1 with 0 \le e \bmod t < t, so e \bmod t = 0. Conversely a^{qt} = (a^t)^q \equiv 1.

A power that hits 1 early therefore makes a short cycle, and any exponent may be reduced modulo t. If no positive power is 1 there may be a tail, and an exponent may be reduced by the period only while it stays past the tail. The figure shows both shapes.

1 3 9 7
\times 3
3^k \bmod 10
 1 2 4 8 16
2^k \bmod 24
Figure 1Left, the powers of 3 modulo 10: they return to 1 and go around a cycle of length 4. Right, the powers of 2 modulo 24: a tail 1, 2, 4 leads into a cycle 8, 16 of length 2, and 1 never comes back.

Worked examples

Example 1

One multiplication at a time

Find 6^9 \bmod 17, reducing after every multiplication, and check against the full power.

Solution

Each column multiplies the previous remainder by 6 and reduces, which the multiplication rule allows:

kprevious remainder times 66^k \bmod 17
166
2362
31212
4724
5247
6428
74814
88416
99611

For instance at k = 4 the product is 12 \cdot 6 = 72 = 4 \cdot 17 + 4. No product exceeds 16 \cdot 6 = 96. So 6^9 \bmod 17 = 11. Check: 6^9 = 10{,}077{,}696 = 17 \cdot 592{,}805 + 11.

Example 2

Repeated squaring when a square reaches 1

Find 5^{77} \bmod 13 by repeated squaring, and count the multiplications.

Solution

In base 2, 77 = 64 + 8 + 4 + 1 = (1001101)_2. Square and reduce: 5^2 = 25 \equiv 12 \pmod{13}, then 5^4 \equiv 12^2 = 144 = 11 \cdot 13 + 1 \equiv 1. Once a square is 1, every later square is 1^2 = 1, so 5^8 \equiv 5^{16} \equiv 5^{32} \equiv 5^{64} \equiv 1. Multiply the squares whose digit is 1:

\begin{aligned} 5^{77} &= 5^{64} \cdot 5^{8} \cdot 5^{4} \cdot 5^{1} \\ &\equiv 1 \cdot 1 \cdot 1 \cdot 5 = 5 \pmod{13}. \end{aligned}

So 5^{77} \bmod 13 = 5. The work took 6 squarings and 3 further multiplications, 9 in all, against 76 one at a time. The order of 5 modulo 13 is 4, and indeed 77 = 4 \cdot 19 + 1 gives 5^{77} \equiv 5^1 by the cycle as well.

Example 3

A full run of repeated squaring

Find 11^{53} \bmod 97.

Solution

In base 2, 53 = 32 + 16 + 4 + 1 = (110101)_2. Each square below is the previous one squared and reduced modulo 97; a negative remainder is used where it keeps the numbers small, which the replacement rule allows.

jsquare11^{2^j} \bmod 97digit
011111
111^2 = 121240
224^2 = 57691 \equiv -61
3(-6)^2 = 36360
436^2 = 1{,}296351
535^2 = 1{,}225611

The reductions are 576 = 5 \cdot 97 + 91, 1{,}296 = 13 \cdot 97 + 35 and 1{,}225 = 12 \cdot 97 + 61.

Multiply the rows with digit 1, reducing after each product:

\begin{aligned} 11^{53} &\equiv 61 \cdot 35 \cdot 91 \cdot 11 \\ &= 2{,}135 \cdot 91 \cdot 11, \quad 2{,}135 = 22 \cdot 97 + 1 \\ &\equiv 1 \cdot 91 \cdot 11 = 1{,}001 \\ &= 10 \cdot 97 + 31 \equiv 31 \pmod{97}. \end{aligned}

So 11^{53} \bmod 97 = 31, after 5 squarings and 3 multiplications, never a number above 2{,}135. The power itself has 56 digits.

Example 4

A last digit from a cycle

Find the last digit of 3^{2026}.

Solution

The last digit of a positive integer is its remainder modulo 10. The powers of 3 modulo 10 are 3^0 \equiv 1, 3^1 \equiv 3, 3^2 \equiv 9, 3^3 \equiv 27 \equiv 7, and 3^4 \equiv 7 \cdot 3 = 21 \equiv 1, as in the left half of the figure. So the order of 3 modulo 10 is 4 and 3^k \equiv 3^{k \bmod 4}. Since 2026 = 4 \cdot 506 + 2,

3^{2026} = (3^4)^{506} \cdot 3^2 \equiv 1 \cdot 9 = 9 \pmod{10}.

The last digit is 9.

Example 5

Which powers give 1

For which positive integers k does 23 divide 2^k - 1? Find 2^{2000} \bmod 23.

Solution

Divisibility by 23 means 2^k \equiv 1 \pmod{23}. List the powers, doubling and reducing each time:

\begin{aligned} &2,\ 4,\ 8,\ 16,\ 32 \equiv 9,\ 18,\ 36 \equiv 13, \\ &26 \equiv 3,\ 6,\ 12,\ 24 \equiv 1. \end{aligned}

The first 1 is at k = 11, so the order of 2 modulo 23 is 11. By the third point of the procedure, 23 \mid 2^k - 1 exactly when 11 \mid k. The powers take only 11 of the 22 nonzero remainders, because the cycle closes early.

For the power, 2000 = 11 \cdot 181 + 9, so 2^{2000} \equiv 2^9 \pmod{23}, the ninth entry of the list: 6. Check: 2^9 = 512 = 22 \cdot 23 + 6.

Example 6

A cycle with a tail

Find 2^{100} \bmod 24.

Solution

The powers of 2 modulo 24 are 1, 2, 4, 8, 16, then 32 \equiv 8, then 16 again. So 2^5 \equiv 2^3, and multiplying by 2^m gives 2^{5+m} \equiv 2^{3+m}: from k = 3 on, the remainders repeat with period 2, odd exponents giving 8 and even ones 16. This is the right half of the figure.

No positive power is 1 here: 2^k - 1 is odd for k \ge 1, and an odd number is not a multiple of 24. So the shortcut a^k \equiv a^{k \bmod t} is not available, and reducing 100 by the period to 0 would wrongly give 2^0 = 1. The exponent may only be reduced to one past the tail: 100 is even and at least 3, so

2^{100} \equiv 2^4 = 16 \pmod{24}.

Check: 2^{100} - 16 = 16(2^{96} - 1), and 2^{96} - 1 = 4^{48} - 1 is divisible by 4 - 1 = 3 because 4 \equiv 1 \pmod{3}. So 2^{100} - 16 is a multiple of 16 \cdot 3 = 48, hence of 24.

Example 7

Checking a big power two ways

Find 6^{45} \bmod 91 by repeated squaring, then confirm it with the cycle of powers.

Solution

First way. 45 = 32 + 8 + 4 + 1 = (101101)_2. The squares modulo 91 are 6, 36, 36^2 = 1{,}296 = 14 \cdot 91 + 22 so 22, 22^2 = 484 = 5 \cdot 91 + 29 so 29, 29^2 = 841 = 9 \cdot 91 + 22 so 22, and 22^2 \equiv 29 again. So 6^1, 6^2, 6^4, 6^8, 6^{16}, 6^{32} leave 6, 36, 22, 29, 22, 29. Then

\begin{aligned} 6^{45} &= 6^{32} \cdot 6^{8} \cdot 6^{4} \cdot 6 \\ &\equiv 29 \cdot 29 \cdot 22 \cdot 6 \\ &\equiv 22 \cdot 22 \cdot 6 \equiv 29 \cdot 6 \\ &= 174 \equiv 83 \pmod{91}. \end{aligned}

Second way. Multiply by 6 one step at a time: the remainders of 6^1 to 6^6 are 6, 36, 34, 22, 41, 64, and those of 6^7 to 6^{12} are 20, 29, 83, 43, 76, 1. The order of 6 is 12, and 45 = 3 \cdot 12 + 9, so 6^{45} \equiv 6^9 \equiv 83. The two routes share no step after the first square and agree: 6^{45} \bmod 91 = 83. They also agree on detail: the cycle says 6^{16} \equiv 6^4, which is why the squares repeated 22, 29, 22, 29.

Boundaries

  • The base may be reduced, the exponent may not be reduced modulo n. Only modulo a period of the powers, and then only past the tail. Example 6 shows the tail mattering.
  • The modulus is a positive integer, as in Congruence modulo n and its arithmetic, and the exponent here is a whole number k \ge 0, with a^0 = 1. A negative exponent would need an inverse modulo n, which exists only sometimes (Modular inverses and linear congruences).
  • A cycle always exists, a return to 1 need not. When a and n share a factor greater than 1, no positive power of a is 1 modulo n, since a^k - 1 is then not a multiple of that factor. When they share none, the powers do return to 1; that is stated here without proof.
  • The bound 2 \log_2 k counts multiplications, each of numbers below n. It says nothing about how hard one multiplication is when n itself is enormous.

Where this goes next

For a prime modulus, a shortcut that predicts where the powers return to 1 comes later, in Fermat's little theorem. Fast powers modulo a large n are also the working engine of RSA public-key encryption, where messages are locked and unlocked by raising to exponents hundreds of digits long.

Exercises

Reducing as you go

  1. Find 3^8 \bmod 17 one multiplication at a time, and check with 3^8 = 6{,}561.
  2. Find 13^6 \bmod 21, and explain why every even power of 13 gives the same remainder.
  3. Find 8^5 \bmod 33, using a negative remainder where it helps.

Repeated squaring

  1. Write 25 in base 2 and find 2^{25} \bmod 19 by repeated squaring.
  2. Find 7^{38} \bmod 31 by repeated squaring.
  3. Find 12^{29} \bmod 85 by repeated squaring.
  4. How many multiplications does repeated squaring use for a^{1{,}000{,}000}?
  5. Count the multiplications for a^{1023} and for a^{1024}. Which exponent is cheaper?

Using a cycle

  1. Find the last digit of 7^{999}.
  2. Find the last digit of 2^{500}.
  3. Find the last two digits of 7^{2030}.
  4. Ksawery counts 10^{100} days forward from a Monday. On what weekday does he land?
  5. Find every positive integer k for which 26 \mid 3^k - 1.
  6. Find the order of 5 modulo 63, and use it to find 5^{100} \bmod 63.
  7. Describe all the powers 2^k \bmod 1024 for k \ge 0: the tail, the cycle, and its length.

Checking and reasoning

  1. Find 4^{50} \bmod 51 two ways: by repeated squaring, and by the order of 4.
  2. Prove that 11 \mid 3^{5m} - 1 for every positive integer m.
  3. Suppose a has order 6 modulo n. Find the orders of a^2 and of a^3 modulo n, and prove your answers.
  4. Modulo 11, 12 \equiv 1. Explain why this does not give 2^{12} \equiv 2^1 \pmod{11}, and say what may be done with the exponent 12 instead.
  5. Among the exponents k from 2^L to 2^{L+1} - 1, find the ones for which repeated squaring uses the most multiplications and the one that uses the fewest, and prove it.
Answers
  1. 16. Remainders 3, 9, 27 \equiv 10, 30 \equiv 13, 39 \equiv 5, 15, 45 \equiv 11, 33 \equiv 16. Check: 6{,}561 = 385 \cdot 17 + 16.
  2. 1. 13^2 = 169 = 8 \cdot 21 + 1, so 13^2 \equiv 1 and 13^{2m} = (13^2)^m \equiv 1^m = 1 for every m; in particular 13^6 \equiv 1.
  3. 32. 8^2 = 64 \equiv -2, 8^3 \equiv -16, 8^4 \equiv -128 \equiv -128 + 132 = 4, 8^5 \equiv 32. Check: 8^5 = 32{,}768 = 993 \cdot 33 - 1 \equiv -1 \equiv 32.
  4. 25 = (11001)_2 = 16 + 8 + 1. Squares modulo 19: 2, 4, 16, 256 \equiv 9, 81 \equiv 5, so 2^{25} \equiv 5 \cdot 9 \cdot 2 = 90 \equiv 14. Answer 14.
  5. 10. 38 = 32 + 4 + 2. Squares modulo 31: 7, 18, 14, 10, 7, 18 for 7^1 to 7^{32}. Then 7^{38} \equiv 18 \cdot 14 \cdot 18; 18 \cdot 14 = 252 \equiv 4 and 4 \cdot 18 = 72 \equiv 10.
  6. 82. 29 = 16 + 8 + 4 + 1. Squares modulo 85: 12, 144 \equiv 59, 59^2 = 3{,}481 \equiv 81 \equiv -4, 16, 256 \equiv 1. So 12^{29} \equiv 1 \cdot 16 \cdot (-4) \cdot 12, which is -768, and -768 + 850 = 82.
  7. 25. 2^{19} \le 10^6 < 2^{20}, so 10^6 has 20 binary digits, (11110100001001000000)_2, and 19 squarings. It has seven digits 1, so 6 more multiplications: 25 against 999{,}999.
  8. 1023 = (1111111111)_2: 9 squarings and 9 multiplications, 18. 1024 = 2^{10}: 10 squarings and none, 10. The larger exponent is cheaper.
  9. 3. Powers of 7 modulo 10: 7, 9, 3, 1, order 4; 999 = 4 \cdot 249 + 3, so 7^{999} \equiv 7^3 \equiv 3.
  10. 6. From k = 1 the powers of 2 modulo 10 run 2, 4, 8, 6 with period 4 (the tail is 2^0 = 1). Since 500 = 4 + 4 \cdot 124 and 4 is past the tail, 2^{500} \equiv 2^4 = 16 \equiv 6.
  11. 49. Modulo 100: 7^2 = 49, 7^3 \equiv 343 \equiv 43, 7^4 \equiv 301 \equiv 1. Order 4, 2030 = 4 \cdot 507 + 2, so 7^{2030} \equiv 49.
  12. Friday. Modulo 7, 10 \equiv 3 and the powers of 3 run 3, 2, 6, 4, 5, 1, order 6. 100 = 6 \cdot 16 + 4, so 10^{100} \equiv 3^4 \equiv 4. Monday is 1, and 1 + 4 = 5 is Friday.
  13. The multiples of 3. 3^1 = 3, 3^2 = 9, 3^3 = 27 \equiv 1 \pmod{26}, so the order is 3, and 3^k \equiv 1 exactly when 3 \mid k.
  14. Order 6: the powers run 5, 25, 125 \equiv 62, 310 \equiv 58, 290 \equiv 38, 190 \equiv 1. Since 100 = 6 \cdot 16 + 4, 5^{100} \equiv 5^4 \equiv 58.
  15. For 0 \le k \le 9, 2^k < 1024, so 2^k \bmod 1024 = 2^k: the tail is 1, 2, 4, \dots, 512. For k \ge 10, 1024 \mid 2^k, so the remainder is 0: a cycle of length 1, entered after a tail of length 10.
  16. 16. 50 = 32 + 16 + 2; squares 4, 16, 256 \equiv 1, then all 1, so 4^{50} \equiv 1 \cdot 1 \cdot 16. Second way: 4^3 = 64 \equiv 13 and 4^4 \equiv 52 \equiv 1, order 4; 50 = 4 \cdot 12 + 2 gives 4^{50} \equiv 4^2 = 16.
  17. Proof. 3^5 = 243 = 22 \cdot 11 + 1, so 3^5 \equiv 1 \pmod{11}. By the power rule of Corollary 4 in Congruence modulo n and its arithmetic, 3^{5m} = (3^5)^m \equiv 1^m = 1 \pmod{11}, that is, 11 \mid 3^{5m} - 1. \square
  18. a^2 has order 3 and a^3 has order 2. Proof. By the third point of the procedure, a^e \equiv 1 exactly when 6 \mid e. For a^2: (a^2)^m = a^{2m}, and 6 \mid 2m exactly when 3 \mid m, so the smallest positive m with (a^2)^m \equiv 1 is 3. For a^3: (a^3)^m = a^{3m}, and 6 \mid 3m exactly when 2 \mid m, so the smallest such m is 2. \square
  19. Congruence lets a base be replaced, because the multiplication rule replaces factors; an exponent counts how many factors there are, and 12 factors are not 1 factor. Indeed 2^{12} = 4{,}096 = 372 \cdot 11 + 4, so 2^{12} \equiv 4, while 2^1 = 2. The powers of 2 modulo 11 run 2, 4, 8, 5, 10, 9, 7, 3, 6, 1, so the order of 2 is 10, and the exponent may be reduced modulo 10: 12 \equiv 2 \pmod{10} gives 2^{12} \equiv 2^2 = 4.
  20. Most: only k = 2^{L+1} - 1, with 2L. Fewest: only k = 2^L, with L. Proof. Every such k has L + 1 binary digits with leading digit 1; say s of them are 1, so 1 \le s \le L + 1. The method uses L squarings and s - 1 multiplications, L + s - 1 in all, which grows with s. The largest value, s = L + 1, means every digit is 1, which is k = 2^{L+1} - 1. The smallest, s = 1, means only the leading digit is 1, which is k = 2^L. \square
kg1128 · updated 2026-10-22 · CC-BY-SA-4.0