Домашние задания: Математика

Найти остаток от деления числа (26!)^26 + (27!)^27 на 29.

Айнур Аскарбекова
Айнур Аскарбекова
96 935
(26!)^26 + (27!)^27 делим на 29.
Давай оценим остатки каждого слагаемого при делении на 29.
1) 26! = 6!*(7*8)(9*10)(11*12)(13*14)(15*16)(17*18)(19*20)(21*22)(23*24)(25*26) =
= 720*56*90*132*182*240*306*380*462*552*650 = (29*24+24)(29+27)(29*3+3)(29*4+16)*
*(29*6+8)(29*8+8)(29*10+16)(29*13+3)(29*15+27)(29*19+1)(29*22+12)
Остатки: 24*27*3*16*8*8*16*3*27*1*12 = 72*27^2*16^2*64*36 =
= 72*729*256*64*36 = (29*2+14)(29*25+4)(29*8+24)(29*2+6)(29+7)
Остатки: 14*4*24*6*7 = 98*24^2 = 98*576 = (29*3+11)(29*19+25)
Остатки: 11*25 = 275 = 29*9+14
Значит, 26! при делении на 29 дает остаток 14.

2) (26!)^26 при делении на 29 имеет такой же остаток, как и 14^26.
14^26 = (14^2)^13 = 196^13 = (29*6+22)^13.
Остатки: 22^13 = 22*22^12 = 22*(22^2)^6 = 22*484^6 = 22*(29*16+20)^6
Остатки: 22*20^6 = 22*(20^2)^3 = 22*400^3 = 22*(29*13+23)^3
Остатки: 22*23^3 = 22*23*23^2 = 506*529 = (29*17+13)(29*18+7)
Остатки: 13*7 = 91 = 29*3 + 4
Значит: (26!)^26 при делении на 29 дает остаток: 4.

3) 27! = 26!*27 = (29*9+14)*27 = 29*27*9 + 14*27 = 29*27*9 + 378 = 29*(27*9+13) + 1
Значит, 27! при делении на 29 дает остаток 1.
(27!)^27 при делении на 29 тоже дает остаток 1.

4) Получаем:
(26!)^26 + (27!)^27 при делении на 29 дает остаток:
4 + 1 = 5

Все расчёты проведены в уме, без калькулятора!
Интересно, существует ли более простой способ это узнать?

Ответ: 5
Бобур Эргашов
Бобур Эргашов
77 562
Лучший ответ
Айнур Аскарбекова Честь и хвала за усердие! Гораздо более простой способ описал Тадасана. Надо знать теорему Вильсона и малую теорему Ферма.
5
Аманжан Ерденбатқызы
Аманжан Ерденбатқызы
66 572
Евгений Рыбенок Так скучно, это и https://www.wolframalpha.com умеет. Вбить туда просто
(26!)^26 + (27!)^27 mod 29
Аманжан Ерденбатқызы Такими не очень то простыми задачами я могу тут всех завалить, но не хочу. И ещё непонятно - а при чём тут вообще домашние задания ?
Решим уравннение x^2 = 1 в поле вычетов по простому модую Zp. Один корень есть - это 1.
x^2 - 1^2 = 0 => (x - 1)(x + 1) = 0 => x = +/-1, т.е. среди ненулевых элементов поля Zp со своим обратным элементом по умножению совпадают только -1 и 1
Все ненулевые элементы Zp перемножим. каждый элемент (кроме 1 и -1) сгруппируем с обратным, получим -1.
Это утверждение.- часть теоремы Вильсона, а заодно оно и намекает на теоремку о произведении всех элементов конечной абелевой группы.
Ну а дальше все просто.

26! * 27*28 = -1 mod 29

=> в поле Z29:
27! = -1/28 = -1/-1 = 1
26! = 27!/27 = 1/27 = 1/(-2) = -1/2

(-1/2)^26 = (1/2)^26 = по малой теореме Ферма = 2^2 = 4

И имеем ответ 4 + 1 = 5.
Елена Вал
Елена Вал
34 449
Бобур Эргашов Ну да, ваш способ короче, но это же надо знать всё это:
понятие о поле вычетов, о конечной абелевой группе,
теорему Вильсона, малую теорему Ферма.
Всё это в школе не проходят, поэтому школьникам непонятно.

Похожие вопросы