Выбор модуля для доказательства делимости / простоты / степени

Подсказка 1

Явно найти делитель числа — вероятно, самый простой способ доказать, что оно не является простым. Еще проще будет проверять делимость на число, не зависящее от n. Найдите значения при первых нескольких n, это может найти постоянные делители (возможно, с дополнительным условием на n), если они зависят от n.

Подсказка 2

8^n растет довольно быстро, тем не менее значения выражения при n = 1, 2, 3 посчитать несложно, они равны соответственно 169, 1233, 9745. Проверять делимость по большому модулю затруднительно, поэтому стоит начать с минимальных делителей - соответственно 13, 3, 5. Например, чему должно удовлетворять число n, чтобы 19*8^n+17 было кратно 3 (заметьте, что n=2 должно удовлетворять этому условию)?

Подсказка 3

Покажите, что при всех четных n число кратно 3. С чем должно быть сравнимо 8^n при этом условии?

Подсказка 4

С 1. Вообще доказывать сравнимость с 1 числа вида a^b довольно просто - для каждого числа a взаимнопростого с числом m существует b такое, что a^b сравнимо с 1 по модулю m, но тогда для любого k число a^{kb} так же сравнимо с 1. Так, 8^2=64 сравнимо с 1 по модулю. Какие условия можно наложить на число n, чтобы оно делилось на 13 и 5?

Подсказка 5

Мы уже доказали утверждения задачи для всех четных n. Доказать делимость на некоторое фиксированное число для любого нечетного n будет трудно, ведь это неправда - числа 169, 9745 взаимнопросты. Остается надеяться, что это можно сделать, для всех n сравнимых с фиксированным остатком по модулю 4.

Подсказка 6

Таким образом, осталось показать, что выражение делится на 13 при всех n=4k+1 и на 5 при всех n=4k+3.