Найдите последние три цифры числа

Question

Дано ответов: 2

Правильный ответ

Три последние цифры , если рассматривать задачу как нахождение остатка , то это задача на нахождения остатка на $1000$ .
$19^{8^7}\equiv abc \ mod(1000)$
Удобно воспользоватся теоремой Эйлера, для упрощения числа.
$\phi(1000)=\phi(5^3*2^3)=100*4=400$
То есть
$19^{400}\equiv 1 \ mod (1000)$
Сама теорема, если $a,m$ простые числа то
$a^{\phi(m)}\equiv1$ $mod \ m$ .
$\phi(m)$ функция Эйлера .
Теперь найдем остатком от    $\frac{8^7}{400}=\frac{2^{17}}{25}$
то есть
$2^{17}\equiv x mod(25)\\ x=22$
то есть сам остаток равен $22*16=352$ , итого получаем что число
$8^7=(400*x+352)\\ 19^{400x+352}=19^{400x}*19^{352}$
Так как $19^{400}\equiv 1 mod 1000$
То задача эквивалента нахождению остатка от число
$19^{352}=x mod 1000$
$\frac{19^{350}*19^2}{2^3*5^3}$ число
$19$ всегда оканчивается на $1$ учтем , используя опять теореме Эйлера получим
$19^{350}\equiv=1\\ mod 1000\\$ , тогда сам остаток равен
$19^2=361$

Ответ $361$

Матов_zn (224k баллов) 18 Март, 18

помогуна5_zn · Answer 1 · 2018-03-18T20:32:24+0000

Для начала посчитаем показатель степени $8^{7} =2097152$
последние три цифры в числе повторяются всегда при увеличении показателя степени на 10. Поэтому достаточно показатель степени разделить на 10 и посмотреть остаток.
2097152:10 в остатке получим 2. Т.е. последние 3 цифры у числа $19^{8^7}$ будут такими же что и у числа $19^{2} =361$
Ответ: 361