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
7377
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
7377
А, дошло: $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
7377
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
7377
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
8505
Последняя аналогичная задача была тут:
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
7377
По-видимому, наиболее общий подход связан именно со сравнениями по модулю. Продемонстрирую его на примере уравнения $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  След.

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



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

Сейчас этот форум просматривают: Google [Bot]


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

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