С6. Уравнения в целых числах

[Новый гость]

Здравствуйте.
Скажите, пожалуйста, существует ли какой-нибудь алгоритм решения уравнения вида `a^x+b=y^2` в целых числах, где `a` - данное натуральное число, `b` - целое число, `x` и `y` - переменные? Очень часто встречаю такие уравнения в С6. Может быть, в какой-нибудь книге описывается решение?
Примеры из книги Пратусевича по С6:
1) `TZ` Решить в целых числах `2^x+65=y^2`[[/TZ]],
2) `TZ` Решить в натуральных числах `3^x+55=y^2`[[/TZ]],
3)`TZ` Решить в целых числах `3^x=1+y^2`[[/TZ]].
По виду они очень похожи, и это наводит на мысль, что и решаются они похоже. Или нет, все они решаются по разному?
Заранее спасибо.

@темы: Олимпиадные задачи, ЕГЭ, Теория чисел

Comments

[VEk]

Посмотрите eek.diary.ru/p148212584.htm Там обсуждалась похожая задача. Очень часто рассматриваются остатки от деления на 2, 3, 4, 8. Используются также формул сокращенного умножения.
Например, в задаче из Пратусевича 3.8 ( у вас под цифрой 2) после рассмотрения остатков от деления на 4, получается, что x-четно, а дальше идет разложение на разность квадратов.
Дерзайте.

[Новый гость]

Спасибо, посмотрю, подумаю. Но я уже пытался решить, и пока безрезультатно.

[Диана Шипилова]

Новый гость
Третье решается очень просто. Рассмотрите остатки от деления на 3.

[VEk]

1. Докажите. что x- четно и используйте разность квадратов.

[Новый гость]

Сейчас и до этих разберусь. Печатал решение третьего уравнения, произошёл какой-то сбой и отправился почему-то старый комментарий. Интернет плохо работает. Пришлось второй раз набирать решение в Word’е.
При всех целых `y` правая часть будет являться натуральным числом, поэтому натуральным числом будет и левая часть. `3^x in NN` только при неотрицательных целых `x`, поэтому рассмотрим два случая.
1. `x=0` `=>` `y=0`
2. `x>0` и `x in ZZ` `=>` `x in NN`.
При любых натуральных `x` левая часть будет делиться на три без остатка. Чтобы уравнение имело решения, нужно, чтобы правая часть также делилась без остатка на 3.
2.1. `y=3n+1`, `n in ZZ` `=>` `9n^2+6n+2` - при делении на 3 даёт остаток 2 - не подходит.
2.2. `y=3n+2`, `n in ZZ` `=>` `9n^2+12n+5` - при делении на 3 даёт остаток 2 - не подходит.
2.3. `y=3n`, `n in ZZ` `=>` `9n^2+1` - при делении на 3 даёт остаток 1 - не подходит.
Следовательно для `x in NN` ни при каких целых значениях `y` уравнение не имеет решений в целых числах.
Таким образом, единственное решение - `(0;0)`.
Ответ: `(0;0)`.

Всё правильно? Дополнительно ничего объяснять не надо?

[VEk]

Стоит пояснить, откуда появляются выражения `9n^2+6n+2` и аналогично с 5.

[Диана Шипилова]

Новый гость
Всё верно.

[Новый гость]

VEk Это левая часть уравнения.

Теперь по первому уравнению.
`2^x+65=y^2`
Левая часть уравнения всегда положительна `=>` правая часть уравнения всегда положительна `=>` т.к. `y` - целое число, то правая часть будет натуральным числом (`y !=0`) `=>` правая часть будет натуральным числом `=>` выражение `2^x` будет натуральным числом `x` - целое неотрицательное число.
При `x=0` `y^2=66` `=>` `y !in ZZ` `=>` значение `x=0` не подходит, и `x` - натуральное число.
Левая часть уравнения нечётна, следовательно, `y` - нечётное число.

Дальше продвинуться не смог.

[Новый гость]

Как доказать, что `x` - чётное?

[Диана Шипилова]

Новый гость
Ну остатки же.

[VEk]

Новый гость Догадался, что это `y^2+1`. Но комиссия, которая будет проверять, может не догадаться.
По поводу №1. Рассмотрите остатки от деления на 5.

[Новый гость]

Может быть, лучше остатки от деления на 4? С 5 ничего не получается.

[Новый гость]

Остатки при делении на 5? Начал рассматривать остатки при делении на 4, переправил. Как понять, что делить нужно именно на 5, а не на 4?

Рассмотрим, какие остатки может давать `y^2` при делении на 5.
1.1. `y=5n+1`, `n in ZZ` `=>` `y^2=25n^2+10n+1` - остаток 1.
1.2. `y=5n+2`, `n in ZZ` `=>` `y^2=25n^2+20n+4` - остаток 4.
1.3. `y=5n+3`, `n in ZZ` `=>` `y^2=25n^2+30n+9` - остаток 4.
1.4. `y=5n+4`, `n in ZZ` `=>` `y^2=25n^2+40n+16` - остаток 1.
1.1. `y=5n`, `n in ZZ` `=>` `y^2=25n^2` - остаток 0.

1. Если `x` - нечётное, то левая часть при делении на 5 даст остаток 2 или 3 (как доказать???). То есть при `x` - нечётном уравнение не имеет решений в целых числах.
2. Если `x` - чётное, то левая часть при делении на 5 даст остаток 1 или 4 (как доказать???)..
То есть при `x` - чётном нам подходят только те значения `y`, которые удовлетворяют формуле `y=5n+1`, `y=5n+2`, `y=5n+3`,`y=5n+4`, где `n=2k+1`, `k in ZZ`.

Какой из этого нужно сделать вывод?

Используем формулу разности квадратов.
`2^x+(1+64)=y^2`,
`2^x+1=y^2-64`,
`2^x+1=(y-8)*(y+8)`,
что дальше?

[VEk]

№1. Легко видеть, что `y` - нечетно. Какие остатки от деления на 5 в этом случае дает `y^2`? Число 65 на 5 вроде делится ( точно не проверял, ). Осталось определить, какие остатки от деления на 5 дает степень двойки. После этого можно сделать некоторые выводы.

[Новый гость]

65 делится на 5 по признаку делимости.
То, что `y` - нечётное, я доказал выше.
Вывод о чётности я уже сделал.
Что делать после разности квадратов и почему делили уравнение именно на 5, а не на 4?

[VEk]

Ну вот , пока писал свой комментарий, Вы уже все написали. Вывод 1: `y^2 (mod 5)` = 0, 1 или 4.
Теперь давайте посчитаем остатки от деления на 5 степеней двойки, они, оказывается периодичны с периодом ... И что видно? Когда остатки обеих частей равенства могут совпадать?

[Новый гость]

Подождите.
`mod5` - это значит "при делении на 5", да?
Откуда 0? Нам подходят только остатки 1 и 4.

[VEk]

Все надо пробовать. В данном случае при `x>=2` обе части уравнения дают одинаковые остатки от деления на 4, а при `x>=3` - и на 8 тоже.
После того, как доказано, что `x` - четно, надо записать `x=2k, k in N ` и тогда уравнение запишется `2^(2k)+65=y^2`. Какие два квадрата видно в этом уравнении?

[VEk]

` a=b ( mod k)`означает, что у чисел a и b совпадают остатки при делении на число k.
`5^2 = 0 ( mod5)`

[Новый гость]

Но нам подходят только `y=5k+1` и `y=5k+4` при `x` - чётном. А при `x` - чётном левая часть не будет давать остаток 0, поэтому и `y=5k` нам не подходит.

[VEk]

Новый гость Вы перескакиваете через один из шагов решения. После Вывода 1 должен идти Вывод 2: "Остатки от деления `2^x` на 5 являются периодическими. с периодом ... . Множество этих остатков пересекается с множеством остатков от деления на 5 правой части. уравнения только при четном x". Тогда и понятно, что остаток 0 правой части нам не подходит.
Вам надо доказать периодичность остатков.

[Новый гость]

То, что остаток 0 не подходит, я доказал, когда разбирал все остатки. Поэтому у меня вывод 1 сразу идёт как то, что из всех `y` нам подходят `y=5n+1` и `y=5n+4`, где `n=2k+1`, `k in ZZ`.
А вот про периодичность я не знаю. Абсолютно нет никаких мыслей, как доказать. Периодичность вообще не понимаю.

[VEk]

Выпишите первые 8 остатков, а дальше метод ММИ.

[Новый гость]

Запутался. Остатки при делении на 5 `y^2` или `2^x` и почему именно так?

[Диана Шипилова]

А мне кажется, проще рассмотреть остатки при делении на 3.

[Новый гость]

Подождите, я уж так начал. Хотя бы с пятёркой до ответа решение довести.

[VEk]

Диана Шипилова Возможно, но с лету у меня не получилось.

[Новый гость]

Ну так что делать мне?

[VEk]

Повторяю. Выпишите первые 8 остатков от деления на 5 степеней двойки, т.е. `2^x`.

[Новый гость]

Выписал
4 - 4
16 - 1
64 - 4
256 - 1
1024 - 4
4096- 1
16384 - 4
Дальше уже слишком много.