Уравнение в целых числах

[Xenia1996]

Не помню, было ли такое уже на форуме. Если было, не отрывайте мне голову

Решить в целых числах:

$3\cdot 2^m-2\cdot 3^n=42$

[nnosipov]

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

Не помню, было ли такое уже на форуме. Если было, не отрывайте мне голову

Решить в целых числах:

$3\cdot 2^m-2\cdot 3^n=42$

А сократить на 6? И тогда степень двойки минус степень тройки равно семи. И весьма вероятно, что это только $2^4-3^2=7$. Как ни странно, такие уравнения почему-то всегда легко решаются (не знаю ни одного исключения).

[Xenia1996]

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

И весьма вероятно, что это только $2^4-3^2=7$.

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

И, кстати, я в целых просила. Стало быть, весьма невероятно (ибо $2^3-3^0=7$)

[nnosipov]

А, дошло: $2^3-3^0=7$. А насчёт красивого ... Здесь почему-то всегда работает метод остатков, т.е. сравнение по некоторому модулю оказывается неразрешимым. Если здесь это не прокатит, сильно удивлюсь.

[Xenia1996]

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

А, дошло: $2^3-3^0=7$. А насчёт красивого ... Здесь почему-то всегда работает метод остатков, т.е. сравнение по некоторому модулю оказывается неразрешимым. Если здесь это не прокатит, сильно удивлюсь.

Вот здесь-то как раз и не прокатит!

[nnosipov]

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

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

А, дошло: $2^3-3^0=7$. А насчёт красивого ... Здесь почему-то всегда работает метод остатков, т.е. сравнение по некоторому модулю оказывается неразрешимым. Если здесь это не прокатит, сильно удивлюсь.

Вот здесь-то как раз и не прокатит!

Не верю!

[Xenia1996]

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

Не верю!

На три желания поспорим?

Может и прокатит, но либо решение будет громоздким, либо замучаетесь эти остатки искать, а у меня - красиво и просто!

[nnosipov]

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

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

Не верю!

На три желания поспорим?

Может и прокатит, но либо решение будет громоздким, либо замучаетесь эти остатки искать, а у меня - красиво и просто!

А компутер на што? Ладно, завтра развлекусь (у нас по местному уже поздновато будет). Тут ведь дело не в простоте: понять бы, почему всегда прокатывает.

[Xenia1996]

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

А компутер на што?

С компутерами на олимпиады не пускают.

Цитата:

Ладно, завтра развлекусь (у нас по местному уже поздновато будет). Тут ведь дело не в простоте: понять бы, почему всегда прокатывает.

Цветных снов!

Прокатывает, может быть и всегда, но представьте себе, скажем перебор всех остатков при делении на $2011^{2011^{2011}}$
За... Устанете ведь!

[w0robey]

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

nnosipov в сообщении #435671 писал(а):А, дошло: . А насчёт красивого ... Здесь почему-то всегда работает метод остатков, т.е. сравнение по некоторому модулю оказывается неразрешимым. Если здесь это не прокатит, сильно удивлюсь.Вот здесь-то как раз и не прокатит!

Как не прокатит, прокатит, ещё как, обычно такие задачи сравнениями по модулю и решают В случае вашей задачи можно сделать например так:
1) Ставим поочерёдно степени 0 (зачем - во втором шаге)
2^0-3^y=7 - не подходит из-за положительности вычитаемого
2^x-3^0=7 - о чудо, одно решение есть: x=3, y=0
2) Теперь каждое слагаемое проверяем на делимость 3 - 7\equiv1, 3 в положительной степени даёт 0, значит двойка должна давать остаток 1. Это выполняется для чётных степеней двойки (нетрудно проверить)
Получаем x=2a 4^a-3^y=7
Теперь проверяем делимость на 4 и проводя аналогичные рассуждения получим, что и тройка обязана быть в чётной степени. Получаем:
x=2a
y=2b
4^a-9^b=(2^a-3^b)(2^a+3^b)=7
Правая скобка всегда положительна (а значит и левая обязана), левая меньше правой, значит 2^a-3^b=1; 2^a+3^b=7 Выполняя огромный перебор из одного значения убеждаемся, что также подходит b=1, a=2 (или x=4, и y=2) На этом и завершается доказательство, надеюсь всё понятно и правильно!

З. Ы. Хочу предложить многоуважаемой Xenia1996 и другим участникам форума, кто сюда заглянет, задачу, которая была на последнем туре Белорусской республиканской олимпиады, задача 10 класса, второй день, первая задача

3^x-7^y=4^z (x, y, z - натуральные, хотя если они будут целыми, то существенно задача не усложнится)

[Xenia1996]

Значит, я не про те остатки подумала.
Мне показалось, что nnosipov имел в виду следующее:

Если бы $2^m-7$ не могло делиться на 27 ни при каких целых m, это бы сильно облегчило нам решение задачи. Мы бы просто перебрали те случаи, когда $3^n<27$.

А то, что Вы написали, я как раз и имела в виду - представить $2^m-3^n$ в виде разности двух квадратов, доказав предварительно, что m и n обязаны быть чётными (за исключениями, которые можно перебрать по пальцам).

[Sonic86]

Последняя аналогичная задача была тут:
topic42767.html
все ссылки я тогда не нашел наиболее общий метод где-то maxal писал, он заключается именно в сравнениях по модулю.
Хотя, видимо, метод не один (см. посты Руста)

-- Вс апр 17, 2011 10:17:58 --

w0robey писал(а):

$3^x-7^y=4^z$ (x, y, z - натуральные, хотя если они будут целыми, то существенно задача не усложнится)

Щас решим (методом разности квадратов)...
Для $z \geq 2$ берем по уравнение модулю 8:
$3^x \equiv (-1)^y \pmod 8$
откуда $x=2u, y=2v$ и значит
$(3^u-7^v)(3^u+7^v)=4^z \Rightarrow 2 \cdot 7^v = 4^k$ - невозможно. Значит $z \leq 1$. Случай $z=0$ невозможен (берем по модулю 2). Случай $z=1$ - берем по модулю 3: $-1 \equiv 1 \pmod 3$ - противоречие. Значит решений совсем нет.

Можно было сразу по модулю 3 брать - тогда сразу получаем $x=0$

[w0robey]

Прошу прощения, я неправильно этот пример выписал (из-за ночной усталости и влияния этой задачи ). Там вместо минуса плюс стоит, ограничения всё те же.

[nnosipov]

По-видимому, наиболее общий подход связан именно со сравнениями по модулю. Продемонстрирую его на примере уравнения $7^x-3^y=4$ (здесь вряд ли сработают более простые аргументы типа разложить левую часть как разность квадратов). Итак, пусть $x=a+1$, $y=b+1$. Имеем

$$ 3(3^a-1)=7(7^b-1). $$

Так как $3^a-1$ делится на $7$, то $a$ делится на порядок $3$ по модулю $7$, т.е. на $6$. Но тогда $3^a-1$ делится на $13$ (делитель числа $3^6-1$). Поэтому $7^b-1$ делится на $13$, откуда $b$ делится на порядок $7$ по модулю $13$, т.е. на $12$. Но тогда $7^b-1$ делится на $9$ (делитель числа $7^{12}-1$). Противоречие. (Фактически оказывается неразрешимым сравнение $7^x-3^y \equiv 4 \pmod{9 \cdot 13}$ при $y \geqslant 2$.)

Ксения, Вы можете опробовать этот метод на уравнении $2^x-3^y=7$, и он сработает. Руст замечает, что стандартным методом было бы сведение к уравнению Пелля (например, в моём примере --- к уравнению $7X^2-3Y^2=4$, где $X=7^{(x-1)/2}$ и $Y=3^{(y-1)/2}$). Но мне это кажется менее общим подходом. Так, например, мне не удалось исследовать соответствующее уравнение Пелля в случае уравнения $2^x-11^y=5$ (возможно, я что-то упустил, проверьте меня), в то время как метод сравнений и здесь сработал.

ЗЫ. Кстати, когда такую задачу мы сводим к уравнению Пелля, противоречие получается тоже при помощи сравнений. Так что от сравнений никуда не деться.

-- Вс апр 17, 2011 13:25:39 --

w0robey в сообщении #435745 писал(а):

Прошу прощения, я неправильно этот пример выписал (из-за ночной усталости и влияния этой задачи ). Там вместо минуса плюс стоит, ограничения всё те же.

Очень похоже на известное уравнение $3^x+4^y=5^z$. И решаться должно не сложнее. Или я не прав? Доказать, что $x$ и $z$ должны быть чётными и затем записать как $4^z-3^x=7^y$?

[w0robey]

Хорошее рассуждение, таким обычно и решают задачу со сравнениями: берут сравнение, равное одному из слагаемых (допустим мы, как здесь, складываем два слагаемых и получаем ответ), сравнивают по модулю, из этих суждений делают равносильное уравнение, но с другими слагаемыми, и берут сравнения по этим изменённым слагаемым, и так до победного конца...
Вот и получается, что такие задачи решаются либо сравнениями, либо функционально (типа 2^a+3^b=11)

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

Очень похоже на известное уравнение . И решаться должно не сложнее. Или я не прав?

Разве только чуть-чуть