Докажите, что при любом натуральном n число 3^3n+2+5*2^3n+1 кратно 19.

Пусть n = 1, тогда:

Так как при некотором n это число действительно кратно 19, то пусть некоторое n = k, при котором это число кратно, тогда исследуем это число при n = k+1, получим:

Первое слагаемое делится на 19, так как мы предположили, что при n = k это выражение делится на 19, а второе слагаемое делится на 19 согласно основной теоремы арифметики.

3³ⁿ⁺² + 5×2³ⁿ⁺¹ = 9×27ⁿ + 10×8ⁿ ≡ 9×8ⁿ + 10×8ⁿ = 19×8ⁿ ≡ 0×8ⁿ = 0 (mod 19). ⇒ ∀n ∈ ℕ: 3³ⁿ⁺² + 5×2³ⁿ⁺¹ кратно 19.

Q.E.D.