Тяжёлая теория чисел (наверное, тяжёлая)

[BanmaN]

Найти все x, y, z - натуральные, такие, что
$3^x-2^y=19^z$.

USAMO unused какого-то года, вроде.

Спасибо за помощь!

(Оффтоп)

Сам не решил, но, вроде, добыл что-то (точно не уверен в результатах: решал месяц назад и то тяп-ляп, а сейчас даже листик потерял, так что по памяти)
Представлял в таком виде:
$3^3(3^x-19^z)=2^3(2^y-19^z)$, после чего получил что-то вроде x делится на 16, z делится на 6 и т.д., но и это ни к чему не привело. Если это может помочь, то могу попробовать подыскать листок, но там, мне помнится, перебор жесточайший был.

[ИСН]

Соображения по модулю хороши тогда, когда решений вообще нет. А здесь есть по крайней мере (1,1,0), (2,3,0) (да, я заметил слово "натуральные", но если бы был тотальный запрет по делимости, то и эти бы не прошли) и (3,3,1).

[Хорхе]

Наличие этих решений не совсем запрещает сравнения по модулю: еще можно брать довольно большие степени двойки и тройки (как предложенное автором 16), остатки по которым не периодичны; хотя помогут они вряд ли.

[spaits]

ИСН в сообщении #418516 писал(а):

Соображения по модулю хороши тогда, когда решений вообще нет. А здесь есть по крайней мере (1,1,0), (2,3,0) (да, я заметил слово "натуральные", но если бы был тотальный запрет по делимости, то и эти бы не прошли) и (3,3,1).

Решение должно быть в натуральных числах, годится только последнее Ваше решение: $(3;3;1)$.

[BanmaN]

Идея состояла в том, что, скажем, напимер, получить, что для того, чтобы правая часть делилась на $3^3$ необходимо, чтобы показатели делились на что-то, по очереди получаем такие следствия (то с одной стороны, то с другой), а потом получаем, что оказывается левая часть делится и на $3^4$, что и даёт противоречие...
Такая тактика очень часто работает, так вот я и думал, что и тут может сработать, но потонул в вычислениях.

[Sonic86]

ИСН писал(а):

Соображения по модулю хороши тогда, когда решений вообще нет. А здесь есть по крайней мере (1,1,0), (2,3,0) (да, я заметил слово "натуральные", но если бы был тотальный запрет по делимости, то и эти бы не прошли) и (3,3,1).

А вроде же нет. Уже же много задач решали типа $3^n-2^m=1$, как раз соображениями по модулю. и решения были.

(Оффтоп)

по-моему, они хороши, когда классы вычетов по модулю $p$ переходят в себя, а тут это не так

И maxal ссылку давал на метод. Надо найти...

-- Вт мар 01, 2011 10:08:20 --

Вот тут немного, но это не то: topic42305.html
Блин, не могу найти ((

-- Вт мар 01, 2011 10:43:11 --

Ага! Вот: topic16555.html

[Батороев]

Цитата:

Тяжёлая теория чисел (наверное, тяжёлая)

Не тяжелая, а очень тяжелая!
Если найдется, хотя бы одно решение для $x;y;z>2$, то можно сшибить сотню тысяч зеленых... за опровержение гипотезы Биля.

[Sonic86]

Ну, возьмем по модулю 3: $-2^y \equiv 1 \pmod 3$, $y \equiv 1 \pmod 2$
$y=2y_1+1$: $3^x-2^y = 19^z \Leftrightarrow 3^x-2 \cdot 4^{y_1} = 19^z$
Ну возьмем по модулю 9 c $x \geq 2$: $-2 \cdot 4^{y_1} \equiv 1 \pmod 9$, $y_1 \equiv 1 \pmod 3$
$y_1 = 1+3y_2$: $3^x - 8 \cdot 64^{y_2} = 6^z$
Возьмем по модулю $13$: $3^x \mod 13 = 1;3;9; 6^z \mod 13 = 6;5;2$
Видим еще что $x \geq 2z$ и тогда взяв по модулю 4 получим $z \equiv x \pmod 4$, то есть можно взять $x=z+4x_1$
Подставим: $3^z \cdot 81^{x_1} - 8 \cdot 64^{y_2} = 19^z$.
Берем по модулю 5, получим: $2 \cdot (-1)^{y_2} = (-1)^z - 3^z \pmod 5$, откуда $y_2 \equiv 0 \pmod 2$, $y_2 = 2y_3$
$3^z \cdot 81^{x_1} - 8 \cdot 256^{y_3} = 19^z$
Берем по модулю 17, получаем $3^z(-4)^{x_1}-8 \equiv 2^z \pmod 17$, $(-4)^{x_1} \equiv 6^z(2^z+8) \pmod 17$, откуда $x_1 \equiv 3 \pmod 4, z \equiv 0 \pmod 4$ или $x_1 \equiv 0 \pmod 4, z \equiv 3 \pmod 4$
Берем опять по модулю 5 - получаем в первом случае $1 + 2 \equiv 1 \pmod 5$, а во втором $3^3+2 \equiv 3^3 \pmod 5$. Значит при $y \geq 4, x \geq 2$ решений нет. Остальное - перебором, но там уже всегда будет 2 переменные - будет гораздо проще.
Если не ошибся нигде ,но принцип такой. Лучше ссылку на maxalа найти - там понятнее у него...

[bot]

ИСН в сообщении #418516 писал(а):

Соображения по модулю хороши тогда, когда решений вообще нет.

Ну как бы не совсем. По модулю 5 если посмотреть, то это сильно ограничивает возможности для переменных. Дальше этого шага не посмотрел.

[Sonic86]

(Оффтоп)

Вот уравнение $y^3 = x^2+2$ модулярными штуками точно не решить именно потому, что есть решение.

[bot]

(Оффтоп)

А кто говорит, что надо обходиться только модулярными штуками?

[Sonic86]

(Оффтоп)

Цитата:

А кто говорит, что надо обходиться только модулярными штуками?

Ну я же вообще говорил Просто почему-то в таких уравнения модулярные штуки существенны, а вот для алгебраических - почти нет.

[Руст]

Стандартный способ решения таких уравнений есть сведение к уравнению Пелля.
Если $x,y$ четные, то приходим $3^{x/2}-2^{y/2}=19^{t}, 3^{x/2}+2^{y/2}=19^{z-t}$ - нет решений. Если $x,z$ четны, то аналогично $3^{x/2}-19^{z/2}=2^t,3^{x/2}+19^{z/2}=2^{y-t}\to x=2,z=0$. Если $y,z$ четны, то $3^x=a^2+b^2$ противоречие.
Поэтому не более одного из них четное число.
Если $x$ четно, то так как $z,y$ нечетны $2^y=6\mod 8$ противоречие.
Если $y$ четно, то $19^z+2^y=1+1\mod 3$ противоречие.
Пусть $x=2k-1,y=2m+1$, тогда уравнение можно записать в виде:
$a^2-6b^2=3*19^z, a=3^k,b=2^m$.
Это уравнение на норму числа $a+b\sqrt 6 \in Z[\sqrt 6]$.
Имеем $|3\pm \sqrt 6|=3, |5\pm \sqrt 6|=19, |5\pm 2\sqrt 6|=1$. Из однозначности разложения в $Z[\sqrt 6]$ получаем $a+b\sqrt 6 =(5+2\sqrt 6)^l(3\pm\sqrt 6)(5\pm\sqrt 6)^z$.
Учитывая, что $a=3^k,b=2^m$ и переходя к cравнениям по этим модулям для $z$ получаем единственное решение.

[BanmaN]

Руст, подскажите, пожалуйста, какую-нибудь литературу, чтобы разобраться в вашем решении.

Sonic86 в сообщении #418591 писал(а):

Видим еще что $x \geq 2z$ и тогда взяв по модулю 4 получим $z \equiv x \pmod 4$, то есть можно взять $x=z+4x_1$

Только не 4, а 16.

Sonic86 в сообщении #418591 писал(а):

Берем по модулю 17, получаем $3^z(-4)^{x_1}-8 \equiv 2^z \pmod 17$, $(-4)^{x_1} \equiv 6^z(2^z+8) \pmod 17$, откуда $x_1 \equiv 3 \pmod 4, z \equiv 0 \pmod 4$ или $x_1 \equiv 0 \pmod 4, z \equiv 3 \pmod 4$

Вроде, у меня получилось, что по 17 уже противоречие.
возможности для $(-4)^x$ такие:
$-4, -1 , 4, 1$

Для $6^z : 6, 2, -5, 4, 7, 8, -3, -1, -6, -2, 5, -4, -7, -8, 3, 1 $
Для $2^z+8 : 10, -5, -1, 7, 6, 4, 0, 9, 10, -5, -1, 7, 6, 4, 0, 9 $

[Sonic86]

BanmaN писал(а):

Только не 4, а 16.

Угу, наврал.

Цитата:

Вроде, у меня получилось, что по 17 уже противоречие.

Ну, главное, чтобы Вы метод поняли. Жаль ссылку на maxalа не нашел - была бы полная картина

Если я правильно понял, Руст просто использует алгебраическую теорию чисел, даже квадратичные поля. Они есть в Хассе Теория чисел, Айрленд, Роузен Теория чисел, Боревич, Шафаревич и даже в Постникове "ВТФ. Введение в алгебраическую теорию чисел"