What is the remainder when the expression 15^{100} + 19^{100} is divided by 17? — State PSC Exam

What is the remainder when the expression $15^{100} + 19^{100}$ is divided by $17$ ?

The remainder when

15^{100} + 19^{100}

is divided by

17

15

Reducing the bases modulo 17 gives

15 \equiv -2

and

19 \equiv 2

. Since

100

is even,

(-2)^{100} + 2^{100} = 2 \cdot 2^{100} = 2^{101}

. By Fermat's Little Theorem (

2^{16} \equiv 1 \pmod{17}

2^{101} \equiv 2^5 = 32 \equiv 15 \pmod{17}

. Thus, the correct remainder is 15.

Reduce the base numbers modulo 17

15 \equiv -2 \pmod{17}

and

19 \equiv 2 \pmod{17}

Using negative remainders simplifies power calculations.

Rewrite the expression using modular congruence

15^{100} + 19^{100} \equiv (-2)^{100} + 2^{100} = 2^{100} + 2^{100} = 2 \times 2^{100} = 2^{101} \pmod{17}

Since the exponent

100

is even,

(-2)^{100} = 2^{100}

Apply Fermat's Little Theorem to simplify the exponent

2^{16} \equiv 1 \pmod{17}

17 is prime and

\gcd(2, 17) = 1

Divide the exponent 101 by 16 to find the remaining power

101 = 16 \times 6 + 5 \implies 2^{101} \equiv (2^{16})^6 \times 2^5 \equiv 1^6 \times 32 \equiv 32 \pmod{17}

Any integer power of 1 is 1 under modular arithmetic.

Compute the final positive remainder

32 = 17 \times 1 + 15 \implies 32 \equiv 15 \pmod{17}

(or

-2 + 17 = 15

)

Remainders must be non-negative integers strictly less than the divisor.

Fermat's Little Theorem and Negative Remainders in Modular Arithmetic

Question