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

найдите остаток от деления 3 в 1989 степени на 7.

Фатима Нашемукова Знаток (394), на голосовании 11 лет назад
Голосование за лучший ответ
Globe Просветленный (24832) 11 лет назад
Если вспомнить малую теорему Ферма, то окажется, что 3^6 = 1 (mod 7), то есть,
3^6 = (7x+1).

В то же время:
1989 = 6*331+3

Получаем:
3^1989 = 3^(6*331+3) = 27 * (3^6)^331 = 27 * (7x+1)^331

Ясно, что по формуле бинома Ньютона выражение (7x+1)^331 после раскрытия скобок превратится во что-то вида 7y + 1. Следовательно:
3^1989 = 27 * (7y + 1) = 7z + 27 = 7(z+3) + 6.

Получаем ответ: 6
Похожие вопросы