Несложное уравнение в натуральных числах

[nnosipov]

age в сообщении #454355 писал(а):

$987463428403=134367047\cdot7349$
а
$(25^{11}-1)\div23\cdot67$
Вот такое удивительное совпадение.

-- Вс июн 05, 2011 17:16:57 --

В том смысле что $24^{11}-1=23\cdot67\cdot134367047\cdot7349$

А, Вы думаете, что $25^{11 \cdot 987463428403}-1=(25^{11}-1)(25^{987463428403}-1)$. Советую отдохнуть, такое ощущение, что Вы переутомились.

[maxal]

nnosipov в сообщении #454337 писал(а):

age в сообщении #454234 писал(а):

Отсюда возможна ситуация, когда $\dfrac{25^{11\cdot987463428403}-1}{24^{11}-1}$ - целое.

age, это число не целое.

Да, нецелое. Чтобы $25^m-1$ делилось на $24^{11}-1$ необходимо, чтобы $m$ делилось на 11219648341. Но для указанного показателя это не так.

[age]

Больше всего умиляет, что

Цитата:

Несложное уравнение в натуральных числах

[Xenia1996]

age в сообщении #454379 писал(а):

Больше всего умиляет, что

Цитата:

Несложное уравнение в натуральных числах

А Вы первый пост видели?
Там уравнение действительно не очень сложное.

[maxal]

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

Xenia1996 в сообщении #454041 писал(а):

При каких $k\in\mathbb N$ уравнение $\frac{(k+1)^n-1}{k^n-1}=m$ не имеет решений в натуральных числах?

Если поступить аналогично: $k^n-1$ всегда делится на $k-1$. Так как $0\equiv (k+1)^n-1 \equiv 2^n-1\pmod{k-1}$, то $k$ обязано быть чётно, а $n$ кратно мультипликативному порядку (показателю) $2$ по модулю $k-1$.
Если этот порядок чётен, то $k^n-1$ делится на $k+1$, и решений нет. Возможными исключениями остаются только те $k$, для которых этот порядок нечетен. Соответствующие им $k-1$ образуют последовательность A036259. Дальше уже надо думать...

Продолжаем. Итак, пусть у нас $n$ нечетно, $k$ четно, причем порядок 2 по модулю $k-1$ нечетен. Это означает, что 2 является квадратичным вычетом по модулю $k-1$, а следовательно $k-1\equiv \pm 1\pmod{8}$. Но тогда $k+1\equiv 1, 3\pmod{8}$, и значит, $-2$ является квадратичным вычетом по модулю $k+1$.

Я докажу, что случай $n>1$ и $k+1\equiv 3\pmod{8}$ (то есть, $k\equiv 2\pmod{8}$) невозможен.

Так как $(k+1)^n\equiv 1\pmod{k^n-1}$ (напомню: $n$ - нечетно), то $k+1$ является квадратичным вычетом по модулю $k^n-1$, то есть символ Якоби $\left(\frac{k+1}{k^n-1}\right)=1$.
С другой стороны, заметим, что $k^n-1\equiv -2\pmod{k+1}$, и применим квадратичный закон взаимности:

$$\left(\frac{k+1}{k^n-1}\right) = (-1)^{k/2\cdot (k^n-2)/2}\cdot \left(\frac{-2}{k+1}\right)=-1\cdot 1=-1.$$

(здесь мы пользуемся тем, что $k/2$ нечетно и $(k^n-2)/2$ нечетно при $n>1$ нечетно)
Полученное противоречие доказывает, что решений в этом случае нет.

В частности, нет решений для $k=2$, то есть, $\frac{3^n-1}{2^n-1}=m$ при $n>1$.

Возможными исключениями теперь остаются лишь те $k-1$ из A036259, которые сравнимы с 7 по модулю 8:
7, 23, 31, 47, 71, 79, 103, 127, 151, 167, 191, 199, 223, 239, 263, 271, 311, 343, 359, 367, 383, 431, 439, 463, 479, 487, ...

-- Sun Jun 05, 2011 19:29:57 --

Каждую конкретное значение $k$, скорее всего, можно убить небольшим перебором.

Для $k=7$ это уже было сделано выше. А вот $k=24$ уничтожается, например, так:

$25^n-1$ обязано делиться на $24-1=23$, а поэтому $n$ делится 11.
Но тогда $25^n-1$ делится на $24^{11}-1$, а поэтому $n$ делится на 11219648341.
Поэтому $25^n-1$ делится на $88177$ (которое является делителем $24^{11219648341}-1$), но тогда $n$ делится на 44088. Противоречие.

[nnosipov]

Ожидалось, что способ решения для случая $k=2$ можно распространить на некоторые другие случаи. Думаю, что-то в этом роде (достаточное условие нецелости для всех или почти всех $n$) можно дать и в более общей ситуации, т.е. для дроби $(a^n-1)/(b^n-1)$ с некоторыми $a$, $b$. Задача про дробь $(3^n-1)/(2^n-1)$ довольно стара, скорее всего, эти обобщения уже известны.

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

Каждую конкретное значение $k$, скорее всего, можно убить небольшим перебором.

Небольшой --- это, наверное, как повезёт. И потом, нужно будет разлагать на множители большие числа типа $24^{167}-1$. Сколько у Вас времени заняла факторизация этого числа? Мой Maple вчера его не смог разложить, а Ваш PARI/GP, видимо, справился? Хотя на самом деле нужно только, чтобы порядок $25$ по модулю $24^{167}-1$ был чётен. Можно ли это доказать не вычисляя?

Кстати, проверил сейчас, делится ли $25^{1892216883193587217526746650035077787956292204}-1$ на $24^{167}-1$. Оказалось, что нет. Что же это за загадочное число, на которое $n$ обязано делиться?

[maxal]

Была описка в коде, приведшая к неправильным результатам.
Доказательство для $k=24$ исправил, и теперь в нем нет "загадочного числа". ;)

[nnosipov]

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

$25^n-1$ обязано делиться на $24-1=23$, а поэтому $n$ делится 11.
Но тогда $25^n-1$ делится на $24^{11}-1$, а поэтому $n$ делится на 11219648341.
Поэтому $25^n-1$ делится на $88177$ (которое является делителем $24^{11219648341}-1$), но тогда $n$ делится на 44088. Противоречие.

Да уж, всё оказалось ещё проще. Подряд перебираем и чудесным образом находим $88177$ (оно оказалось первым в списке, а дальше есть $2028071$ и т.д.) Кто бы мог подумать, что у числа $24^{11219648341}-1$ окажется много маленьких делителей. Интересно, до каких $k$ этот фокус удаётся?

[age]

nnosipov в сообщении #454687 писал(а):

Интересно, до каких $k$ этот фокус удаётся?

А Вы разве не знаете?

[nnosipov]

age в сообщении #454753 писал(а):

nnosipov в сообщении #454687 писал(а):

Интересно, до каких $k$ этот фокус удаётся?

А Вы разве не знаете?

Нет, не знаю. Список представляющих интерес значений $k-1$ приведён выше, и фокус был продемонстрирован только для $k=8$ и $k=24$. Следующее интересное значение --- $k=32$. Сможете для него показать тот же фокус? Как много интересных значений $k$ можно обработать подобным образом?

[maxal]

nnosipov в сообщении #454888 писал(а):

Следующее интересное значение --- $k=32$. Сможете для него показать тот же фокус?

Так как $33^n-1$ делится на $32-1$, то $n$ делится на 5.
Но тогда $33^n-1$ делится на $32^5-1$, что влечет делимость $n$ на 1800. Вуаля.

-- Mon Jun 06, 2011 13:44:15 --

Для $k=48$ тоже все просто:

? znorder(Mod(49,48-1))
%3 = 23
? znorder(Mod(49,48^23-1))
%4 = 167408269445841662902217430590220

-- Mon Jun 06, 2011 13:45:19 --

И для $k=72$ тоже:

? znorder(Mod(73,72-1))
%5 = 35
? znorder(Mod(73,72^35-1))
%6 = 1953603476888653398214073158658169202674701627400

-- Mon Jun 06, 2011 13:46:30 --

и для $k=80$ тоже:

? znorder(Mod(81,80-1))
%7 = 39
? znorder(Mod(81,80^39-1))
%8 = 13982618480378038812055644172992939400681579469359310882550

-- Mon Jun 06, 2011 13:48:06 --

и для $k=104$:

? factor( znorder(Mod(105,104-1)) )
%11 = 
[3 1]

[17 1]

? znorder(Mod(105,104^3-1))
%12 = 102

-- Mon Jun 06, 2011 13:50:30 --

ну и $k=128$ до кучи:

? factor( znorder(Mod(129,128-1)) )
%15 = 
[7 1]

? znorder(Mod(129,128^7-1))
%16 = 316619771328

[age]

nnosipov в сообщении #454888 писал(а):

Нет, не знаю.

Ну вообще-то $24=4!$. У всех $(k!)^n-1$ будет много маленьких делителей (в контексте задачи, в общем случае это неверно). Случай $32=2^5$ почти тривиален, (там очень много маленьких делителей). Ну а если много маленьких делителей, то можно поприменять этот фокус.

[nnosipov]

Вряд ли это счастье будет длиться долго, порядки как-то угрожающе растут (я имел в виду опыты maxal'а).

[maxal]

nnosipov
Долго - понятие относительное. Готов обсудить конкретное проблематичное значение.

[nnosipov]

age в сообщении #454911 писал(а):

У всех $(a!)^n-1$ будет много маленьких делителей

А это с чего вдруг? Возьмите, например, $a=35$.

-- Вт июн 07, 2011 02:35:31 --

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

nnosipov
Долго - понятие относительное. Готов обсудить конкретное проблематичное значение.

Мне сейчас вспомнилась подобная же история с уравнением вида $a^x-b^y=a-b$, которое нужно решить в натуральных $x$, $y$ при фиксированных $a$, $b$. Поначалу мне казалось, что есть только единичные примеры, когда оно решается (примерно таким же фокусом с порядками). Потом эти примеры стали множится, и в какой-то момент захотелось сконструировать уравнение этого вида, для которого фокус не проходил бы. И, как ни странно, не удалось (но я, правда, не сильно и старался). Думается, здесь как раз интересно было бы найти эти проблематичные ситуации. Понимаю, что это несколько скучновато, поэтому не настаиваю.

-- Вт июн 07, 2011 02:42:29 --

age в сообщении #454911 писал(а):

У всех $(k!)^n-1$ будет много маленьких делителей (в контексте задачи, в общем случае это неверно)

Ох, и любите же Вы фантазировать. Какой-такой контекст? Здесь конкретные примеры надо разбирать.