Областная олимпиада по математике, 2021 год, 11 класс

Покажите, что существует бесконечно много натуральных чисел $n$ таких, что $\dfrac{{{8^n} - 1}}{{{n^2} + n + 1}}$ также является натуральным числом.

Комментарий/решение

Рассмотрим число $n=2^{2^k}$. Так как если $m$ делится на $l$, то $2^m-1$ делится на $2^l-1$, тогда:

$8^n-1=2^{3n}-1$ делится на $2^{3*2^k}-1$ делится на $2^{2*2^k}+2^{2^k}+1=n^2+n+1$, что и требовалось доказать.

Перепишем данную дробь в виде $\frac{(2^n-1)((2^n)^2 + 2^n + 1)}{n^2+n+1}$.

Заменим $(2^n)^2 + 2^n + 1$ и $n^2+n+1$, как значения $f(x) = x^2 + x +1$.

Тогда исходное выражение примет вид $\frac{(2^n-1)f(2^n)}{f(n)}$

Заметим, что $f(n^2) = n^4 + n^2 + 1 = (n^2+n+1)(n^2-n+1) \Leftrightarrow f(n) \vert f(n^2)$

Отсюда по индукции легко доказать, что $ f(n) \vert f(n^{2^k}) \, \forall n,k \in \mathbb{N} \, (1)$

Переформулируем задачу: докажем, что существует бесконечно много натуральных $n$ таких, что $f(n) \vert f(2^n)$

Предположим, что $n^{2^k} = 2^n$, отсюда можно понять, что $n$ - степень двойки в какой-то степени, поэтому пусть $n = 2^{2^x}$

$n^{2^k} = (2^{2^x})^{2^k} \Leftrightarrow 2^{2^{k+x}} = 2^n = 2^{2^{2^x}} \Leftrightarrow 2^{k+x} = 2^{2^x} \Leftrightarrow k + x = 2^x \Leftrightarrow k = 2^x - x \, (\forall x \in \mathbb{N})$

Подставим новые значения $k$ и $n$ в $(1)$:

$f(n) \vert f(n^{2^k}) = f((2^{2^x})^{2^x-1}) = f(2^{2^x * \frac{2^{2^x}}{2^x}}) = f(2^{2^{2^x}}) = f(2^n)$, а поскольку таких $x$ из которых и исходят значения $n$ и $k$ бесконечно много, то и самих таких $n$ (и $k$) бесконечно много, что и требовалось доказать.