Точные степени среди чисел Кацечки

[Ktina]

Назовём натуральное число числом Кацечки, если оно минимальное среди всех натуральных чисел с такой же, как у него, суммой цифр. Найдите все числа Кацечки, являющиеся точными степенями (квадратами, кубами и т. д.) натуральных чисел.

[maxal]

Ktina в сообщении #977102 писал(а):

Назовём натуральное число числом Кацечки, если оно минимальное среди всех натуральных чисел с такой же, как у него, суммой цифр.

A051885, они же числа вида $m\cdot 10^n - 1$, где $1\leq m\leq 9$, $n\geq 0$.

[Ktina]

maxal
Опять мне показалось, что это открытая проблема, а на самом деле это всего лишь задача (пусть и трудная) олимпиадного типа.

[maxal]

Квадрат (и, значит, вообще любая чётная) и третья степень сводятся к вычислениям целых точек на элиптических кривых, а четвертая и более степени невозможны, что следует из теоремы Zsygmondy.

[Ktina]

maxal
Спасибо!

[Руст]

maxal в сообщении #977296 писал(а):

Квадрат (и, значит, вообще любая чётная) и третья степень сводятся к вычислениям целых точек на элиптических кривых, а четвертая и более степени невозможны, что следует из теоремы Zsygmondy.

То, что числа имеют вид $m*10^n-1$ очевидно. Только причем тут эллиптические кривые и теорема Зигмунда?
На самом деле решения для квадратов имеются $m=1,n=1, x=3, m=5,n=1,x=7$. Для других степеней нет.
В доказательстве пожалуй лучше привлекать abc гипотезу. Для квадратов можно доказать и без этого рассматривая уравнения Пелля.

[maxal]

Руст в сообщении #977361 писал(а):

То, что числа имеют вид $m*10^n-1$ очевидно. Только причем тут эллиптические кривые и теорема Зигмунда?

Пусть $m\cdot 10^n - 1 = x^k$ для некоторого $k\geq 2$. Тогда для $k=2,3$, обозначая $y=10^{\lfloor n/3\rfloor}$, мы сводим уравнение к конечному числу элиптических кривых вида:

$$m\cdot 10^t\cdot y^3 - 1 = x^k$$

где $1\leq m\leq 9$ и $0\leq t\leq 2$, целые точки на которых можно явно вычислить (и их конечное число).

Теперь пусть $k\geq 4$. Перепишем уравнение в виде $m\cdot 10^n = x^k + 1$ и рассмотрим последовательность $x^1 + 1,\ x^2 + 1,\ \dots,\ x^k+1$.
Согласно теореме Зигмунда, у каждого члена этой последовательности есть примитивный простой делитель (специальный случай $x=2$ легко рассматривается отдельно). Но простые делители $2, 3, 5, 7$, если и появляются у членов этой последовательности, то уже у членов с показателями не превосходящими $\frac{7-1}{2}=3$ (заметим, что для простого $p\geq 3$, если $q\geq 1$ - минимальное такое число, что $x^q+1$ делится на $p$, то $q$ делит $\frac{p-1}{2}$ и поэтому $q\leq \frac{p-1}{2}$).
Поэтому у $x^k+1$ примитивный простой делитель должен быть отличен от $2,3,5,7$, что противоречит нашему уравнению.

-- Thu Feb 12, 2015 12:01:24 --

Кстати, мое доказательство для $k\geq 4$ по сути опирается на следующее следствие из теоремы Зигмунда:

Всякое число $x^k+1$ для целых $x\geq 2$ и $k\geq 2$, $(x,k)\ne (2,3)$, имеет простой делитель больший $2k$.

[Руст]

Понятно.
Только случай k=2 (и вообще k - четный) проще через уравнение Пелля.
Для нечетного $k\ge 3$ $m*10^n=x^k+1$ сводим $x^k=-1\mod 5^n\to x=-1\mod 5^{n-v_5(k)}$.
Отсюда получается отсутствие решения при нечетном k.

[maxal]

Руст в сообщении #977401 писал(а):

Только случай k=2 (и вообще k - четный) проще через уравнение Пелля.

Как через Пелля получить конечность числа решений?

[Руст]

Решений специального вида конечно.
Можно еще проще.
на 9 заканчивается только квадрат числа оканчивающаяся на 3 или 7. А вот на 99 ни заканчивается ни один квадрат, так как получается число 3 mod 4.