Разделы 
Дополнительно
Задача по математике - 3054
2019-05-06 
Согласно теореме Эйлера разность $2^k - 1$, где $k = 5^n - 5^{n-1}$, делится на $5^n$ (см. задачу 3053, в частности, примечание к этой задаче). Доказать, что ни при каком $k$, меньшем чем $5^n - 5^{n-1}$, разность $2^k- 1$ не делится на $5^n$.
Решение:
Доказательство проведем методом математической индукции. Прежде всего очевидно, что при $n = 1$ предложение задачи справедливо: $2^1 - 1 = 1, 2^2- 1 = 3$ и $2^3- 1 = 7$ не делятся на 5. Докажем еще это предложение для $n = 2$. Пусть $2^к$ есть наименьшая степень числа 2, дающая при делении на $5^2 = 25$ остаток 1 (т. е. такая, что $2^k - 1$ делится на 25); предположим, что $k < 5^2 - 5 = 25 - 5 = 20$. Если 20 не делится на $к$, так что $20 = q^k + r$, где $r < k$, то мы будем иметь:
$2^{20} - 1 = 2^{qk+r} - 1 = 2^r(2^qk - 1) + (2^r - 1)$.
Но $2^{20} - 1$ делится на 25, в силу теоремы Эйлера, а $2^{qk} - 1 = (2^k)^q- 1^q$ делится на $2^k - 1$, т. е., в силу нашего предположения, тоже делится на 25; следовательно, и $2^r - 1$, делится на 25, что противоречит тому, что $к$ есть наименьшее число, для которого $2^к - 1$ делится на 25, Итак, $k$ должно быть делителем числа 20, т. е. может равняться только 2, 4, 5 или 10. Но $2^2- 1 = 3$, $2^5 - 1 = 31$ и $2^{10} - 1 = 1023$ не делятся даже на 5, а $2^4- 1 = 15$ делится на 5, но не делится на 25. Значит, действительно и для $n = 2$ предложение задачи справедливо.
Предположим теперь, что для какого-то $n$ предложение задачи справедливо, а для значения $n+1$ оно неверно: наименьшее $к$, такое, что $2^k - 1$ делится на $5^{n+1}$, меньше чем $5^{n+1} - 5^n = 4 \cdot 5^n$. В точности, как выше (для $n = 2$), доказывается, что $к$ должно являться делителем числа $4 \cdot 5^n$. С другой стороны, аналогично доказывается, что число $5^n - 5^{n-1} = 4 \cdot 5^{n-1}$ должно являться делителем числа $к$: если бы было $k = q \cdot 4 \cdot 5^{n-1} + r$, где $r < 4 \cdot 5^{n-1}$, то число $5^r - 1$ делилось бы на $5^n$, что противоречит предположению о справедливости утверждения задачи для числа $n$. Таким образом, для $к$ остается единственное возможное значение, а именно: $k = 4 \cdot 5^{n-1}$.
Так как число $2^{5^{n-1}} - 5^{n-2} - 1 = 2^{4 \cdot 5^{n-2} - 1}$ делится на $5^{n-1}$ (в силу теоремы Эйлера) и не делится на $5^n$ (иначе предложение задачи не было бы справедливо для числа $n$), то $2^{4 \cdot 5^{n-2}} = q \cdot 5^{n-1} + 1$, где $q$ не делится на 5. Воспользовавшись теперь формулой
$(a+b)^5 = a^5 = 5a^4b + 10 a^3b^2 + 10a^2b^3 + 5ab^4 + b^5$,
получим:
$2^{4 \cdot 5^{n-1}} - 1 = (2^{4 \cdot 5^{n-2}})^5 - 1 = (q \cdot 5^{n-1} + 1)^5 - 1 = 5^{n+1} (q^5 \cdot 5^{4n-6} + a^4 \cdot 5^{3n-4} + 2 q^3 \cdot 5^{2n-3} + 2q^2 \cdot 5^{n-2}) + q \cdot 5^n$,
откуда видно,что $2^{4 \cdot 5^{n-1}} - 1$ не делится на $5^{n+1}$. Итак, действительно, из справедливости предложения задачи для какого-то $n$ и следует справедливость его и для $n + 1$.
Согласно теореме Эйлера разность $2^k - 1$, где $k = 5^n - 5^{n-1}$, делится на $5^n$ (см. задачу 3053, в частности, примечание к этой задаче). Доказать, что ни при каком $k$, меньшем чем $5^n - 5^{n-1}$, разность $2^k- 1$ не делится на $5^n$.
Решение:
Доказательство проведем методом математической индукции. Прежде всего очевидно, что при $n = 1$ предложение задачи справедливо: $2^1 - 1 = 1, 2^2- 1 = 3$ и $2^3- 1 = 7$ не делятся на 5. Докажем еще это предложение для $n = 2$. Пусть $2^к$ есть наименьшая степень числа 2, дающая при делении на $5^2 = 25$ остаток 1 (т. е. такая, что $2^k - 1$ делится на 25); предположим, что $k < 5^2 - 5 = 25 - 5 = 20$. Если 20 не делится на $к$, так что $20 = q^k + r$, где $r < k$, то мы будем иметь:
$2^{20} - 1 = 2^{qk+r} - 1 = 2^r(2^qk - 1) + (2^r - 1)$.
Но $2^{20} - 1$ делится на 25, в силу теоремы Эйлера, а $2^{qk} - 1 = (2^k)^q- 1^q$ делится на $2^k - 1$, т. е., в силу нашего предположения, тоже делится на 25; следовательно, и $2^r - 1$, делится на 25, что противоречит тому, что $к$ есть наименьшее число, для которого $2^к - 1$ делится на 25, Итак, $k$ должно быть делителем числа 20, т. е. может равняться только 2, 4, 5 или 10. Но $2^2- 1 = 3$, $2^5 - 1 = 31$ и $2^{10} - 1 = 1023$ не делятся даже на 5, а $2^4- 1 = 15$ делится на 5, но не делится на 25. Значит, действительно и для $n = 2$ предложение задачи справедливо.
Предположим теперь, что для какого-то $n$ предложение задачи справедливо, а для значения $n+1$ оно неверно: наименьшее $к$, такое, что $2^k - 1$ делится на $5^{n+1}$, меньше чем $5^{n+1} - 5^n = 4 \cdot 5^n$. В точности, как выше (для $n = 2$), доказывается, что $к$ должно являться делителем числа $4 \cdot 5^n$. С другой стороны, аналогично доказывается, что число $5^n - 5^{n-1} = 4 \cdot 5^{n-1}$ должно являться делителем числа $к$: если бы было $k = q \cdot 4 \cdot 5^{n-1} + r$, где $r < 4 \cdot 5^{n-1}$, то число $5^r - 1$ делилось бы на $5^n$, что противоречит предположению о справедливости утверждения задачи для числа $n$. Таким образом, для $к$ остается единственное возможное значение, а именно: $k = 4 \cdot 5^{n-1}$.
Так как число $2^{5^{n-1}} - 5^{n-2} - 1 = 2^{4 \cdot 5^{n-2} - 1}$ делится на $5^{n-1}$ (в силу теоремы Эйлера) и не делится на $5^n$ (иначе предложение задачи не было бы справедливо для числа $n$), то $2^{4 \cdot 5^{n-2}} = q \cdot 5^{n-1} + 1$, где $q$ не делится на 5. Воспользовавшись теперь формулой
$(a+b)^5 = a^5 = 5a^4b + 10 a^3b^2 + 10a^2b^3 + 5ab^4 + b^5$,
получим:
$2^{4 \cdot 5^{n-1}} - 1 = (2^{4 \cdot 5^{n-2}})^5 - 1 = (q \cdot 5^{n-1} + 1)^5 - 1 = 5^{n+1} (q^5 \cdot 5^{4n-6} + a^4 \cdot 5^{3n-4} + 2 q^3 \cdot 5^{2n-3} + 2q^2 \cdot 5^{n-2}) + q \cdot 5^n$,
откуда видно,что $2^{4 \cdot 5^{n-1}} - 1$ не делится на $5^{n+1}$. Итак, действительно, из справедливости предложения задачи для какого-то $n$ и следует справедливость его и для $n + 1$.
