Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Найти остаток от деления 6^394 на 29

Александра Жиренкина Z Ученик (81), на голосовании 11 месяцев назад
Найти остаток от деления 6^394 на 29
Голосование за лучший ответ
Раз Кудрявый Оракул (51870) 1 год назад
56
Александра Жиренкина ZУченик (81) 1 год назад
Можно расписать решение, пожалуйста
Леонид Зайцев Мыслитель (6372) 1 год назад
Согласно малой теореме Ферма 6^28 есть число вида 29N+1. Поскольку 6^394 = 6^(28*14+2) = 36*(6^28)^14 = 36*(29N+1)^14 = (29+7)*(29M+1) = 29K+7, при делении 6^394 на 29 остаток = 7.
Леонид ЗайцевМыслитель (6372) 1 год назад
(Как можно быстро вспомнить малую теорему Ферма.)
Делимость 2^p - 2 на некоторое (большое) простое p
получается при помощи биномиальной теоремы:
2^p = (1+1)^p = 1^p + [сумма целых, содержащих множитель p] + 1.
Из делимости 2^p - 2 на p выводится делимость 3^p - 3 на p, так как
3^p = (2+1)^p = 2^p + [сумма целых, содержащих множитель p] + 1,
и хорошо видно, что 3^p - 3 = (2^p - 2) + [...] делится на p.
Сделанное для 2 и 3 можно повторить для 4,5,6,7,etc.,p-1.
Таким образом a^p - a, равное a*[a^(p-1)-1] , делится на p.
Но делимости а на р нет, - потому a^(p-1)-1 делится на р.
Похожие вопросы