Posted by Joel on November 03, 2002 at 10:11:32:
I'm trying to prove that 2^2^n + 3^2^n + 5^2^n is divisible by 19 for all positive integers n (by induction).
Easy enough to show this is true for n=1 and n=2, etc., as a basis step.
But for the inductive step, I get
f(n+1) = 2^2^(n+1) + 3^2^(n+1) + 5^2^(n+1)
= (2^2^n)^2 + (3^2^n)^2 + (5^2^n)^2
or (2^2)^(2^n) + (3^2)^(2^n) + (5^2)^(2^n)
= 4^2^n + 9^2^n + 25^2^n
---------------------------------------
similarly, for n+2:
f(n+2) = 2^2^(n+2) + 3^2^(n+2) + 5^2^(n+2)
= (2^2^n)^4 + (3^2^n)^4 + (5^2^n)^4
or (2^4)^(2^n) + (3^4)^(2^n) + (5^4)^(2^n)
= 16^2^n + 81^2^n + 625^2^n
I can't find a multiple or power of (2^2^n + 3^2^n + 5^2^n), or a combination of that plus some other multiple of 19, in either of those expressions.
I found this "hint" for a solution on another website:
16^2^n + 81^2^n + 625^2^n = (19-3)^2^n + (19*4+5)^2^n + (19*33-2)^2^n , also stating that "using the binomial theorem", f(n+2) can be shown to be = f(n) + m(19)
How does splitting up the coefficients in that strange manner (19-3), (19*4+5) and (19*33-2) show that the result is divisible by 19?