Question

1) Докажите, что при любом натуральном n число 21^n + 4^(n+2) делится на 17
2)Найти последние две цифры числа 7^302

Answer 1

1) $21^n+4^{n+2}\equiv 4^n+16\times 4^n \equiv 17\times 4^n\equiv 0\mod17$

2) требуется вычислить $7^{302} \mod100$. По модулю 25: $7^2 \equiv -1 \mod 25$, поэтому $(7^2)^{151}\equiv (-1)^{151}\equiv -1 \mod 25$. По модулю 4: $7^2\equiv 1 \mod 4$, поэтому $(7^2)^{151}\equiv 1\mod 4$. По китайской теореме об остатках решение единственно по модулю $25\times 4=100$ и равно $-1\times 4\times 19+1\times 25\times 1=-51\equiv 49\mod100$ (результат прямого применения теоремы). Итак, число оканчивается на 49