Помогите, пожалуйста, решить задачу: Вычислить без калькулятора 61^70(mod 56), используя китайскую теорему об остатках.
решаю:
56=8*7
p(8)=7 p(7)=6
61^70(mod 7) (так как 70 = 11*6 + 4, то это 61^4=61)
61^70(mod 8) (так как 70 делится на 8-1, это 1)
Используя кит. т. об ост. на промежутке от 0 до 55 должен найтись x такой, что:
x=61(mod 7) х-61=7t
x=1(mod 8) x-1=8t
но х получается = 481! Где-то я вероятно ошибаюсь?
Ответ верный. Будет короче, если воспользоваться теоремой Эйлера:
При x взаимно простом с m справедливо сравнение x^ф(m)=1 (mod m)
Здесь ф - функция Эйлера.
Так как 61=5 (mod 56) и ф(56)=24, то основание 61 можно заменить на 5, а из показателя убрать два раза по 24:
61^70=5^22 (mod 56). Домножив на 25, получим 25*61^70=5^24=1 (mod 56).
Остается убрать множитель 25 из сравнения 25*61^70=1 (mod 56)
Ищем обратный для 25 по модулю 56:
5*11=55=-1 (mod 56), возводя в квадрат получаем
1=25*121=25*(112+9)=25*9 (mod 56). Домножая 25*61^70=1 (mod 56) на 9, получаем 9*25*61^70=9 (mod 56).
Другой вариант - рассмотреть сравнение по модулям 7 и 8, числа поменьше будут. Получится x=2 (mod 7) и x=1 (mod 8).
Отсюда, если сразу не видно, то по китайской теореме об остатках получится x=9 (mod 56)
Русская версия Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)