Помогите, пожалуйста, решить задачу: Вычислить без калькулятора 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.