Problem 1115

The following divisibility theorems are known:

If $n$ is a natural number, then

$$\begin{gathered} a^{n}-b^{n} \text { is divisible by }(a-b), \\ a^{n}+b^{n} \text { is divisible by }(a+b) \text { if } n \text { is odd. } \end{gathered}$$

Using these theorems, we can prove the statement of our problem in several ways.

I. Solution: Let the given expression be denoted by $F(n)$,

a) If $n$ is even, i.e., $n=2 k$ (where $k=1,2,3 \ldots$), then write $F(n)$ in the following form

$$F(2 k)=\left(5^{2 k}-1\right)+2\left(3^{2 k-1}+1\right)$$

The first term on the right-hand side is divisible by $\left(5^{2}-1^{2}\right)=24=3 \cdot 8$ according to (1), and the factor in parentheses in the second term is divisible by $3+1=4$ according to (2), so the second term is divisible by $2 \cdot 4=8$.

b) If $n$ is odd, i.e., $n=2 k+1$ (where $k=0,1,2, \ldots$), then for $k=0$, $F(1)=5+2+1=8$, and in all other cases

$$F(2 k+1)=5^{2 k+1}-5+2 \cdot 3^{2 k}+6=5\left(5^{2 k}-1\right)+6\left(3^{2 k-1}+1\right)$$

In this case, not only is the first term divisible by 24, but the second term is also divisible by $6 \cdot 4=24$. Therefore, for odd $n$ greater than 1, the expression is not only divisible by 8, but also by 24.

II. Solution: a) If $n=2 k$ (where $k=1,2,3, \ldots$), then $F(n)$ can also be written as:

$$\begin{aligned} & F(2 k)=5 \cdot 5^{2 k-1}+5 \cdot 3^{2 k-1}-3 \cdot 3^{2 k-1}+1= \\ & =5\left(5^{2 k-1}+3^{2 k-1}\right)-\left(9^{k}-1\right) \end{aligned}$$

The first term on the right-hand side is divisible by $5+3=8$ according to (2), and the second term is divisible by $9-1=8$ according to (1).

b) If $n=2 k+1$ (where $k=0,1,2, \ldots$), then

$$F(2 k+1)=5^{2 k+1}+(3-1) 3^{2 k}+1=\left(5^{2 k+1}+3^{2 k+1}\right)-\left(9^{k}-1\right)$$

from which it follows, similarly to the previous case, that $F(n)$ is divisible by 8.

Note: Many contestants used the polynomial representation of the power of a binomial, but as we have seen, the divisibility theorems (1) and (2) that require fewer prerequisites are sufficient. These can even be omitted if complete induction is used.

III. Solution: For $n=1$, the statement to be proved is true, because $F(1)=8$.

Assume that $F(k)$ is divisible by 8, then it is sufficient to prove that $F(k+1)-F(k)$ is also divisible by 8.

$$\begin{aligned} & F(k+1)-F(k)=\left(5^{k+1}+2 \cdot 3^{k}+1\right)-\left(5^{k}+2 \cdot 3^{k-1}+1\right)= \\ & =5 \cdot 5^{k}+6 \cdot 3^{k-1}+1-5^{k}-2 \cdot 3^{k-1}-1=4\left(5^{k-1}+3^{k-1}\right) \end{aligned}$$

The expression in parentheses, being the sum of two odd numbers, is an even number, and thus $F(k+1)-F(k)$ is divisible by $4 \cdot 2=8$.