Разделы 
Дополнительно
Задача по математике - 1987
2019-01-22 
Докажите, что существует бесконечно много натуральных $n$, для которых числитель несократимой дроби, равной $1+ \frac {1}{2}+\cdots+ \frac {1}{n}$, не является степенью простого числа с натуральным показателем.
Решение:
Положим
$S(n) = \sum_{i=1}^{n}\frac{1}{i} = \frac{A(n)}{B(n)}$
где $A(n)$ и $B(n)$ взаимно просты.
Заметим, что $B(n) > n/2$ (действительно, наибольшая степень двойки, не превосходящая $n$, является делителем ровно одного из чисел $1, 2, \cdots, n$ и потому является делителем знаменателя суммы $S(n)$).
Предположим, что при всех $n \geq n_0$ число $A(n)$ является степенью простого. Пусть $p > n_0 + 5$ - простое число. Тогда $A(p - 1) \vdots p$ (слагаемые суммы $S(p - 1)$ разбиваются на пары, для каждой из которых числитель суммы делится на $p$). Следовательно, $A(p - 1) = p^k, k \in \mathbb{N}$.
Далее, докажем, что числитель $A(p^n - 1)$ также кратенp (и, стало быть, является степенью $p$) при всех натуральных $n$.
Проведем индукцию по $n$.
База доказана.
Переход от $n - 1$ к $n$. Имеем: $S(p^n - 1) = S(p^{n - 1} - 1)/p + S^{\prime}$, где $S^{\prime} = \sum_{d \leq p^n - 1, p/d}^{ }\frac{1}{d}$ (первое слагаемое как раз равно сумме слагаемых со знаменателями, делящимися на $p$). Сумма $S^{\prime}$ разбивается на несколько (а именно, $р^{n-1}$) сумм вида $\sum_{i=1}^{p-1}\frac{1}{pl+i}, l = 0, 1, \cdots, р^{n-1} - 1$. Каждая из них имеет числитель, делящийся на $p$, что устанавливается как и для $S(p - 1)$. Осталось убедиться, что числитель дроби $S(p^{n-1} - 1)/p$ делится на $p$. Действительно, $A(p^{n-1} - 1) = p^s$ в силу индуктивного предположения, причем $s > 1$ (вспомним, что $B(p^{n-1} - 1) \geq p^{n-1}/2 \geq p/2,$ а $S(p^{n-1} - 1) \geq S(n_0 + 4) \geq S(4) > 2)$.
Положим $H_p(n)$: $= S(p^n - p)- S(p^n - 1) = \sum_{i=1}^{p-1}\frac{1}{-p^n+i}$. Если $n > k$, то числитель дроби $Н_p(n)$ делится на $p^k$, но не на $p^{k+1}$ (ибо $Н_p(n) - S(p - 1)$ - дробь, числитель которой делится на $p^n$). Отсюда получаем, что оба числителя $A(p^n - 1)$ и $A(p^n - p)$ делятся на $p$, но один из них не делится на $p^{k+1}$. Значит, одна из дробей $S(p^n - 1) и S(p^n - p)$ не превосходит $\frac{2p^k}{p^n - p} < 1$ при $n = k + 2$ - противоречие.
Докажите, что существует бесконечно много натуральных $n$, для которых числитель несократимой дроби, равной $1+ \frac {1}{2}+\cdots+ \frac {1}{n}$, не является степенью простого числа с натуральным показателем.
Решение:
Положим
$S(n) = \sum_{i=1}^{n}\frac{1}{i} = \frac{A(n)}{B(n)}$
где $A(n)$ и $B(n)$ взаимно просты.
Заметим, что $B(n) > n/2$ (действительно, наибольшая степень двойки, не превосходящая $n$, является делителем ровно одного из чисел $1, 2, \cdots, n$ и потому является делителем знаменателя суммы $S(n)$).
Предположим, что при всех $n \geq n_0$ число $A(n)$ является степенью простого. Пусть $p > n_0 + 5$ - простое число. Тогда $A(p - 1) \vdots p$ (слагаемые суммы $S(p - 1)$ разбиваются на пары, для каждой из которых числитель суммы делится на $p$). Следовательно, $A(p - 1) = p^k, k \in \mathbb{N}$.
Далее, докажем, что числитель $A(p^n - 1)$ также кратенp (и, стало быть, является степенью $p$) при всех натуральных $n$.
Проведем индукцию по $n$.
База доказана.
Переход от $n - 1$ к $n$. Имеем: $S(p^n - 1) = S(p^{n - 1} - 1)/p + S^{\prime}$, где $S^{\prime} = \sum_{d \leq p^n - 1, p/d}^{ }\frac{1}{d}$ (первое слагаемое как раз равно сумме слагаемых со знаменателями, делящимися на $p$). Сумма $S^{\prime}$ разбивается на несколько (а именно, $р^{n-1}$) сумм вида $\sum_{i=1}^{p-1}\frac{1}{pl+i}, l = 0, 1, \cdots, р^{n-1} - 1$. Каждая из них имеет числитель, делящийся на $p$, что устанавливается как и для $S(p - 1)$. Осталось убедиться, что числитель дроби $S(p^{n-1} - 1)/p$ делится на $p$. Действительно, $A(p^{n-1} - 1) = p^s$ в силу индуктивного предположения, причем $s > 1$ (вспомним, что $B(p^{n-1} - 1) \geq p^{n-1}/2 \geq p/2,$ а $S(p^{n-1} - 1) \geq S(n_0 + 4) \geq S(4) > 2)$.
Положим $H_p(n)$: $= S(p^n - p)- S(p^n - 1) = \sum_{i=1}^{p-1}\frac{1}{-p^n+i}$. Если $n > k$, то числитель дроби $Н_p(n)$ делится на $p^k$, но не на $p^{k+1}$ (ибо $Н_p(n) - S(p - 1)$ - дробь, числитель которой делится на $p^n$). Отсюда получаем, что оба числителя $A(p^n - 1)$ и $A(p^n - p)$ делятся на $p$, но один из них не делится на $p^{k+1}$. Значит, одна из дробей $S(p^n - 1) и S(p^n - p)$ не превосходит $\frac{2p^k}{p^n - p} < 1$ при $n = k + 2$ - противоречие.
