2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Уравнение в целых числах
Сообщение16.04.2011, 21:47 


01/10/10

2116
Израиль (племянница БизиБивера)
Не помню, было ли такое уже на форуме. Если было, не отрывайте мне голову :D

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

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

 Профиль  
                  
 
 Re: Уравнение в целых числах
Сообщение16.04.2011, 22:36 
Заслуженный участник


20/12/10
8858
Xenia1996 в сообщении #435649 писал(а):
Не помню, было ли такое уже на форуме. Если было, не отрывайте мне голову :D

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

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


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

 Профиль  
                  
 
 Re: Уравнение в целых числах
Сообщение16.04.2011, 22:47 


01/10/10

2116
Израиль (племянница БизиБивера)
nnosipov в сообщении #435661 писал(а):
И весьма вероятно, что это только $2^4-3^2=7$.

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

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

 Профиль  
                  
 
 Re: Уравнение в целых числах
Сообщение16.04.2011, 22:56 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Уравнение в целых числах
Сообщение16.04.2011, 22:58 


01/10/10

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

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

 Профиль  
                  
 
 Re: Уравнение в целых числах
Сообщение16.04.2011, 23:00 
Заслуженный участник


20/12/10
8858
Xenia1996 в сообщении #435672 писал(а):
nnosipov в сообщении #435671 писал(а):
А, дошло: $2^3-3^0=7$. А насчёт красивого ... Здесь почему-то всегда работает метод остатков, т.е. сравнение по некоторому модулю оказывается неразрешимым. Если здесь это не прокатит, сильно удивлюсь.

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


Не верю!

 Профиль  
                  
 
 Re: Уравнение в целых числах
Сообщение16.04.2011, 23:03 


01/10/10

2116
Израиль (племянница БизиБивера)
nnosipov в сообщении #435674 писал(а):
Не верю!

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

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

 Профиль  
                  
 
 Re: Уравнение в целых числах
Сообщение16.04.2011, 23:09 
Заслуженный участник


20/12/10
8858
Xenia1996 в сообщении #435675 писал(а):
nnosipov в сообщении #435674 писал(а):
Не верю!

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

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


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

 Профиль  
                  
 
 Re: Уравнение в целых числах
Сообщение16.04.2011, 23:13 


01/10/10

2116
Израиль (племянница БизиБивера)
nnosipov в сообщении #435677 писал(а):
А компутер на што?

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

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


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

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

 Профиль  
                  
 
 Re: Уравнение в целых числах
Сообщение16.04.2011, 23:48 


14/04/11
33
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 Выполняя огромный перебор из одного значения :wink: убеждаемся, что также подходит b=1, a=2 (или x=4, и y=2) На этом и завершается доказательство, надеюсь всё понятно и правильно! :-)

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

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

 Профиль  
                  
 
 Re: Уравнение в целых числах
Сообщение17.04.2011, 00:16 


01/10/10

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

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

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

 Профиль  
                  
 
 Re: Уравнение в целых числах
Сообщение17.04.2011, 07:02 
Заслуженный участник


08/04/08
8556
Последняя аналогичная задача была тут:
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$ :?

 Профиль  
                  
 
 Re: Уравнение в целых числах
Сообщение17.04.2011, 09:06 


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

 Профиль  
                  
 
 Re: Уравнение в целых числах
Сообщение17.04.2011, 09:11 
Заслуженный участник


20/12/10
8858
По-видимому, наиболее общий подход связан именно со сравнениями по модулю. Продемонстрирую его на примере уравнения $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$ (возможно, я что-то упустил, проверьте меня), в то время как метод сравнений и здесь сработал.

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

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

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


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

 Профиль  
                  
 
 Re: Уравнение в целых числах
Сообщение17.04.2011, 10:03 


14/04/11
33
Хорошее рассуждение, таким обычно и решают задачу со сравнениями: берут сравнение, равное одному из слагаемых (допустим мы, как здесь, складываем два слагаемых и получаем ответ), сравнивают по модулю, из этих суждений делают равносильное уравнение, но с другими слагаемыми, и берут сравнения по этим изменённым слагаемым, и так до победного конца... :D
Вот и получается, что такие задачи решаются либо сравнениями, либо функционально (типа 2^a+3^b=11)
nnosipov в сообщении #435750 писал(а):
Очень похоже на известное уравнение . И решаться должно не сложнее. Или я не прав?

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group