What is the remainder when 17^{17^{17}} is divided by 7? — GMAT

What is the remainder when $17^{17^{17}}$ is divided by $7$ ?

Answer: 5

The remainder when

17^{17^{17}}

is divided by

7

5

First, reduce the base modulo

7

17 \equiv 3 \pmod 7

, turning the expression into

3^{17^{17}} \pmod 7

. Next, evaluate the pattern of powers of

3 \pmod 7

3^1 \equiv 3

3^2 \equiv 2

3^3 \equiv 6

3^4 \equiv 4

3^5 \equiv 5

, and

3^6 \equiv 1

, showing a period of

6

. To find which term of the cycle corresponds to the exponent

17^{17}

, evaluate

17^{17} \pmod 6

. Since

17 \equiv -1 \pmod 6

17^{17} \equiv (-1)^{17} = -1 \equiv 5 \pmod 6

. Finally, the

5

th term of the cycle gives

3^5 = 243 \equiv 5 \pmod 7

. Therefore, the remainder is

5

Reduce the base modulo 7

17 \equiv 3 \pmod 7

, so

17^{17^{17}} \equiv 3^{17^{17}} \pmod 7

Modular arithmetic permits replacing the base of an exponential expression with its remainder upon division by the modulus.

Determine the cyclicity period of powers of 3 modulo 7

The remainders of

3^n \pmod 7

repeat in a cycle of length 6:

(3, 2, 6, 4, 5, 1)

By Fermat's Little Theorem,

3^6 \equiv 1 \pmod 7

, meaning the sequence of remainders repeats every 6 integer powers.

Evaluate the exponent

17^{17}

modulo the period length 6

17 \equiv -1 \pmod 6

, so

17^{17} \equiv (-1)^{17} = -1 \equiv 5 \pmod 6

The position within the 6-term cyclicity pattern depends on the exponent modulo 6. Using negative remainders simplifies calculating odd powers of

-1

Calculate the final remainder using the 5th position in the cyclicity pattern

3^5 = 243 = 7 \times 34 + 5 \equiv 5 \pmod 7

Since the exponent leaves a remainder of 5 when divided by 6, the overall remainder corresponds to

3^5 \pmod 7

Modular cyclicity and tower exponent remainder reduction

Question