Доказать: 3^(105) + 4^(105) делится на 181

181 — простое число, поэтому мы не можем упростить себе задачу, разложив его на множители.
Введем операцию деления по модулю — mod.
Выражение a mod b равно остатку от деления a на b.
Пример:
10 mod 3 = 1
11 mod 3 = 2
12 mod 3 = 0

Число a делится на b (без остатка), если a mod b = 0.

У деления по модулю есть несколько важных свойств:

1) При умножении делимого умножается и его остаток.
Если a mod c = d, то (a • b) mod c = (d • b) mod c

Пример:
20 mod 9 = 2
20 • 2 mod 9 = (2 • 2) mod 9 = 4 mod 9 = 4
Сравните: 40 mod 9 = 4

Другой пример:
20 mod 11 = 9
20 • 2 mod 11 = (9 • 2) mod 11 = 18 mod 11 = 7
Сравните: 40 mod 11 = 7

2) Результат деления суммы чисел по модулю равен сумме остатков от их деления по отдельности.
Если
a mod b = c
d mod b = e
тогда (a + d) mod b = (c + e) mod b

Пример:
20 mod 11 = 9
30 mod 11 = 8
(20 + 30) mod 11 = (9 + 8) mod 11 = 17 mod 11 = 6
Сравните: 50 mod 11 = 6

Помня об этих двух свойствах, найдем значение
(3^105 + 4^105) mod 181 = ?

Начнем с тройки.
3 mod 181 = 3
3^2 mod 181 = 9
3^3 mod 181 = 27
3^4 mod 181 = 81
3^5 mod 181 = 243 mod 181 = 62
3^6 mod 181 = (62 • 3) mod 181 = 186 mod 181 = 5
3^7 mod 181 = 5 • 3 mod 181 = 15 mod 181 = 15
3^8 mod 181 = 45
3^9 mod 181 = 135
3^10 mod 181 = 405 mod 181 = 43
3^11 mod 181 = (43 • 3) mod 181 = 129
3^12 mod 181 = 387 mod 181 = 25
3^13 mod 181 = 75
3^14 mod 181 = 225 mod 181 = 44
3^15 mod 181 = (44 • 3) mod 181 = 132
3^16 mod 181 = (132 • 3) mod 181 = 396 mod 181 = 34
3^17 mod 181 = (34 • 3) mod 181 = 102
3^18 mod 181 = (102 • 3) mod 181 = 306 mod 181 = 125

Вы можете заметить третье важное свойство, взглянув на эти результаты:
3^6 mod 181 = 5
3^12 mod 181 = 25 = (3^6 • 3^6) mod 181 = (5 • 5) mod 181 = 25
3^18 mod 181 = 125 = (3^12 • 3^6) mod 181 = (25 • 5) mod 181 = 25

Произведение чисел, деленное по модулю, равно произведению остатков от деления отдельных множителей.

Аналогичным образом мы можем рассчитать
3^24 mod 181 = (3^18 • 3^6) mod 181 = (125 • 5) mod 181 = 625 mod 181 = 82
3^30 mod 181 = (82 • 5) mod 181 = 410 mod 181 = 48
3^36 mod 181 = (48 • 5) mod 181 = 240 mod 181 = 59
3^42 mod 181 = (59 • 5) mod 181 = 295 mod 181 = 114
3^48 mod 181 = (114 • 5) mod 181 = 570 mod 181 = 27
3^96 mod 181 = (27 • 27) mod 181 = (3^3 • 3^3) mod 181 = 3^6 mod 181 = 5

Наконец:
3^105 mod 181 = (3^96 • 3^9) mod 181 = (5 • 135) mod 181 = 675 mod 181 =
= 132

Теперь четверки.

4 mod 181 = 4
4^2 mod 181 = 16
4^3 mod 181 = 64
4^4 mod 181 = 256 mod 181 = 75
4^5 mod 181 = (75 • 4) mod 181 = 300 mod 181 = 119
4^6 mod 181 = (119 • 4) mod 181 = 476 mod 181 = 114
4^7 mod 181 = (114 • 4) mod 181 = 456 mod 181 = 94
4^8 mod 181 = (94 • 4) mod 181 = 376 mod 181 = 14
4^9 mod 181 = (14 • 4) mod 181 = 56 mod 181 = 56

Мы нашли маленький остаток — 14, с ним считать легко.
Далее:
4^16 mod 181 = (4^8 • 4^8) mod 181 = (14 • 14) mod 181 = 196 mod 181 = 15
4^32 mod 181 = (4^16 • 4^16) mod 181 = (15 • 15) mod 181 =
= 225 mod 181 = 44
4^48 mod 181 = (4^32 • 4^16) mod 181 = (44 • 15) mod 181 =
= 660 mod 181 = 117
4^64 mod 181 = (117 • 15) mod 181 = 1755 mod 181 = 126
4^80 mod 181 = (126 • 15) mod 181 = 1890 mod 181 = 80
4^96 mod 181 = (80 • 15) mod 181 = 1200 mod 181 = 114

Наконец:
4^105 mod 181 = (4^96 • 4^9) mod 181 = (114 • 56) mod 181 =
= 6384 mod 181 = 49

Итак:
3^105 mod 181 = 132
4^105 mod 181 = 49

Тогда (3^105 + 4^105) mod 181 = (132 + 49) mod 181 = 181 mod 181 = 0,
что и требовалось доказать.

Но я подозреваю, что есть более простой способ.

3^5 + 4^5 = 1267 = 181 * 7
тогда
3^105 + 4^105 = (3^5)^21 + (4^5)^21 = (3^5 + 4^5) * X, где X - некоторое целое число = 181 * 7X

см. вики, статья "Формулы сокращённого умножения многочленов":