Найти три последних числа (4652^9371)

Чтобы найти три последних цифры числа \(4652^{9371}\), можно использовать метод вычисления по модулю 1000. Таким образом, мы ищем \(4652^{9371} \mod 1000\). Сначала найдём \(4652 \mod 1000\): \[ 4652 \mod 1000 = 652 \] Теперь нам нужно вычислить \(652^{9371} \mod 1000\). Для такого вычисления удобно использовать метод быстрого возведения в степень и свойства чисел по модулю. Начнём с разложения числа 1000: \[ 1000 = 2^3 \times 5^3 \] Мы можем использовать **теорему китайской теоремы о остатках** (КТO). Сначала найдём \(652^{9371} \mod 8\) и \(652^{9371} \mod 125\), а затем объединяем результаты. 1. **Вычислим \(652 \mod 8\)**: \[ 652 \mod 8 = 4 \] Теперь найдем \(4^{9371} \mod 8\): Поскольку \(4^1 = 4\) и \(4^2 = 0 \mod 8\), для любой степени \(n \geq 2\), имеем: \[ 4^n \mod 8 = 0 \quad (n \geq 2) \] Таким образом: \[ 4^{9371} \mod 8 = 0 \] 2. **Вычислим \(652 \mod 125\)**: \[ 652 \mod 125 = 27 \] Теперь найдем \(27^{9371} \mod 125\). Для этого воспользуемся **малой теоремой Ферма**, которая говорит, что если \(a\) и \(p\) взаимно просты, то: \[ a^{p-1} \equiv 1 \mod p \] Здесь \(p = 125\) (где \(p^k\) — это \(5^3\)), значит: \[ \phi(125) = 125 \left(1 - \frac{1}{5}\right) = 100 \] Поскольку 27 и 125 взаимно просты, можем использовать теорему: \[ 27^{100} \equiv 1 \mod 125 \] Теперь найдем \(9371 \mod 100\): \[ 9371 \mod 100 = 71 \] Значит, нам нужно вычислить \(27^{71} \mod 125\). Используя метод быстрого возведения в степень: - \(27^1 \equiv 27 \mod 125\) - \(27^2 \equiv 729 \mod 125 \equiv 104 \) - \(27^4 \equiv 104^2 = 10816 \mod 125 \equiv 66\) - \(27^8 \equiv 66^2 = 4356 \mod 125 \equiv 31\) - \(27^{16} \equiv 31^2 = 961 \mod 125 \equiv 86\) - \(27^{32} \equiv 86^2 = 7396 \mod 125 \equiv 21\) Теперь мы можем собрать всё вместе (используем разложение по степеням): \[ 27^{71} = 27^{64} \cdot 27^{4} \cdot 27^{2} \cdot 27^{1} \equiv 21 \cdot 66 \cdot 104 \cdot 27 \mod 125 \] Для упрощения можно поэтапно считать: - \(21 \cdot 66 \equiv 1386 \equiv 11 \mod 125\) - \(11 \cdot 104 \equiv 1144 \equiv 19 \mod 125\) - \(19 \cdot 27 \equiv 513 \equiv 13 \mod 125\) Теперь у нас есть два результата: \[ 652^{9371} \equiv 0 \mod 8 \] \[ 652^{9371} \equiv 13 \mod 125 \] Теперь применим теорему китайских остатков: Найдем такое число \(x\), что: \[ x \equiv 0 \mod 8 \] \[ x \equiv 13 \mod 125 \] Предположим, что \(x = 125k + 13\), подставим в первое уравнение: \[ 125k + 13 \equiv 0 \mod 8 \] Или: \[ 125 \equiv 5 \mod 8 \implies 5k + 5 \equiv 0 \mod 8 \implies 5(k + 1) \equiv 0 \mod 8 \] Поскольку 5 и 8 взаимно просты, \(k + 1 \equiv 0 \mod 8\) или \(k \equiv 7 \mod 8\). Пусть \(k = 8m + 7\) для некоторого целого \(m\): \[ x = 125(8m + 7) + 13 = 1000m + 875 + 13 = 1000m + 888 \] Таким образом, \(x \equiv 888 \mod 1000\). Итак, три последних цифры числа \(4652^{9371}\) равны: \[ \boxed{888} \]