Examkin

Question

Difficulty: Very hardDivisibility Rules and Remainder Theorem

Let NN be the smallest positive integer that leaves remainders of 22, 44, and 66 when divided by 55, 77, and 99, respectively. What is the remainder when N2025N^{2025} is divided by 1717?

  1. 11Answer
  2. B
    6
  3. C
    2
  4. D
    5

Answer

The remainder when N2025N^{2025} is divided by 1717 is 11.
The number NN satisfies N≡−3(modlcm(5,7,9))N \equiv -3 \pmod{\text{lcm}(5,7,9)}, giving N=315−3=312N = 315 - 3 = 312. Reducing 312(mod17)312 \pmod{17} gives 66. By Fermat's Little Theorem, 616≡1(mod17)6^{16} \equiv 1 \pmod{17}, so 62025≡69(mod17)6^{2025} \equiv 6^9 \pmod{17}. Calculating 69(mod17)6^9 \pmod{17} yields −6(mod17)-6 \pmod{17}, which converts to positive remainder 17−6=1117 - 6 = 11.

Step-by-Step Solution

1
Determine the value of the smallest positive integer NN
N=312N = 312
From the problem statement: N≡2≡−3(mod5)N \equiv 2 \equiv -3 \pmod 5, N≡4≡−3(mod7)N \equiv 4 \equiv -3 \pmod 7, and N≡6≡−3(mod9)N \equiv 6 \equiv -3 \pmod 9. Therefore, N+3N + 3 must be divisible by lcm(5,7,9)=315\text{lcm}(5, 7, 9) = 315. The smallest positive integer is N=315−3=312N = 315 - 3 = 312.
2
Reduce NN modulo 1717
N≡6(mod17)N \equiv 6 \pmod{17}
Dividing 312312 by 1717 gives 312=17×18+6312 = 17 \times 18 + 6, so 312≡6(mod17)312 \equiv 6 \pmod{17}.
3
Apply Fermat's Little Theorem to reduce the power
62025≡69(mod17)6^{2025} \equiv 6^9 \pmod{17}
Since 1717 is prime and gcd⁡(6,17)=1\gcd(6, 17) = 1, 616≡1(mod17)6^{16} \equiv 1 \pmod{17}. Expressing the exponent as 2025=16×126+92025 = 16 \times 126 + 9 yields 62025≡(616)126×69≡1126×69≡69(mod17)6^{2025} \equiv (6^{16})^{126} \times 6^9 \equiv 1^{126} \times 6^9 \equiv 6^9 \pmod{17}.
4
Evaluate 69(mod17)6^9 \pmod{17} and convert to positive remainder
Remainder is 1111
Computing successive powers modulo 1717: 62=36≡2(mod17)6^2 = 36 \equiv 2 \pmod{17}, 64≡22=4(mod17)6^4 \equiv 2^2 = 4 \pmod{17}, and 68≡42=16≡−1(mod17)6^8 \equiv 4^2 = 16 \equiv -1 \pmod{17}. Thus, 69=68×6≡(−1)×6=−6(mod17)6^9 = 6^8 \times 6 \equiv (-1) \times 6 = -6 \pmod{17}. Converting to a positive remainder gives −6+17=11-6 + 17 = 11.

Key Concept

Chinese Remainder Theorem (Constant Difference Method), Fermat's Little Theorem, and Negative Remainder Conversion
Rate this question

Topics

Divisibility Rules and Remainder Theorem

More questions from this topic