теория-чисел — Как найти остаток от деления числа в степени?
Найдите остаток от деления чисел:
а) 23 в степени 277 на 9;
б) 17 в степени 332 на 10.
Нужно подробное решение. Заранее большое спасибо!
задан 15 Дек ’14 21:23
1 ответ
Нужно воспользоваться свойствами сравнений и теоремой Эйлера. В первом примере 23 заменяем на 5 (остаток от деления на 9), и используем то, что $%\varphi(9)=6$%. Поскольку 5 взаимно просто с 9, из теоремы Эйлера следует, что $%5^6\equiv1\pmod9$%. Ввиду того, что $%277=6\cdot49+1$%, получается $%5^<277>\equiv(5^6)^<49>\cdot5\equiv5\pmod9$%, то есть остаток равен 5.
Во втором случае $%\varphi(10)=4$%, поэтому показатель степени делим с остатком на 4. Получается 0, поэтому остаток равен $%7^0=1$%. Здесь можно рассуждать даже проще, следя за последней цифрой произведения: ясно, что $%7^4$% оканчивается на 1, и при возведении в любую степень последняя цифра остаётся равна 1.