Examkin

Question

Difficulty: HardDivisibility Rules and Remainder Theorem
What is the remainder when the sum 222026+392026+562026+732026+90202622^{2026} + 39^{2026} + 56^{2026} + 73^{2026} + 90^{2026} is divided by 1717?

Answer: 11

Answer

11
By reducing all bases modulo 17, the sum becomes five identical terms of 520265^{2026}, which simplifies to 520275^{2027}. Using Fermat's Little Theorem (516≡1(mod17)5^{16} \equiv 1 \pmod{17}), the exponent 2027 is reduced modulo 16 to 11. Finally, calculating 511(mod17)5^{11} \pmod{17} yields −40-40, which corresponds to a positive remainder of 11.

Step-by-Step Solution

1
Reduce each base in the expression modulo 17.
The expression simplifies to 52026+52026+52026+52026+52026(mod17)5^{2026} + 5^{2026} + 5^{2026} + 5^{2026} + 5^{2026} \pmod{17}.
Using the property (A(modM))k(modM)=Ak(modM)(A \pmod M)^k \pmod M = A^k \pmod M, we find that 22, 39, 56, 73, and 90 all leave a remainder of 5 when divided by 17.
2
Combine the identical terms into a single expression.
The sum becomes 5×52026=52027(mod17)5 \times 5^{2026} = 5^{2027} \pmod{17}.
Since there are exactly 5 identical terms, adding them together is equivalent to multiplying the term by 5, which conveniently increases the exponent by 1.
3
Apply Fermat's Little Theorem to reduce the large exponent.
Fermat's Little Theorem states 516≡1(mod17)5^{16} \equiv 1 \pmod{17}. Dividing the exponent 2027 by 16 yields 2027=16×126+112027 = 16 \times 126 + 11.
Because 17 is a prime number and does not divide 5, we can use ap−1≡1(modp)a^{p-1} \equiv 1 \pmod p to eliminate full cycles of 16 in the exponent.
4
Simplify the remaining expression 511(mod17)5^{11} \pmod{17}.
The expression reduces to −6(mod17)-6 \pmod{17}.
We break down the power: 52=25≡85^2 = 25 \equiv 8, 54≡82=64≡−45^4 \equiv 8^2 = 64 \equiv -4, and 58≡(−4)2=16≡−15^8 \equiv (-4)^2 = 16 \equiv -1. Thus, 511=58×52×51≡(−1)×8×5=−405^{11} = 5^8 \times 5^2 \times 5^1 \equiv (-1) \times 8 \times 5 = -40. Since −40=−3×17+11-40 = -3 \times 17 + 11, the remainder is 11 (or −6-6).
5
Convert any negative remainder to a valid positive remainder.
−6+17=11-6 + 17 = 11. The final remainder is 11.
A standard remainder must be a positive integer strictly less than the divisor.

Key Concept

Fermat's Little Theorem and Modulo Arithmetic Reductions
Rate this question

Topics

Divisibility Rules and Remainder Theorem

More questions from this topic