Докажите что:

1) 17^n - 1 кратно 16

2) 23^2n+1 + 1 кратно 24

3) 13^2n+1 + 1 кратно 14

Доказательство проведем индукцией по n.

1) 17ⁿ - 1 кратно 16. При n = 1 кратность подтверждается: 17 - 1 = 16. Пусть кратность 16-ти сохраняется при произвольном n. Докажем, что она подтверждается и при n + 1. 17ⁿ⁺¹ - 1 = 17*17ⁿ + 1. Составим разность: 17ⁿ⁺¹ - 1 - (17ⁿ - 1) = 17ⁿ⁺¹ - 1 - 17ⁿ + 1 = 17*17ⁿ - 17ⁿ = 17ⁿ (17 - 1) = 16*17ⁿ. Получили, что разность 17ⁿ⁺¹ - 1 - (17ⁿ - 1) кратна 16. Т. к. слагаемое 17ⁿ - 1 также кратно 16 по предположению индукции, то и слагаемое 17ⁿ⁺¹ - 1 кратно 16, следовательно кратность доказана.

2) 23²ⁿ⁺¹ + 1 кратно 24. При n = 1 кратность подтверждается: 23³ + 1 = 12167 + 1 = 12168 = 24*507. Полагая, что имеет место кратность 23²ⁿ⁺¹ + 1 двадцати четырем, покажем, что и при n + 1 кратность подтверждается. 23² ⁽ⁿ⁺¹⁾ ⁺¹ + 1 = 23²ⁿ⁺³ + 1. Составляем разность 23²ⁿ⁺³ + 1 - (23²ⁿ⁺¹ + 1) = 23²ⁿ⁺³ + 1 - 23²ⁿ⁺¹ - 1 = 23²ⁿ⁺¹*23² - 23²ⁿ⁺¹ = 23²ⁿ⁺¹ (23² - 1) = 23²ⁿ⁺¹ (23 - 1) (23 + 1) = 22*24*23²ⁿ⁺¹. Видим, что эта разность кратна 24. Т. к. слагаемое 23²ⁿ⁺¹ + 1 кратно 24 по предположению индукции, то и 23²ⁿ⁺³ + 1 кратно 24, тем самым кратность доказана.

3) 13²ⁿ⁺¹ + 1 кратно 14. Действуя как в предыдущем пункте, получаем: при n = 1, 13³ + 1 = 2197 + 1 = 2198 = 14*157. Полагаем, что 13²ⁿ⁺¹ + 1 кратно 14 и доказываем кратность четырнадцати при n + 1. 13² ⁽ⁿ⁺¹⁾ ⁺¹ + 1 = 13²ⁿ⁺³ + 1. Составляем разность 13²ⁿ⁺³ + 1 - (13²ⁿ⁺¹ + 1) = 13²ⁿ⁺³ - 13²ⁿ⁺¹ = 13²*13²ⁿ⁺¹ - 13²ⁿ⁺¹ = 13²ⁿ⁺¹ (13² - 1) = 13²ⁿ⁺¹ (13 - 1) (13 + 1) = 12*14*13²ⁿ⁺¹. Разность кратна 14, т. к. по предположению 13²ⁿ⁺¹ + 1 кратно 14, то и 13²ⁿ⁺³ + 1 кратно 14. Кратность доказана.