Помогите, пожалуйста, решить задачу: Вычислить без калькулятора 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! Где-то я вероятно ошибаюсь? (IMG:style_emoticons/default/huh.gif)

Я могу ошибаться, но по-моему, здесь дело в следующем.
61 mod 56 = 5.
Поэтому
61^70(mod 56) = 5^70(mod 56) = (125^23 * 5)(mod 56) = (5 * 125^23(mod 56))(mod 56).
Т.к. 125(mod 56) = 13, то
(5 * 125^23(mod 56))(mod 56) = (5 * 13^23(mod 56))(mod 56) = (5 * (13*169^11(mod 56)))(mod 56) = (5 * 13*(169^11(mod 56)))(mod 56) = (65*(169^11(mod 56)))(mod 56).
Т.к. 169(mod 56) = 1, то
(65*(169^11(mod 56)))(mod 56) = (65*1)(mod 56) = 9.

Ответ верный. Будет короче, если воспользоваться теоремой Эйлера:
При 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)