С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

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

Я потом на это не обращал внимание, потому что был момент, когда я понимал, как нужно доказать, а потом забыл. Т.е. и в этом случае нужно доказывать периодичность остатков, верно?
Я правильно начинал в 2011-02-25 в 16:42 ?

[VEk]

Начинали верно, но только надо было взять `x=4n+2` и `4n+4`.
Мне вот тут коллеги подсказали "`2^(n+4)-2^n=15*2^n` не требует явного применения ММИ" и утверждают, что именно так рекомендуется в книге Пратусевича.

[Гость]

Пример 1.7 стр. 8

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

Про неявное применение ММИ, так же как и пример 1.7, не понял.
Перечитал теорию по индукции, похожего не нашёл.

Индукция по `n`: число `2^(4n+2)` при делении на 5 даёт остаток 4.
1. Для `n=0` верно.
2. Пусть верно для `n=k`:
`2^(4n+2)=4(mod5)`,
тогда утверждение должно быть верно и для `n=k+1`:
`2^(4k+2+4)=2^(4k+2)*16`.

Как показать, что число `2^(4k+2)*16` даёт остаток 4 при делении на 5?

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

Пришла в голову такая мысль. Остаток от деления 1-го числа на 2-е равно остатку от деления на 2-е число произведения остатков от деления на 2-е число множителей 1-го числа.
Применительно к данному случаю: Остаток от первого множителя 4, от второго 1, их произведение 4 при делении на 5 даёт остаток 4, тогда всё верно, утверждение доказано. Главное - правильно ли то, что выделено курсивом?

[VEk]

`2^(4k+2) = 4 (mod5)` это означает, что `2^(4k+2) = 5*M+4`. `16=5*3+1`. Перемножьте эти равенства.

PS Новый гость А вы задачи С1-С5 все решаете? На мой взгляд за C6 стоит браться тогда, когда C1-C4 делаются максимум за 1час (все) и за полчаса вся часть B. 2.5 часа на C5 и С6 - это достаточно скромно (по времени).

[VEk]

правильно ли то, что выделено курсивом?

Правильно!

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

Приступаю ко второму уравнению.
`3^x+55=y^2`, решить в натуральных числах.

Рассмотрим остатки от деления на 5 числа `y^2`.
1. `y=5m+1` `=>` `y^2=25m^2+10m+1` - даёт остаток 1 при делении на 5.
2. `y=5m+2` `=>` `y^2=25m^2+20m+4` - даёт остаток 4 при делении на 5.
3. `y=5m+3` `=>` `y^2=25m^2+30m+9` - даёт остаток 4 при делении на 5.
4. `y=5m+4` `=>` `y^2=25m^2+40m+16` - даёт остаток 1 при делении на 5.
5. `y=5m` `=>` `y^2=25m^2` - даёт остаток 0 при делении на 5.

1 случай. Пусть `x` - чётное, тогда левая часть при делении на 5 даёт в качестве остатка либо 4, либо 1.
Докажем это.
Множество чётных `x` разобьём на 2 подмножества:
1.1. `x=4n+2`, где `n` - целое неотрицательное число.
Докажем по индукции, что все числа вида `3^(4n+2)` при делении на 5 дают остаток 4.
Для `n=0` верно, т.к. 9 при делении на 5 даёт остаток 4.
Пусть утверждение верно для `n=k`, т.е. все числа вида `3^(4k+2)` при делении на 5 дают остаток 4, тогда оно должно быть верно и для `n=k+1`:
`3^(4k+2+4)=3^(4k+2)*81`. Остаток первого множителя от деления на 5 равен 4, от второго 1. Их произведение 4 при делении на 5 даёт остаток 4, значит, предположение верно.
1.2. `x=4n+2`, где `n` - целое неотрицательное число.
Аналогично п.1.1 доказываем, что все числа вида `3^(4n+4)` при делении на 5 дают остаток 1.
Следовательно, при чётном `x` левая часть даёт такие же остатки от деления на 5, что и правая часть.

2 случай. Пусть `x` - чётное, тогда левая часть при делении на 5 даёт в качестве остатка либо 3, либо 2. Аналогично случаю 1 доказываем истинность этого утверждения, применяя ММИ.
Следовательно, при нечётном `x` остатки левой части от деления на 5 не совпадают с остатками правой части от деления на 5.

Вывод: `x` - чётное, т.е. `x=2t`, преобразуем исходное уравнение следующим образом:
`y^2-(3^t)^2=55`,
`(y-3^t)*(y+3^t)=55`.
Т.к. `y in NN`, то второй множитель в левой части больше нуля, а значит, и первый множитель больше 0. Кроме того, второй множитель не равен 1 и больше первого множителя. Учитывая это и используя то, что выражения в скобках являются натуральными числами, получаем совокупность двух систем:
1) `{(y-3^t=1),(y+3^t=55):}` `<=>` `x=6; y=28`,
2) `{(y-3^t=5),(y+3^t=11):}` `<=>` `x=2; y=8`.

Ответ: `(6;28)`, `(2;8)`.

Так бы я решал на ЕГЭ.
Вопросы.
1) Всё ли верно, нужны ли дополнительные обоснования? Что не хватает? Что лишнее?
2) Можно ли было опускать доказательство остатков и писать "аналогично" или же нужно всё подробно расписывать?
3) Обязательно ли в качестве временных переменных, которые были нужны только на определённом этапе решения и не использовались на другом, брать разные "БУКВЫ": `m`, `n`, `k`, `t`?
4) Сколько бы баллов из 4-х поставил эксперт на ЕГЭ?

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

PS Новый гость А вы задачи С1-С5 все решаете? На мой взгляд за C6 стоит браться тогда, когда C1-C4 делаются максимум за 1час (все) и за полчаса вся часть B. 2.5 часа на C5 и С6 - это достаточно скромно (по времени).

С1-С4 за час? Это же невозможно. На каждую задачу по 15 минут. С4 за 15 минут - это нереально! Нет, к сожалению, плохо получаются задачи с параметрами. Решал по Козко (книга из серии МЦНМО), но она показалась очень трудной.

[Robot]

Новый гость 4) Сколько бы баллов из 4-х поставил эксперт на ЕГЭ?
Вы посмотрели выложенные на diary рекомендации для экспертов?

[VEk]

Вообще-то в самом первом комментарии Вам советовали здесь использовать делимость на 4 (намного прощерешение). Ваши выкладки, если очень надо, могу посмотреть завтра, но не сейчас.

[VEk]

С1 - 10минут, С2- 15-20 минут, С3 - 10 минут, С4 - 20 - 25 минут (это все с оформлением). Настоятельно рекомендую больше внимания обратить на С1-С4, нежели на С6. Они проще (намного).

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

Robot Да, я их видел. Только там нет этой задачи, и оценка собственных решений всегда необъективна.

VEk 20-25 минут на С4 - очень мало. Неужели кто-то способен проходить тесты с такой скоростью?

[VEk]

Новый гость На самом деле корифеи делают без ошибок часть B за 15 минут, с1 и с3 еще за 15 минут, С2 за 10 и на 3 последние задачи можно отвести остальное время. Но это корифеи. Средний школьник (прилично наученный) на часть B тратит около часа, c1-c3 - еще минут 40, С2 - С4 - где-то 1 - 1,5 часа. И когда на последние 50 минут перед ним открываются задачи С5 и С6, с ним становится плохо. Поэтому если хотите на экзамене успеть взяться за С5 и С6, отрабатывайте начальные пункты до автоматизма.

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

Значит, мне "станет плохо". Часть В за 15 минут - невозможно. Наш учитель сделал часть В за 15 минут, используя калькулятор (а в заданиях, например, В1, В12 и В5 особенно он существенно облегчает задачу).
Я думал, что лучше всё проходить параллельно, пока буду отрабатывать начальные пункты (С4 начальным пунктом никак нельзя назвать), можно и не добраться до подготовки к С5 и С6.

[VEk]

Но книгу Гордина ( С4 из серии МЦНМО) прорешать явно стоит. Да и в книгах С1 , С2, С3 тоже есть над чем подумать.

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

Все книги С1-С4? Нужно попробовать. Все эти книги я начинал, но потом отвлекался и забывал про них.
А параметры?

[VEk]

Параметры намного сложнее. Особенно если надо доказывать достаточность полученных условий (в тетрадях типа типовых вариантов, самых полных вариантов и т.п.)

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

Т.е. к С5 подготовиться практически невозможно... Понятно. Спасибо за помощь. Проверите завтра решение задачи 2)?

[VEk]

Завтра проверю. К С5 подготовиться можно, но достаточно трудно. Но в С6 может тоже попасться такая задача, что можно на нее час смотреть и не увидеть решения (хотя оно может быть очень простым).
Вот например задача из самарского сборника: "найти сумму всех чисел, не превосходящих 1000, каждое из которых имеет нечетное число делителей". Засеките время на поиск и оформление решения этой задачи.

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

Завтра проверю. К С5 подготовиться можно, но достаточно трудно. Но в С6 может тоже попасться такая задача, что можно на нее час смотреть и не увидеть решения (хотя оно может быть очень простым). Вот например задача из самарского сборника: "найти сумму всех чисел, не превосходящих 1000, каждое из которых имеет нечетное число делителей". Засеките время на поиск и оформление решения этой задачи.

По С5. Можно, но достаточно трудно - это по какой книге?

По С6. Засекаю время: 20:28. Как-то раз в сентябре или октябре, готовясь к городской олимпиаде по сборнику Агаханова, я встретил там задачу о том, какие числа имеют нечётное число делителей. Так вот оказывается, эти числа - полные квадраты (не знаю, есть ли "неполные" квадраты, но использовался, кажется, именно такой термин).
Полные квадраты (имеются в виду натуральные числа) до 1000 - это 1, 4, 9 и т.д. Последний квадрат - это `31^2=961`.
Теперь нужно использовать формулу суммы квадратов. Она существует готовая, но на ЕГЭ нужно будет вывести. Я знал эту формулу, но забыл. Вроде бы она выводится по индукции.
Выводил минут 40, но всё-таки получилось.

Закончил в 21:55. Самым трудным было вывести формулу суммы квадратов.
Вообще, эта задача для меня оказалась в какой-то степени нетрудной, потому что я знал о существовании элементов 1 и 2 решения.
В общем, решал полтора часа. Никакими справочниками не пользовался "для чистоты эксперимента", хотя хотелось подсмотреть формулу. Подглядел два раза только в сам задачник: первый раз, чтобы уточнить условие: должно быть слово "натуральные", и второй раз, чтобы проверить ответ.

Итак, решение:

1. Если `d` - делитель натурального числа `A`, то `A/d` - тоже делитель числа `A`. Таким образом, все делители числа можно разбить на пары, и их будет чётное число. Нечётное число делителей будет в том случае, когда какие-то два делителя равны, т.е. `d=A/d`, отсюда `A=d^2`, т.е. число, имеющее нечётное число делителей, является полным квадратом. Задача сводится к нахождению суммы квадратов натуральных чисел, не превышающих 1000.

2. Выведем формулу для нахождения суммы квадратов. Для этого рассмотрим несколько первых частных случаев:
`S_1=1`,
`S_2=1+4=5`,
`S_3=5+9=14`,
`S_4=14+16=30`,
`S_5=30+25=55`,
`S_6=55+36=91`,
`S_7=91+49=140`,
`S_8=140+64=204`,
`S_9=204+81=285`.
Возьмём для рассмотрения три последних суммы:
`S_7=140=2*2*5*7=7*8/2*(2*7+1)/3=(7(7+1)(2*7+1))/6`,
`S_8=204=2*2*3*17=8/2*9/3*(2*8+1)=(8(8+1)(2*8+1))/6`,
`S_9=285=3*5*19=9/3*10/2*(2*9+1)=(9(9+1)(2*9+1))/6`.
Делаем вывод, что `S_n=(n*(n+1)*(2*n+1))/6`.
Докажем это утверждение по индукции.
Для `n=1` верно, т.к. `S_1=(1(1+1)(2*1+1))/6=1`.
Пусть утверждение верно для `n=k`:
`S_k=(k*(k+1)*(2*k+1))/6`.
Тогда утверждение верно и для `n=k+1`:
`S_(k+1)=((k+1)*(k+2)*(2*k+1+2))/6=(k(k+1)(2k+1+2)+2(k+1)(2k+3))/6=(k(k+1)(2k+1)+2k(k+1)+2(k+1)(2k+3))/6=(k(k+1)(2k+1))/6+(2k(k+1)+2(k+1)(2k+3))/6=`
`=S_k+(2(k+1)(3k+3))/6=S_k+(k+1)^2` - верно.
Итак, сумма `n` первых квадратов натуральных чисел находится по формуле `S_n=(n*(n+1)*(2*n+1))/6`.

3. Найдём последний член последовательности методом подбора.
`n=30` `=>` `n^2=900<1000`,
`n=31` `=>` `n^2=961<1000`,
`n=32` `=>` `n^2=1024>1000`.
Итак, последний число, удовлетворяющее условию задачи - это `961`, поэтому `n=31`.
`S_31=(31*32*63)/6=(31*16*2*21*3)/6=31*16*21=10416`.

Ответ: `10416`.

Всё правильно, обосновано, доказано? Сколько баллов? Проверьте, пожалуйста.

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

2.5 часа на C5 и С6 - это достаточно скромно (по времени).

Да, это точно.
На кого же рассчитан экзамен, если 4-х часов не хватает?

[VEk]

Полтора часа на задачу, решение которой видно практически сразу. Вот и задумайтесь по поводу затрат времени на экзамене. Прибавьте туда волнение. а если сразу решение не видно? Что тогда?
Поэтому в первую очередь сосредоточьте свои усилия на задачах C1 - C4 и части B.
По поводу оформления: Догадались или вспомнили формулу - сразу пишем докажем то-то. Совсем необязательно считать 10 значений и якобы догадываться до вида формулы. Это отнимает время. Кроме того возможны ошибки в вычислениях. Ваши цифры, кроме последней и квадратов 31 и 32 не проверял. а так решение вроде полное - соответственно, полный балл.

Экзамен рассчитан на поступление в ВУЗ. А полный балл (100) получают единицы - в прошлом году 157 чел. из 830000. Поэтому надо стремиться набрать как можно больше баллов - по прошлому году - результат 75-80 практически гарантирует поступление на бюджет (конечно, все зависит от выбранной специальности и ВУЗа).

[VEk]

Задача 2. 2-й случай x- нечетное (написано четное). Доказательство того, какие остатки, по ММИ все-таки надо приводить.
После решения систем сначала надо привести решения в виде (y, t), а затем уже (x, y). Остальное верно.

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

якобы догадываться до вида формулы.

Почему же "якобы"? Я на самом деле выводил формулу, и для этого мне пришлось брать много значений. Я помнил, что эта формула есть и как она примерно выглядит (то, что это дробь, в числителе какое-то произведение, в знаменателе какое-то число), а саму формулу не помнил.
С4 не легче, чем С5 (для меня).

[VEk]

Новый гость Дело не в том, что Вы так пришли к формуле. При оформлении решения стоило записать: "докажем, что `sum_(k=1)^n k^2 = (n*(n+1)*(2n+1))/6`", и привести ее доказательство. Лишние записи - лишние ошибки.

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

Вы не могли бы расшифровать то, что стоит до знака "="?
Значит, готовиться по книжкам МЦНМО по С1-С4, а С5 и С6 забросить?

[VEk]

Это краткая запись суммы квадратов натуральных чисел от 1 до n.
Забрасывать C5 и C6 не стоит. Но основное внимание все-таки надо уделить задачам с C1 по С4. Опять же, если Вы решаете, скажем диагностические работы в конце сборника C1 за 1.5 часа без ошибок, то можно считать, что этот материал Вы знаете. Аналогично проверка по сборнику C3 (но там за 1 час).
Сборник по С2 имеет чертежи, практически по всем задачам. Это и минус и плюс. Минус в том, что в рамках реального экзамена чертежа не будет. А плюс в том, что школьник по крайней мере видит условие на картинке, и легче воспринимает задачу. Поэтому временные границы по C2 даже сказать не могу. Просто после работы с этим сборником, воспользуйтесь методичкой Корянова АГ.
C4 - это планиметрия, иногда легкая, иногда - гроб с музыкой (или без нее).
Ну и помаленьку решайте С5 и С6, но не очень ими на первых порах не увлекайтесь.
Успехов!

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

Я не совсем понимаю, почему используются две переменные: `n` и `k`.

[VEk]

В этом обозначении переменная k изменяется от 1 до некоторого числа n ( n - верхняя граница). Так удобнее записывать громоздкие выражения.