Задача 1. Допустим, в аквариуме живут осьминоги и морские звёзды. У осьминогов по 8 ног, а у морских звёзд – по 5. Всего конечностей насчитывается 39. Сколько в аквариуме животных?

Решение. Пусть х - количество морских звёзд, у – количество осьминогов. Тогда у всех осьминогов по 8у ног, а у всех звёзд 5х ног. Составим уравнение: 5х + 8у = 39.

Заметим, что количество животных не может выражаться нецелым или отрицательным числами. Следовательно, если х – целое неотрицательное число, то и у=(39 – 5х)/8 должно быть целым и неотрицательным, а, значит, нужно, чтобы выражение 39 – 5х без остатка делилось на 8. Простой перебор вариантов показывает, что это возможно только при х = 3, тогда у = 3. Ответ: (3; 3).

Уравнения, вида ах+bу=с, называются диофантовыми, по имени древнегреческого математика Диофанта Александрийского. Жил Диофант, по-видимому, в 3 в. н. э., остальные известные нам факты его биографии исчерпываются таким стихотворением-загадкой, по преданию выгравированным на его надгробии:

Прах Диофанта гробница покоит; дивись ей и камень

Мудрым искусством его скажет усопшего век.

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

И половину шестой встретил с пушком на щеках.

Только минула седьмая, с подругой он обручился.

С нею, пять лет, проведя, сына дождался мудрец;

Только полжизни отцовской возлюбленный сын его прожил.

Отнят он был у отца ранней могилой своей.

Дважды два года родитель оплакивал тяжкое горе,

Тут и увидел предел жизни печальной своей.

Сколько же лет прожил Диофант Александрийский?

Задача 2. На складе имеются гвозди в ящиках по 16,17 и 40 кг. Может ли кладовщик выдать 100 кг гвоздей, не вскрывая ящики? (метод прямого перебора)

Разберем метод решения относительно одного неизвестного.

Задача 3. В каталоге картинной галереи всего 96 картин. На каких-то страницах расположено 4 картины, а на каких-то 6. Сколько страниц каждого вида есть в каталоге?

Решение. Пусть х – количество страниц с четырьмя картинами,

у – количество страниц с шестью картинами,

Решаем это уравнение относительно того из неизвестных, при котором наименьший (по модулю) коэффициент. В нашем случае это 4х, то есть:

Делим все уравнение на этот коэффициент:

4х=96-6у | :4;

Остатки при делении на 4: 1,2,3. Подставим вместо у эти числа.

Если у=1, то х=(96-6∙1):4=90:4 - Не походит, решение не в целых числах.

Если у=2, то х=(96-6∙2):4=21 – Подходит.

Если у=3, то х=(96-6∙3):4=78:4 - Не походит, решение не в целых числах.

Итак, частным решением является пара (21;2), а это значит, что на 21 странице расположено по 4 картины, а на 2 страницах по 6 картин.

Разберем метод решения с использованием алгоритма Евклида.

Задача 4. В магазине продаётся шоколад двух видов: молочный и горький. Весь шоколад хранится в коробках. Молочного шоколада на складе имеется 7 коробок, а горького 4. Известно, что горького шоколада было на одну плитку больше. Сколько плиток шоколада находятся в коробках каждого вида?

Решение. Пусть х – количество плиток молочного шоколада в одной коробке,

у – количество плиток горького шоколада в одной коробке,

тогда по условию этой задачи можно составить уравнение:

Решим это уравнение, используя алгоритм Евклида.

Выразим 7=4∙1+3, => 3=7-4∙1.

Выразим 4=3∙1+1, => 1=4-3∙1=4-(7-4∙1)=4-7+4∙1=4∙2 -7∙1 =1.

Итак, получается х=1; у=2.

А это значит, что молочный шоколад лежит в коробке по 1 штуке, а горький по 2 штуки.

Разберем метод поиска частного решения и общей формулы решений.

Задача 5. В африканском племени Тумбе-Юмбе два аборигена Тумба и Юмба работают парикмахерами, причем Тумба всегда заплетает своим клиентам по 7 косичек, а Юмба по 4 косички. Сколько клиентов обслужили мастера по отдельности за смену, если известно, что вместе они заплели 53 косички?

Решение. Пусть х – количество клиентов Тумбы,

у – количество клиентов Юмбы,

тогда 7х+4у=53 (1).

Теперь чтобы найти частные решения уравнения (,), заменим данную нам сумму чисел на 1. Это заметно упростит поиск подходящих чисел. Получим:

Решим это уравнение методом подстановки.

4у=1-7х │:4;

Остатки при делении на 4: 1, 2, 3. Подставим вместо х эти числа:

Если х=1, то у=(1-7):4 – не подходит, т.к. решение не в целых числах.

Если х=2, то у=(1-7∙2):4 – не подходит, т.к. решение не в целых числах.

Если х=3, то у=(1-7∙3):4=-5 – подходит.

Затем умножим получившиеся значения на начальное значение суммы, которую мы заменяли на 1, т.е.

х=х 0 ∙53=3∙53=159;

у=у 0 ∙53=-5∙53=-265.

Мы нашли частное решение уравнения(1). Проверим его, подставив начальное уравнение:

7∙159+4∙(-265)=53; (3)

Ответ сошелся. Если бы, мы решали абстрактное уравнение, то можно было бы на этом остановиться. Однако мы решаем задачу, а поскольку Тумба не мог заплести отрицательное число косичек, нам необходимо продолжать решение. Теперь составим формулы для общего решения. Чтобы это сделать вычтем из начального уравнения(1) уравнение с подставленными значениями (3). Получим:

Вынесем общие множители за скобки:

7(х-159)+4(у+265)=0.

Перенесем одно из слагаемых из одной части уравнения в другую:

7(х-159)=-4(у+265).

Теперь стало видно, что чтобы уравнение решалось (х-159) должно делиться на -4, а (у+265) должно делиться на 7. Введем переменную n, которая будет отображать это наше наблюдение:

Перенесем слагаемые из одной части уравнения в другую:

Мы получили общее решение данного уравнения, теперь в него можно подставлять различные числа и получать соответствующие ответы.

Например, пусть n=39, тогда

А это значит, что Тумба заплел косички 3 клиентам, а Юмба 8 клиентам.

Решите задачи различными методами.

Задача 6: Вовочка купил ручки по 8 рублей и карандаши по 5 рублей. Причем за все карандаши он заплатил на 19 рублей больше, чем за все ручки. Сколько ручек и сколько карандашей купил Вовочка? (метод поиска общего решения, решение относительно одного не известного, использование алгоритма Евклида).

Задача 7. Куплены фломастеры по 7 рублей и карандаши по 4 рубля за штуку, всего на сумму 53 рубля. Сколько куплено фломастеров и карандашей?

Задача 8.(муниципальный тур ВОШ 2014-2015 г.) : на планете С в ходу два вида монет: по 16 тугриков и по 27 тугриков. Можно ли с их помощью купить товар, ценой в 1 тугрик?

Задача 9. Шехерезада рассказывает свои сказки великому правителю. Всего она должна рассказать 1001 сказку. Сколько ночей потребуется Шехерезаде, чтобы рассказать все свои сказки, если в какие-то ночи она будет рассказывать по 3 сказки, а в какие-то по 5? За сколько ночей Шехерезада расскажет все свои сказки, если хочет сделать это как можно быстрее? Сколько ночей понадобится Шехерезаде, если ей утомительно рассказывать по пять сказок за ночь, поэтому таких ночей должно быть как можно меньше?

Задача10. (вспомним «Водолея») Как налить 3 литра воды, имея 9-литровую и 5-литровую емкости?

Задача 11. Вовочка отлично успевает по математике. В дневнике у него только пятерки и четверки, причем пятерок больше. Сумма всех Вовочкиных оценок по математике равна 47. Сколько Вовочка получил пятерок и сколько четверок?

Задача 12. Кощей Бессмертный устроил питомник по разведению Змеев Горынычей. В последнем выводке у него есть Змеи о 17-ти головах и о 19-ти головах. Всего этот выводок насчитывает 339 голов. Сколько 17-тиголовых и сколько 19-тиголовых Змеев вывелось у Кощея?

Ответы: Диофант прожил 84 года;

задача 2: 4 ящика по 17 кг и 2 ящика по 16 кг;

задача 6: куплено 7 карандашей и 8 ручек, то есть (7,2) – частное решение и у = 2 + 5n, х = 7 + 8n, где nє Z – общее решение;

задача 7: (-53; 106) – частное решение, х=4n-53, у=-7n+106 – общие решения, при n=14, х=3, у=8, то есть куплено 3фломастера и 8 карандашей;

задача 8: например, заплатить 3 монеты по 27 тугриков и получить сдачу 5 монет по 16 тугриков;

задача 9: (2002; -1001) – частное решение, х=-5 n+2002, у=3n-1001 – общее решение, при n=350, у=49, х=252, то есть 252 ночи по 3 сказки и 49 ночей по 5 сказок - всего 301 ночь; самый быстрый вариант: 2 ночи по три сказки и 199 ночей по 5 сказок - всего 201 ночь; самый долгий вариант: 332 ночи по 3 сказки и 1 ночь 5 сказок - всего 333 ночи.

задача 10: например, 2 раза налить воду 9-тилитровой банкой и 3 раза вычерпать ее 5-тилитровой банкой;

задача 11: Вовочка получил 7 пятерок и 4 четверки;

задача 12: 11 Змеев о 17-ти головах и 8 Змеев о 19-ти головах.

Алгоритмы решений диофантовых уравнений

Алгоритм Евклида

Пример №1 (простой)
Пример №2 (сложный)

Решаем задачи на подбор чисел без подбора

Задача про кур, кроликов и их лапы
Задача про продавщицу и сдачу

По отзывам сибмам, настоящим камнем преткновения в школьном курсе математики не только для учеников, но и для родителей становятся диофантовы уравнения. Что это такое и как их правильно решать? Разобраться нам помогли учитель математики образовательного центра «Горностай» Аэлита Бекешева и кандидат физико-математических наук Юрий Шанько.

Кто такой Диофант?

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

Первым, кто придумал, как можно записать уравнение, был замечательный ученый Диофант Александрийский. Александрия была большим культурным, торговым и научным центром древнего мира. Этот город существует и сейчас, он находится на Средиземноморском побережье Египта.

Жил Диофант, по-видимому, в III веке н.э. и был последним великим математиком античности. До нас дошли два его сочинения — «Арифметика» (из тринадцати книг сохранилось шесть) и «О многоугольных числах» (в отрывках). Творчество Диофанта оказало большое влияние на развитие алгебры, математического анализа и теории чисел.

А ведь вы знаете кое-что о диофантовых уравнениях…

Диофантовы уравнения знают все! Это задачки для учеников младших классов, которые решаются подбором.

” Например, «сколькими различными способами можно расплатиться за мороженое ценой 96 копеек, если у вас есть только копейки и пятикопеечные монеты?»

Если дать диофантовому уравнению общее определение, то можно сказать, что это алгебраическое уравнение с дополнительным условием: все его решения должны быть целыми числами (а в общем случае и рациональными).

” Зачастую мамы (особенно те, кто окончил школу еще при развитом социализме) полагают, что основная цель таких задач - научить детей расплачиваться мелочью за мороженое. И вот, когда они искренне убеждены, что раскладывание мелочи кучками осталось далеко в прошлом, их любимый семиклассник (или восьмиклассник) подходит с неожиданным вопросом: «Мама, как это решать?», и предъявляет уравнение с двумя переменными. Раньше таких задачек в школьном курсе не было (все мы помним, что уравнений должно быть столько же, сколько и переменных), так что мама не-математик нередко впадает в ступор. А ведь это та же самая задача про мелочь и мороженое, только записанная в общем виде!

Кстати, а зачем к ней вдруг возвращаются в седьмом классе? Все просто: цель изучения диофантовых уравнения - дать основы теории целых чисел, которая дальше развивается как в математике, так и в информатике и программировании. Диофантовы уравнения часто встречаются среди задач части «С» единого госэкзамена. Трудность, прежде всего в том, что существует множество методов решения, из которых выпускник должен выбрать один верный. Тем не менее, линейные диофантовы уравнения ax + by = c могут быть решены относительно легко с помощью специальных алгоритмов.

Алгоритмы для решения диофантовых уравнений

Изучение диофантовых уравнения начинается в углубленном курсе алгебры с 7 класса. В учебнике Ю.Н. Макарычева, Н.Г. Миндюка приводятся некоторые задачи и уравнения, которые решают с использованием алгоритма Евклида и метода перебора по остаткам , - рассказывает Аэлита Бекешева. - Позже, в 8 - 9 классе, когда уже рассматриваем уравнения в целых числах более высоких порядков, показываем ученикам метод разложения на множители , и дальнейший анализ решения этого уравнения, оценочный метод . Знакомим с методом выделения полного квадрата . При изучении свойств простых чисел знакомим с малой теоремой Ферма, одной из основополагающих теорем в теории решений уравнений в целых числах. На более высоком уровне это знакомство продолжается в 10 - 11 классах. В это же время мы подводим ребят к изучению и применению теории «сравнений по модулю», отрабатываем алгоритмы, с которыми знакомились в 7 - 9 классах. Очень хорошо это материал прописан в учебнике А.Г. Мордковича «Алгебра и начала анализа, 10 класс» и Г.В. Дорофеева «Математика» за 10 класс.

Алгоритм Евклида

Сам метод Евклида относится к другой математической задаче - нахождению наибольшего общего делителя: вместо исходной пары чисел записывают новую пару - меньшее число и разность между меньшим и большим числом исходной пары. Это действие продолжают до тех пор, пока числа в паре не уравняются - это и будет наибольший общий множитель. Разновидность алгоритма используется и при решении диофантовых уравнений - сейчас мы вместе с Юрием Шанько покажем на примере, как решать задачи "про монетки".

Рассматриваем линейное диофантово уравнение ax + by = c, где a, b, c, x и y — целые числа. Как видите, одно уравнение содержит две переменных. Но, как вы помните, нам нужны только целые корни, что упрощает дело - пары чисел, при которых уравнение верно, можно найти.

Впрочем, диофантовы уравнения не всегда имеют решения. Пример: 4x + 14y = 5. Решений нет, т.к. в левой части уравнения при любых целых x и y будет получаться четное число, а 5 — число нечетное. Этот пример можно обобщить. Если в уравнении ax + by = c коэффициенты a и b делятся на какое-то целое d, а число c на это d не делится, то уравнение не имеет решений. С другой стороны, если все коэффициенты (a, b и c) делятся на d, то на это d можно поделить все уравнение.

Например, в уравнении 4x + 14y = 8 все коэффициенты делятся на 2. Делим уравнение на это число и получаем: 2𝑥 + 7𝑦 = 4. Этот прием (деления уравнения на какое-то число) позволяет иногда упростить вычисления.

Зайдем теперь с другой стороны. Предположим, что один из коэффициентов в левой части уравнения (a или b) равен 1. Тогда наше уравнение уже фактически решено. Действительно, пусть, например, a = 1, тогда мы можем в качестве y взять любое целое число, при этом x = c − by. Если научиться сводить исходное уравнение к уравнению, в котором один из коэффициентов равен 1, то мы научимся решать любое линейное диофантово уравнение!

Я покажу это на примере уравнения 2x + 7y = 4.

Его можно переписать в следующем виде: 2(x + 3y) + y = 4.

Введем новую неизвестную z = x + 3y, тогда уравнение запишется так: 2z + y = 4.

Мы получили уравнение с коэффициентом один! Тогда z — любое число, y = 4 − 2z.

Осталось найти x: x = z − 3y = z − 3(4 − 2z) = 7z − 12.

Пусть z=1. Тогда y=2, x=-5. 2 * (-5)+7 * 2=4

Пусть z=5. Тогда y=-6, x=23. 2 * (23)+7 * (-6)=4

” В этом примере важно понять, как мы перешли от уравнения с коэффициентами 2 и 7 к уравнению с коэффициентами 2 и 1. В данном случае (и всегда!) новый коэффициент (в данном случае - единица) это остаток от деления исходных коэффициентов друг на друга (7 на 2).

В этом примере нам повезло, мы сразу после первой замены получили уравнение с коэффициентом 1. Такое бывает не всегда, но и мы можем повторять предыдущий трюк, вводя новые неизвестные и выписывая новые уравнения. Рано или поздно после таких замен получится уравнение с коэффициентом 1.

Давайте попрообуем решить более сложное уравнение, предлагает Аэлита Бекешева.

Рассмотрим уравнение 13x - 36y = 2.

Шаг №1

36/13=2 (10 в остатке). Таким образом, исходное уравнение можно переписать следующим образом: 13x-13* 2y-10y=2. Преобразуем его: 13(x-2y)-10y=2. Введем новую переменную z=x-2y. Теперь мы получили уравнение: 13z-10y=2.

Шаг №2

13/10=1 (3 в остатке). Исходное уравнение 13z-10y=2 можно переписать следующим образом: 10z-10y+3z=2. Преобразуем его: 10(z-y)+3z=2. Введем новую переменную m=z-y. Теперь мы получили уравнение: 10m+3z=2.

Шаг №3

10/3=3 (1 в остатке). Исходное уравнение 10m+3z=2 можно переписать следующим образом: 3* 3m+3z+1m=2. Преобразуем его: 3(3m+z)+1m=2. Введем новую переменную n=3m+z. Теперь мы получили уравнение: 3n+1m=2.

Ура! Мы получили уравнение с коэффициентом единица!

m=2-3n, причем n может быть любым числом. Однако нам нужно найти x и y. Проведем замену переменных в обратном порядке. Помните, мы должны выразить x и y через n, которое может быть любым числом.

y=z-m; z=n-3m, m=2-3n ⇒ z=n-3* (2-3n), y=n-3*(2-3n)-(2-3n)=13n-8; y=13n-8

x=2y+z ⇒ x=2(13n-8)+(n-3*(2-3n))=36n-22; x=36n-22

Пусть n=1. Тогда y=5, x=24. 13 * (14)-36 * 5=2

Пусть n=5. Тогда y=57, x=158. 13 * (158)-36 * (57)=2

Да, разобраться не очень просто, зато теперь вы всегда сможете решить в общем виде задачи, которые решаются подбором!

Решаем задачи на подбор чисел

Примеры задач для учеников младших классов, которые решаются подбором: посоревнуйтесь с ребенком, кто решит их быстрее: вы, используя алгорит Евклида, или школьник - подбором?

Задача про лапы

Условия

В клетке сидят куры и кролики. Всего у них 20 лап. Сколько там может быть кур, а сколько - кроликов?

Решение

Пусть у нас будет x кур и y кроликов. Составим уравнение: 2х+4y=20. Сократим обе части уравнения на два: x+2y=10. Следовательно, x=10-2y, где x и y - это целые положительные числа.

Ответ

Число кроликов и куриц: (1; 8), (2; 6), (3; 4), (4; 2), (5; 0)

Согласитесь, получилось быстрее, чем перебирать «пусть в клетке сидит один кролик...»

Задача про монетки

Условия

У одной продавщицы были только пяти- и двухрублевые монетки. Сколькими способами она может набрать 57 рублей сдачи?

Решение

Пусть у нас будет x двухрублевых и y пятирублевых монеток. Составим уравнение: 2х+5y=57. Преобразуем уравнение: 2(x+2y)+y=57. Пусть z=x+2y. Тогда 2z+y=57. Следовательно, y=57-2z , x=z-2y=z-2(57-2z) ⇒ x=5z-114 . Обратите внимание, переменная z не может быть меньше 23 (иначе x, число двухрублевых монеток, будет отрицательным) и больше 28 (иначе y, число пятирублевых монеток, будет отрицательным). Все значения от 23 до 28 нам подходят.

Ответ

Шестью способами.

Подготовила Татьяна Яковлева

Линейные диофантовы уравнения

Исследовательская работа по алгебре

ученика 9 класса МОУ «Упшинская ООШ»

Антонова Юрия

«Если вы хотите научиться плавать, то

смело входите в воду, а если хотите

научиться решать задачи, то решайте их.»

Д.Пойя

Руководитель – Софронова Н.А .

Задача

Для настилки пола шириной в 3 метра имеются доски шириной в 11 см и 13 см. Сколько нужно взять досок того и другого размера?

Если х – число досок шириной в 11 см, а у – число досок шириной в 13 см, то нам надо решить уравнение:

11 х + 13 у = 300

Особенности уравнения 11 х + 13 у = 300: ▪ Коэффициенты 11, 13, 300 – целые числа. ▪ Число неизвестных превышает число уравнений. ▪ Решения данного уравнения х и у должны быть целыми положительными числам

Алгебраические уравнения или системы алгебраических уравнений с целыми коэффициентами, в которых число неизвестных превышает число уравнений и для которых надо найти целые решения, называют неопределенными или диофантовыми, по имени греческого математика Диофанта .

Примеры диофантовых уравнений

1 . Найдите все пары целых чисел

x , y , для которых верно равенство

2 . Покажите, что уравнение

имеет бесконечное множество решений

целых числах

Цель работы:

Выяснить:

Какие методы с уществуют для решения диофантовых уравнений?

Задачи:

Найти и и зучить методы решения линейных диофантовых уравнений с двумя переменными.

Рассмотреть возможности теории линейных диофантовых уравнений.

Пифагоровы тройки

Неопределенные уравнения в целых числах решались еще до Диофанта. Большой интерес вызывало, например, алгебраическое уравнение x 2 + y 2 = z 2 , связывающее стороны x , у , z прямоугольного треугольника. Натуральные числа x , y и z , являющиеся решениями этого уравнения, называются "пифагоровыми тройками" .

Уравнение Ферма

К работам Диофанта имеют непосредственное отношение и математические исследования французского математика Пьера Ферма. Считается, что именно с работ Ферма началась новая волна в развитии теории чисел. И одна из его задач - это знаменитое уравнение Ферма

х n + y n = z n

Ни один крупный математик не прошел мимо теории диофантовых уравнений.

Ферма, Эйлер, Лагранж, Гаусс, Чебышев оставили неизгладимый след в этой интересной теории.

1, (Каталана); ах 2 + bxy + су 2 + dx + еу + f = 0 , где а, b , с, d , е, f - целые числа, т. е. общее неоднородное уравнение второй степени с двумя неизвестными (П.Ферма, Дж. Валлис, Л. Эйлер, Ж. Лагранж и К.Гаусс) " width="640"

Примеры неопределенных уравнений решаемых великими математиками 19-го и 20-го столетий: x 2 − ny 2 = 1 , где n не является точным квадратом (Ферма, Пелля); x z − y t = 1 , где z , t 1, (Каталана); ах 2 + bxy + су 2 + dx + еу + f = 0 , где а , b , с , d , е , f - целые числа, т. е. общее неоднородное уравнение второй степени с двумя неизвестными (П.Ферма, Дж. Валлис, Л. Эйлер, Ж. Лагранж и К.Гаусс)

Диофантовы уравнения в 20 веке

1900 год. Международный математический конгресс.

10-я проблема Гильберта

Задано Диофантово уравнение с некоторым числом неизвестных и рациональными целыми коэффициентами. Необходимо придумать процедуру, которая могла определить за конечное число операций – является ли уравнение разрешимым в рациональных целых числах.

Русский математик Юрий Матиясевич доказал :

10-ая проблема Гильберта неразрешима - требуемого в ней алгоритма не существует.

Всегда ли можно найти для конкретного неопределенного уравнения все целые решения или доказать отсутствие таковых?

Проблема решения уравнений в целых числах решена до конца только для уравнений первой степени с двумя или тремя неизвестными.
ДУ второй степени с двумя неизвестными решаются уже с большим трудом.
ДУ второй степени с числом неизвестных больше двух решены лишь в отдельных частных случаях, например уравнение x 2 + y 2 = z 2 .
ДУ степени выше второй имеют, как правило, лишь конечное число решений (в целых числах).
Для уравнений выше второй степени с двумя или более неизвестными достаточно трудной является даже задача существования целочисленных решений. Например, неизвестно, имеет ли уравнение

x 3 + y 3 + z 3 = 30 хотя бы одно целочисленное решение.

Для решения отдельных ДУ, а иногда и для конкретных уравнений, приходится изобретать новые методы. Очевидно, что алгоритма, который позволял бы находить решения произвольных ДУ не существует.

Линейные диофантовы уравнения

Общий вид:

ЛДУ с двумя переменными:

a х + by = c

ЛДУ с тремя переменными:

a х + by + cz = d

ЛДУ с двумя неизвестными

ЛДУ с двумя переменными:

a х + by = c

Решения:

x = х 0 - bt

у = у 0 + at

Однородные:

a х + by = 0

Решения:

x = - bt

у = at

Поиск частного решения

Методы решения:

Метод кратных.
Применение алгоритма Евклида.
Метод перебора.
Метод спуска.

Метод рассмотрения остатков от деления

Метод кратных

Решить уравнение 11 х + 2 у = 69

Ищем сумму, равную 69: 55 + 14 = 69 Частное решение уравнения

х 0 = 5, у 0 = 7

Применение алгоритма Евклида

Решить уравнение 4 х + 7 у = 16

Найдем НОД чисел 4 и 7 по алгоритму Евклида: НОД(4,7) = 1

Выразим число 1 через коэффициенты а = 4 и b =7, используя теорему о линейном разложении НОД:

НОД ( а, b ) = au + bv .

Получим: 1 = 4 ∙ 2 + 7 ∙ (-1) u = 2, v = -1

Частное решение уравнения: х 0 = 2 ∙ 16 = 32,

у 0 = -1 ∙ 16 = -16

Метод перебора

Решить уравнение 7 х + 12 у = 100

7х + 12у = 100
7х = 100 – 12у
100 – 12у кратно 7

Частное решение уравнения: х 0 = 4, у 0 = 6

100-12у

Метод спуска: 3х+8у=60

Выразим

переменную х

через у

Выразим

переменную х

через t

Ответ:

Проверка:

Метод рассмотрения остатков от деления

Решить в целых числах уравнение 3х – 4у = 1
3 х = 4 у + 1
Левая часть уравнения делится на 3, значит и правая должна делиться на 3. При делении на 3 могут получиться остатки 0, 1, и 2.
Рассмотрим 3 случая.

3 x = 4 ∙ 3p + 1 = 12 p + 1

y = 3p + 1

Не делится на 3

3 x = 4 ∙ (3p + 1) +1 = 12 p + 3

y = 3p + 2

Не делится на 3

3 x = 4 ∙ (3p + 2) +1 = 12 p + 9

3 x = 3 (4 p + 3)

x = 4 p + 3

Ответ:

Делится на 3

x = 4 p + 3 ; y = 3p + 2

Возможности теории ЛДУ Найти все целочисленные решения уравнения х 2 + 5y 2 + 34z 2 + 2ху - 10xz - 22уz =0

Что дала мне работа над проектом?

Получил представление о работе над исследовательским проектом.
Познакомился с историей развития диофантовых уравнений и биографией Диофанта.
Изучил методы решения ЛДУ с двумя и тремя неизвестными.
решил группу задач, которые носят практический характер, а также встречаются на олимпиадах, экзаменах за курс основной школы
Приобрел навыки решения нестандартных задач.

Думаю, что в последующем я продолжу изучение диофантовых уравнений второй степени и методов их решения.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Математика в понятиях, определениях и терминах. Ч.1. Пособие для учителей. Под ред. Л.В.Сабинина. М., «Просвещение», 1978. -320 с. (Библиотека учителя математики.) На обороте тит.л.авт.: О.В.Мантуров, Ю.К.Солнцев, Ю.И.Сорокин, Н.Г.Федин.
Нагибин Ф.Ф., Канин Е.С. Математическая шкатулка: Пособие для учащихся. – 4-е изд., перераб. и доп. - М.: Просвещение, 1984. – 160с., ил.
Н.П.Тучнин. Как задать вопрос? (О математическом творчестве школьников): Книга для учащихся. – М.: Просвещение, 1993. – 192с., ил.
С.Н.Олехник, Ю.В.Нестеренко, М.К.Потапов Старинные занимательные задачи. –М.: Дрофа, 2002. -176с., ил.
Я.И.Перельман. Занимательная алгебра. – М.: Наука, 1975г. – 200с., ил.
Электорнный ресурс: http :// www.yugzone.ru /x/ diofant-i-diofantovy-uravneniya / И.Г.Башмакова «Диофант и диофантовы уравнения».
Электорнный ресурс: http :// www.goldenmuseum.com /1612Hilbert_rus.html 10-я проблема Гильберта: история математического открытия (Диофант, Ферма, Гильберт, Джулия Робинзон, Николай Воробьев, Юрий Матиясевич).
Электорнный ресурс: http://ru.wikipedia.org/wiki/ Диофантовы уравнения.
Электорнный ресурс: http :// revolution.allbest.ru / mathematics /d00013924.html Белов Денис Владимирович Линейные диофантовы уравнения.
Электорнный ресурс: http :// revolution.allbest.ru / mathematics /d00063111.html Линейные диофантовы уравнении
Электорнный ресурс: http ://portfolio.1september.ru/work.php?id=570768 Зюрюкина Ольга. Неопределенные уравнения в целых числах или диофантовы уравнения.
Электорнный ресурс: http ://portfolio.1september.ru/work.php?id=561773 Арапов Александр. Диофант и его уравнения.
Электорнный ресурс: http :// ru.wikipedia.org / wiki / Алгоритм Евклида.

Чтобы решить линейное диофантово уравнение, нужно найти значения переменных «x» и «y», которые являются целыми числами. Целочисленное решение сложнее обычного и требует определенного набора действий. Сначала необходимо вычислить наибольший общий делитель (НОД) коэффициентов, а затем найти решение. Если вы нашли одно целочисленное решение линейного уравнения, можно применить простой шаблон, чтобы найти бесконечное множество других решений.

Шаги

Часть 1

Как записать уравнение

Запишите уравнение в стандартной форме. Линейное уравнение - это уравнение, в котором показатели степени переменных не превышают 1. Чтобы решить такое линейное уравнение, сначала запишите его в стандартной форме. Стандартная форма линейного уравнения выглядит так: A x + B y = C {\displaystyle Ax+By=C} , где A , B {\displaystyle A,B} и C {\displaystyle C} - целые числа.

Упростите уравнение (если можно). Когда вы запишете уравнение в стандартной форме, посмотрите на коэффициенты A , B {\displaystyle A,B} и C {\displaystyle C} . Если у этих коэффициентов есть НОД, разделите на него все три коэффициента. Решение такого упрощенного уравнения также будет решением исходного уравнения.

Проверьте, можно ли решить уравнение. В некоторых случаях можно сразу заявить, что уравнение не имеет решений. Если коэффициент «С» не делится на НОД коэффициентов «А» и «В», у уравнения нет решений.

Часть 2

Как записать алгоритм Евклида

Уясните алгоритм Евклида. Это ряд повторных делений, в котором предыдущий остаток используется как следующий делитель. Последний делитель, который делит числа нацело, является наибольшим общим делителем (НОД) двух чисел.

Примените алгоритм Евклида к коэффициентам «A» и «B». Когда вы запишете линейное уравнение в стандартной форме, определите коэффициенты «A» и «B», а затем примените к ним алгоритм Евклида, чтобы найти НОД. Например, дано линейное уравнение 87 x − 64 y = 3 {\displaystyle 87x-64y=3} .

Найдите наибольший общий делитель (НОД). Поскольку последним делителем было число 1, НОД 87 и 64 равен 1. Таким образом, 87 и 64 являются простыми числами по отношению друг к другу.

Проанализируйте полученный результат. Когда вы найдете НОД коэффициентов A {\displaystyle A} и B {\displaystyle B} , сравните его с коэффициентом C {\displaystyle C} исходного уравнения. Если C {\displaystyle C} делится на НОД A {\displaystyle A} и B {\displaystyle B} , уравнение имеет целочисленное решение; в противном случае у уравнения нет решений.

Часть 3

Как найти решение с помощью алгоритма Евклида

Пронумеруйте шаги вычисления НОД. Чтобы найти решение линейного уравнения, нужно использовать алгоритм Евклида в качестве основы процесса подстановки и упрощения.

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

Изолируйте остаток предыдущего шага. Этот процесс представляет собой пошаговое «перемещение вверх». Каждый раз вы будете изолировать остаток в уравнении предыдущего шага.

Сделайте замену и упростите. Обратите внимание, что уравнение шага 6 содержит число 2, а в уравнении шага 5 число 2 изолировано. Поэтому вместо «2» в уравнении шага 6 подставьте выражение шага 5:

Повторите процесс подстановки и упрощения. Повторите описанный процесс, перемещаясь по алгоритму Евклида в обратном порядке. Каждый раз вы будете переписывать уравнение предыдущего шага и подставлять его в последнее полученное уравнение.

Продолжите процесс подстановки и упрощения. Этот процесс будет повторяться до тех пор, пока вы не достигнете первоначального шага алгоритма Евклида. Цель процесса - записать уравнение с коэффициентами 87 и 64 исходного уравнения, которое нужно решить. В нашем примере:
- 1 = 2 (18) − 7 (5) {\displaystyle 1=2(18)-7(5)}
- 1 = 2 (18) − 7 (23 − 18) {\displaystyle 1=2(18)-7(23-18)} (подставили выражение из шага 3)
- 1 = 9 (64 − 2 ∗ 23) − 7 (23) {\displaystyle 1=9(64-2*23)-7(23)} (подставили выражение из шага 2)
- 1 = 9 (64) − 25 (87 − 64) {\displaystyle 1=9(64)-25(87-64)} (подставили выражение из шага 1)

Министерство образования и науки Российской Федерации

Государственное образовательное учреждение высшего

профессионального образования

«Тобольская государственная социально-педагогическая академия

им. Д.И. Менделеева»

Кафедра математики, ТиМОМ

Некоторые диофантовы уравнения

Курсовая работа

студента III курса ФМФ

Матаева Евгения Викторовича

Научный руководитель:

к.ф.-м.н.Валицкас А.И.

Оценка: ____________

Тобольск – 2011

Введение……………………………………………………………………........ 2

§ 1. Линейные диофантовы уравнения………………………………….. 3

§ 2. Диофантово уравнение x 2 – y 2 = a ………………………………….....9

§ 3. Диофантово уравнение x 2 + y 2 = a …………………………………... 12

§ 4. Уравнение х 2 + х + 1 = 3у 2 …………………………………………….. 16

§ 5. Пифагоровы тройки………………………………………………….. 19

§ 6. Великая теорема Ферма………………………………………………23

Заключение……………………………………………………………….….....29

Список литературы........... ………………………………………………..30

ВВЕДЕНИЕ

Диофантово уравнение – это уравнение вида P (x 1 , … , x n ) = 0 , где левая часть представляет собой многочлен от переменных x 1 , … , x n с целыми коэффициентами. Любой упорядоченный набор (u 1 ; … ; u n ) целых чисел со свойством P (u 1 , … , u n ) = 0 называется (частным) решением диофантова уравнения P (x 1 , … , x n ) = 0 . Решить диофантово уравнение – значит найти все его решения, т.е. общее решение этого уравнения.

Нашей целью будет научиться находить решения некоторых диофантовых уравнений, если эти решения имеется.

Для этого, необходимо ответить на следующие вопросы:

а. Всегда ли диофантово уравнение имеет решение, найти условия существования решения.

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

Примеры: 1. Диофантово уравнение 5 x – 1 = 0 не имеет решений.

2. Диофантово уравнение 5 x – 10 = 0 имеет решение x = 2 , которое является единственным.

3. Уравнение ln x – 8 x 2 = 0 не является диофантовым.

4. Часто уравнения вида P (x 1 , … , x n ) = Q (x 1 , … , x n ) , где P (x 1 , … , x n ) , Q (x 1 , … , x n ) – многочлены с целыми коэффициентами, также называют диофантовыми. Их можно записать в виде P (x 1 , … , x n ) – Q (x 1 , … , x n ) = 0 , который является стандартным для диофантовых уравнений.

5. x 2 – y 2 = a – диофантово уравнение второй степени с двумя неизвестными x и y при любом целом a. Оно имеет решения при a = 1 , но не имеет решений при a = 2 .

§ 1. Линейные диофантовы уравнения

Пусть a 1 , … , a n , с Z . Уравнение вида a 1 x 1 + … + a n x n = c называется линейным диофантовым уравнением с коэффициентами a 1 , … , a n , правой частью c и неизвестными x 1 , … , x n . Если правая часть с линейного диофантова уравнения нулевая, то такое диофантово уравнение называется однородным.

Наша ближайшая цель – научиться находить частные и общие решения линейных диофантовых уравнений с двумя неизвестными. Очевидно, что любое однородное диофантово уравнение a 1 x 1 + … + a n x n = 0 всегда имеет частное решение (0; … ; 0).

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

Теорема (о существовании решения линейного диофантова уравнения). Линейное диофантово уравнение a 1 x 1 + … + a n x n = c , не все коэффициенты которого равны нулю, имеет решение тогда и только тогда, когда НОД(a 1 , … , a n ) | c.

Доказательство. Необходимость условия очевидна: НОД(a 1 , … , a n ) | a i (1 i n ) , так что НОД(a 1 , … , a n ) | (a 1 x 1 + … + a n x n ) , а значит, делит и

c = a 1 x 1 + … + a n x n .

Пусть D = НОД(a 1 , … , a n ) , с = Dt и a 1 u 1 + … + a n u n = D – линейное разложение наибольшего общего делителя чисел a 1 , … , a n . Умножая обе части на t , получим a 1 (u 1 t ) + … + a n (u n t ) = Dt = c , т.е. целочисленная

n -ка (x 1 t ; … ; x n t) является решением исходного уравнения с n неизвестными.

Теорема доказана.

Эта теорема даёт конструктивный алгоритм для нахождения частных решений линейных диофантовых уравнений.

Примеры: 1. Линейное диофантово уравнение 12x+21y = 5 не имеет решений, поскольку НОД(12, 21) = 3 не делит 5 .

2. Найти частное решение диофантова уравнения 12x+21y = 6 .

Очевидно, что теперь НОД(12, 21) = 3 | 6 , так что решение существует. Запишем линейное разложение НОД(12, 21) = 3 = 122 + 21(–1) . Поэтому пара (2; –1) – частное решение уравнения 12x+21y = 3 , а пара (4; –2) – частное решение исходного уравнения 12x+21y = 6 .

3. Найти частное решение линейного уравнения 12x + 21y – 2z = 5 .

Так как (12, 21, –2) = ((12, 21), –2) = (3, –2) = 1 | 5 , то решение существует. Следуя доказательству теоремы, вначале найдём решение уравнения (12,21)х–2у=5 , а затем, подставив линейное разложение наибольшего общего делителя из предыдущей задачи, получим решение исходного уравнения.

Для решения уравнения 3х – 2у = 5 запишем линейное разложение НОД(3, –2) = 1 = 31 – 21 очевидно. Поэтому пара чисел (1; 1) является решением уравнения 3 x – 2 y = 1 , а пара (5; 5) – частным решением диофантова уравнения 3х – 2у = 5 .

Итак, (12, 21)5 – 25 = 5 . Подставляя сюда найденное ранее линейное разложение (12, 21) = 3 = 122 + 21(–1) , получим (122+21(–1))5 – 25 = 5 , или 1210 + 21(–5) – 25 = 5 , т.е. тройка целых чисел (10; –5; 5) является частным решением исходного диофантова уравнения 12x + 21y – 2z = 5 .

Теорема (о структуре общего решения линейного диофантова уравнения). Для линейного диофантова уравнения a 1 x 1 + … + a n x n = c справедливы следующие утверждения:

(1) если = (u 1 ; … ; u n ), = (v 1 ; … ; v n ) – его частные решения, то разность (u 1 – v 1 ; … ; u n – v n ) – частное решение соответствующего однородного уравнения a 1 x 1 + … + a n x n = 0 ,

(2) множество частных решений линейного диофантова однородного уравнения a 1 x 1 + … + a n x n = 0 замкнуто относительно сложения, вычитания и умножения на целые числа,

(3) если M – общее решение данного линейного диофантова уравнения, а L – общее решение соответствующего ему однородного диофантова уравнения, то для любого частного решения = (u 1 ; … ; u n ) исходного уравнения верно равенство M = + L .

Доказательство. Вычитая равенство a 1 v 1 + … + a n v n = c из равенства a 1 u 1 + … + a n u n = c , получим a 1 (u 1 – v 1 ) + … + a n (u n – v n ) = 0 , т. е. набор

(u 1 – v 1 ; … ; u n – v n ) – частное решение линейного однородного диофантова уравнения a 1 x 1 + … + a n x n = 0 . Таким образом, доказано, что

= (u 1 ; … ; u n ), = (v 1 ; … ; v n ) M L .

Это доказывает утверждение (1).

Аналогично доказывается утверждение (2):

, L z Z L z L .

Для доказательства (3) вначале заметим, что M + L . Это следует из предыдущего: M+L .

Обратно, если = (l 1 ; … ; l n ) L и = (u 1 ; … ; u n ) M , то M :

a 1 (u 1 + l 1 )+ …+a n (u n + l n ) = (a 1 u 1 + … + a n u n )+(a 1 l 1 + … + a n l n ) = c + 0 = c .

Таким образом, + L M , и в итоге M = + L .

Теорема доказана.

Доказанная теорема имеет наглядный геометрический смысл. Если рассмотреть линейное уравнение a 1 x 1 + … + a n x n = c , где х i R , то как известно из геометрии, оно определяет в пространстве R n гиперплоскость, полученную из плоскости L c однородным уравнением a 1 x 1 + … +a n x n =0 , проходящей через начало координат, сдвигом на некоторый вектор R n . Поверхность вида + L называют также линейным многообразием с направляющим пространством L и вектором сдвига . Таким образом, доказано, что общее решение М диофантова уравнения a 1 x 1 + … + a n x n = c состоит из всех точек некоторого линейного многообразия, имеющих целые координаты. При этом координаты вектора сдвига тоже целые, а множество L решений однородного диофантова уравнения a 1 x 1 + … + a n x n = 0 состоит из всех точек направляющего пространства с целыми координатами. По этой причине часто говорят, что множество решений произвольного диофантова уравнения образует линейное многообразие с вектором сдвига и направляющим пространством L .

Пример: для диофантова уравнения х – у = 1 общее решение M имеет вид (1+у; у), где у Z , его частное решение = (1; 0) , а общее решение L однородного уравнения х – у = 0 запишется в виде (у; у) , где у Z . Таким образом, можно нарисовать следующую картинку, на которой решения исходного диофантова уравнения и соответствующего однородного диофантова уравнения изображены жирными точками в линейном многообразии М и пространстве L соответственно.

2. Найти общее решение диофантова уравнения 12x + 21y – 2z = 5 .

Частное решение (10; –5; 5) этого уравнения было найдено ранее, найдём общее решение однородного уравнения 12x + 21y – 2z = 0 , эквивалентного диофантову уравнению 12 x + 21 y = 2 z .

Для разрешимости этого уравнения необходимо и достаточно выполнение условия НОД(12, 21) = 3 | 2z, т.е. 3 | z или z = 3t для некоторого целого t . Сокращая обе части на 3 , получим 4x + 7y = 2t . Частное решение (2; –1) диофантова уравнения 4x + 7y = 1 найдено в предыдущем примере. Поэтому (4t ; –2t) – частное решение уравнения 4x + 7y = 2t при любом

t Z . Общее решение соответствующего однородного уравнения

(7 u ; –4 u ) уже найдено. Таким образом, общее решение уравнения 4x + 7y = 2t имеет вид: (4t + 7 u ; –2t – 4 u ) , а общее решение однородного уравнения 12x + 21y – 2z = 0 запишется так:

(4t + 7 u ; –2t – 4 u ; 3t) .

Нетрудно убедиться, что этот результат соответствует сформулированной выше без доказательства теореме о решениях однородного диофантова уравнения а 1 х 1 + … + а n х n = 0 : если Р = , то Р и

(u ; t ) P – общее решение рассматриваемого однородного уравнения.

Итак, общее решение диофантова уравнения 12x + 21y – 2z = 5 выглядит так: (10 + 4t + 7 u ; –5 – 2t – 4 u ; 5 + 3t) .

3. На примере предыдущего уравнения проиллюстрируем другой метод решения диофантовых уравнений от многих неизвестных, который состоит в последовательном уменьшении максимального значения модулей его коэффициентов.

12x + 21y – 2z = 5 12x + (102 + 1)y – 2z = 5

12x + y – 2(z – 10y) = 5

Таким образом, общее решение рассматриваемого уравнения можно записать и так: (x; 5 – 12x + 2u ; 50 – 120x + 21u) , где x, u – произвольные целые параметры.

§ 2. Диофантово уравнение x 2 – y 2 = a

Примеры: 1. При a = 0 получаем бесконечное число решений: x = y или x = – y для любого y Z .

2. При a = 1 имеем x 2 – y 2 = 1 (x + y )(x – y ) = 1 . Таким образом, число 1 разложено в произведение двух целых множителей x + y и x – y (важно, что x , y – целые!). Поскольку у числа 1 всего два разложения в произведение целых множителей 1 = 11 и 1 = (–1)(–1) , то получаем две возможности: .

3. Для a = 2 имеем x 2 – y 2 = 2 (x + y )(x – y ) = 2. Действуя аналогично предыдущему, рассматриваем разложения

2=12=21=(–1)(–2)=(–2)(–1), составляем системы: , которые, в отличие от предыдущего примера, не имеют решений. Так что нет решений и у рассматриваемого диофантова уравнения x 2 – y 2 = 2.

4. Предыдущие рассмотрения наводят на некоторые выводы. Решения уравнения x 2 – y 2 = a находятся по разложению a = km в произведение целых чисел из системы . Эта система имеет целые решения тогда и только тогда, когда k + m и k – m чётны, т.е. когда числа k и m одной чётности (одновременно чётны или нечётны). Таким образом, диофантово уравнение x 2 – y 2 = a имеет решение тогда и только тогда, когда a допускает разложение в произведение двух целых множителей одной чётности. Остаётся только найти все такие a .

Теорема (об уравнении x 2 – y 2 = a ). (1) Уравнение x 2 – y 2 = 0 имеет бесконечное множество решений .

(2) Любое решение уравнения получается имеет вид , где a = km – разложение числа a в произведение двух целых множителей одной чётности.

(3) Уравнение x 2 – y 2 = a имеет решение тогда и только тогда, когда a 2 (mod 4).

Доказательство. (1) уже доказано.

(2) уже доказано.

(3) () Пусть вначале диофантово уравнение x 2 – y 2 = a имеет решение. Докажем, что a 2 (mod 4) . Если a = km – разложение в произведение целых чисел одной чётности, то при чётных k и m имеем k = 2 l , m = 2 n и a = km = 4 ln 0 (mod 4) . В случае же нечётных k , m их произведение a также нечётно, разность a – 2 нечётна и не делится на 4 , т.е. снова

a 2 (mod 4).

() Если теперь a 2 (mod 4) , то можно построить решение уравнения x 2 – y 2 = a . Действительно, если a нечётно, то a = 1 a – разложение в произведение целых нечётных чисел, так что – решение диофантова уравнения. Если же a чётно, то ввиду a 2 (mod 4) получаем, что 4 | a , a = 4 b = 2(2 b ) – разложение в произведение целых чётных чисел, так что – решение диофантова уравнения.

Теорема доказана.

Примеры: 1. Диофантово уравнение x 2 – y 2 = 2012 не имеет решений, т.к. 2010 = 4502 + 2 2 (mod 4).

2. Диофантово уравнение x 2 – y 2 = 2011 имеет решения, т.к.

2011 3 (mod 4). Имеем очевидные разложения

2011 = 12011 = 20111 = (–1)(–2011) = (–2011)(–1),

по каждому из которых находим решения (комбинации знаков любые). Других решений нет, т.к. число 2011 простое (?!).

§ 3. Диофантово уравнение x 2 + y 2 = a

Примеры: 1. 0 = 0 2 + 0 2 , 1 = 0 2 + 1 2 , k 2 = 0 2 + k 2 . Таким образом, очевидно, любой квадрат тривиальным образом представим в виде суммы двух квадратов.

2. 2 = 1 2 + 1 2 , 5 = 1 2 + 2 2 , 8 = 2 2 + 2 2 , 10 = 1 2 + 3 2 , 13 = 2 2 + 3 2 , 17 = 1 2 + 4 2 , 18 = 3 2 + 3 2 , 20 = 2 2 + 4 2 , …

3. Решений нет для a = 3, 6 = 23, 7, 11, 12 = 2 2 3, 14 = 27, 15 = 35, 19, 21 = 37, 22 = 211, 23, 24 = 32 3 , …

Анализ приведённых результатов способен навести на мысль, что отсутствие решений каким-то образом связано с простыми числами вида

4 n +3 , присутствующими в разложении на множители чисел, не представимых в виде сумм двух квадратов.

Теорема (о представлении натуральных чисел суммами двух квадратов). Натуральное число a представимо в виде суммы двух квадратов тогда и только тогда, когда в его каноническом разложении простые числа вида 4 n + 3 имеют чётные показатели степеней.

Доказательство. Вначале докажем, что если натуральное число a представимо в виде суммы двух квадратов, то в его каноническом разложении все простые числа вида 4 n + 3 должны иметь чётные показатели степеней. Предположим, вопреки доказываемому, что a = р 2 k +1 b = x 2 + y 2 , где

р – простое число вида 4 n +3 и b p . Представим числа х и у в виде

х = Dz , y = Dt , где D = НОД(x , y ) = р s w , p w ; z , t , s N 0 . Тогда получаем равенство р 2 k +1 b = D 2 (z 2 + t 2 ) = р 2 s w 2 (z 2 + t 2 ) , т.е. р 2( k – s )+1 b = w 2 (z 2 + t 2 ) . В левой части равенства присутствует p (нечётная степень не равна нулю), значит, на простое число p делится один из множителей в правой части. Поскольку p w , то р | (z 2 + t 2 ) , где числа z , t взаимно просты. Это противоречит следующей лемме (?!).

Лемма (о делимости суммы двух квадратов на простое число вида

4 n + 3 ). Если простое число р = 4 n +3 делит сумму квадратов двух натуральных чисел, то оно делит каждое из этих чисел.

Доказательство. От противного. Пусть x 2 + y 2 0(mod p ) , но x 0(mod p ) или y 0 (mod p ) . Поскольку x и y симметричны, их можно менять местами, так что можно предполагать, что x p .

Лемма (об обратимости по модулю p ). Для любого целого числа x , не делящегося на простое число p , существует обратный элемент по модулю p – такое целое число 1 u < p , что xu 1 (mod p ).

Доказательство. Число x взаимно простое с p , поэтому можно записать линейное разложение НОД(x , p ) = 1 = xu + pv (u , v Z ) . Ясно, что xu 1(modp ) , т.е. u – обратный элемент к x по модулю p . Если u не удовлетворяет ограничению 1 u < p , то поделив u с остатком на p , получим остаток r u (mod p ) , для которого xr xu 1 (mod p ) и 0 r < p .

Лемма об обратимости по модулю p доказана.

Умножая сравнение x 2 + y 2 0 (mod p ) на квадрат u 2 обратного элемента к x по модулю p , получим 0 = 0u 2 x 2 u 2 + y 2 u 2 = (xu) 2 + (yu) 2 1 + t 2 (mod p).

Таким образом, для t = yu выполнено сравнение t 2 –1 (mod p ) , которое и приведём к противоречию. Ясно, что t p : иначе t 0 (mod p ) и 0 t 2 –1 (mod p ) , что невозможно. По теореме Ферма имеем t p –1 1 (mod p ), что вместе с t 2 –1 (mod p ) и p = 4 n + 3 приводит к противоречию:

1 t p–1 = t 4n+3–1 = t 2(2n+1) = (t 2 ) 2n+1 (–1) 2n+1 = –1 (mod p).

Полученное противоречие показывает, что допущение о x 0 (mod p ) было не верным.

Лемма о делимости суммы двух квадратов на простое число 4 n +3 доказана.

Таким образом, доказано, что число, в каноническое разложение которого входит простое число p = 4 n + 3 в нечётной степени, не представимо в виде суммы двух квадратов.

Докажем теперь, что любое число, в каноническом разложении которого простые числа p = 4 n + 3 участвуют только в чётных степенях, представимо в виде суммы двух квадратов.

Идея доказательства основана на следующем тождестве:

(а 2 + b 2 )(c 2 + d 2 ) = (ac – bd) 2 + (ad + bc) 2 ,

которое можно получить из известного свойства модуля комплексных чисел – модуль произведения равен произведению модулей. Действительно,

| z || t | = | zt | | a + bi || c + di | = |(a + bi )(c + di )|

|a + bi| 2 |c + di| 2 = |(ac – bd) + (ad + bc)i| 2

(а 2 + b 2 )(c 2 + d 2 ) = (ac – bd) 2 + (ad + bc) 2 .

Из этого тождества следует, что если два числа u, v представимы в виде суммы двух квадратов: u = x 2 + y 2 , v = z 2 + t 2 , то и их произведение uv представимо в виде суммы двух квадратов: uv = (xz – yt ) 2 + (xt + yz ) 2 .

Любое натуральное число a > 1 можно записать в виде a = р 1 … р k m 2 , где р i – попарно различные простые числа, m N . Для этого достаточно найти каноническое разложение , записать каждую степень вида r в виде квадрата (r ) 2 при чётном = 2, или в виде r = r (r ) 2 при нечётном = 2 + 1 , а затем сгруппировать отдельно квадраты и оставшиеся одиночные простые числа. Например,

29250 = 23 2 5 3 13 = 2513(35) 2 , m = 15.

Число m 2 обладает тривиальным представлением в виде суммы двух квадратов: m 2 = 0 2 + m 2 . Если доказать представимость в виде суммы двух квадратов всех простых чисел р i (1 i k ) , то используя тождество, будет получено и представление числа a. По условию, среди чисел р 1 , … , р k могут встретиться только 2 = 1 2 + 1 2 и простые числа вида 4 n + 1 . Таким образом, осталось получить представление в виде суммы двух квадратов простого числа р = 4т + 1 . Это утверждение выделим в отдельную теорему (см. ниже)

Например, для a = 29250 = 2513(15) 2 последовательно получаем:

2 = 1 2 + 1 2 , 5 = 1 2 + 2 2 , 13 = 2 2 + 3 2 ,

25 = (11 – 12) 2 + (12 + 11) 2 = 1 2 + 3 2 ,

2513 = (12 – 33) 2 + (13 + 32) 2 = 7 2 + 9 2 ,

29250 = 2513(15) 2 = (715) 2 + (915) 2 = 105 2 + 135 2 .

Теорема доказана.

§ 4. Уравнение х+ х + 1 = 3у

Займемся теперь уравнением х+x+1=Зу. Оно уже имеет свою историю. В 1950 г. Р. Облат высказал предположение, что, кроме решения

x =у=1 . оно не имеет иных решений в натуральных числах х, у , где х есть нечетное число. В том же году Т. Нагель указал решение x = 313, у =181. Метод, аналогичный изложенному выше для уравнения х+х-2у=0 , позволит нам определить все решения уравнения x +х+1=3у (1)

в натуральных числах x , у. Предположим, что (х, у) есть решение уравнения (1) в натуральных числах, причем х > 1 . Можно легко убедиться, что уравнение(18) не имеет решений в натуральных числах x , у , где х = 2, 3. 4, 5, 6, 7, 8, 9; поэтому должно быть х10.

Покажем, что 12у<7 x +3, 7у>4 x + 2. 4у> 2 x +1 . (2)

Если бы было 12y > 7x+3 , мы имели бы 144у > 49 x +42 x +9 . а так как, в виду (18), 144у= 48 x + 48 x + 48 , то было бы х < 6 x +3 9, откуда

(х-З) < 48 и, значит, учитывая, что x > 10, 7 < 148 , что невозможно. Итак, первое из неравенств (2) доказано.

Если бы было 7у < 4 x +2 , мы имели бы 49у < 16 x + 16 x +4 , а так как, ввиду (1), 16 x + 16 x + 16 = 48у , то было бы 49у < 48у- 12 , что невозможно. Таким образом, доказано второе из неравенств (2), из которого уже непосредственно вытекает третье. Итак, неравенства (2) верны.

Положим теперь

w = 7х - 12у+3, h = -4 x + 7у-2 . (3)

На основании (2), найдем, что w > 0 , h > 0 и х - w =3(4 y -2 x -1)>0 и, значит, w <х . Согласно (3), имеем w 2 + w +1=3 h 2 откуда, ввиду (1), Примем g(x, у) = (7х- 12у + 3, -4x + 7у -2) .

Итак, можно сказать, что, исходя из любого решения (х, у) уравнения (1) в натуральных числах, где х > 1 , мы получаем новое решение (w , h ) = g(x, у) уравнения (1) в натуральных числах w , h где w < х (и значит, решение в меньших натуральных числах). Отсюда, действуя как выше, найдем, что для каждого решения уравнения (1) в натуральных числах х, у , где х > 1 , существует натуральное число n такое, что g(x, y) = (l, 1).

Приняв же f(x, у) = (7 x +12у + 3, 4 x + 7у + 2) , (4) легко найдем, что f(g(x,y)) = (x, у) и, следовательно, (x , y ) = f (1,1) С другой стороны, легко проверить, что если (х, у) есть решение уравнения (1) в натуральных числах, то f (x , y ) также есть решение уравнения (1) в натуральных числах (соответственно больших, чем х и у ).

Приняв x=y=1(x, y) = f(1, 1) для n =2,3,…..,

получим последовательность { x , y } для n = 1, 2,….., содержащую все решения уравнения (1) в натуральных числах и только такие решения.

Здесь мы имеем (х, y )= f (1,1)= f (x, y), следовательно, в силу (4), получаем

х= 7 x +12 y+3, y =4 x+7 y+2 (5) (n =1, 2, ...)

Формулы, позволяющие последовательно определять все решения (х, у) уравнения (1) в натуральных числах. Таким путем легко получаем решения (1,1),(22,13),(313,181),.(4366,2521),(60817,35113),..

Этих решений имеется, очевидно, бесконечное множество. Из равенств

х= у= 1 и (4) при помощи индукции легко находим, что числа х с нечетными индексами суть нечетные, с четными же - четные, а числа y суть нечетные для n = 1, 2, ... Для получения всех решений уравнения (1) в целых числах х, у , как нетрудно доказать, следовало бы к уже полученным решениям (x, y) присоединить (x, -y) и (-x-1, ±y) для n =1, 2, .. .

Так что здесь мы имеем, например, еще такие решения: (-2,1) (-23,13), (-314,181). А. Роткевич заметил, что из всех решений уравнения (1) в натуральных числах х > 1 и у можно получить все решения уравнения (z+1)- z = y (6)

в натуральных числах z, у. В самом деле, допустим, что натуральные числа z,у удовлетворяют уравнению (5). Положив x=3z+l , получим, как легко проверить, натуральные числа х > 1 и у , удовлетворяющие уравнению (1).

С другой стороны, если натуральные числа х > 1 и у удовлетворяют уравнению (1), то имеем, как легко проверить, (х- 1)= 3(у-х) , откуда следует, что число (натуральное) х-1 делится на 3 , следовательно х-1= 3 z, где z есть натуральное число, причем имеет место равенство 3z= y- x =у3 z -1 , которое доказывает, что числа z и у удовлетворяют уравнению (6). Таким образом, исходя из решений (22,13),(313,181), (4366,2521) уравнения (1), получаем решения (7,13),(104,181),(1455,2521) уравнения (6). Заметим здесь еще, что если натуральные числа z, у удовлетворяют уравнению (6), то доказано, что у есть сумма двух последовательных квадратов, например 13=2+3,181=9+10, 2521=35+ 36 . Подобным образом, как прежде для уравнения(1), мы могли бы найти все решения уравнения x +(x +1)= y в натуральных числах х, у , приняв для х > 3 g(x. у) = (3х -2у+1, 3у - 4х- 2) и для x > 1 f(x, y) = (3 x + 2y+l, 4х + Зу + 2), что приводит к формуле (х, у) f (3,5) и к выводу, что все решения уравнения (6) в натуральных числах х, у содержатся в последовательности { x , y } для n = 1, 2,…., где х= 3, у= 5, а x =3 x +2 y +1 . y = 4 x +3 y +2 (n =1, 2, ...). Например, х=3 3+2 5+1=20, у= 4 3+З 5 + 2 = 29; x =119, у=169: x =69б, у= 985; x =4059, у=5741.

Геометрический смысл рассмотренного уравнения состоит в том, что оно дает все пифагоровы треугольники (прямоугольные с натуральными сторонами), катеты которых выражаются последовательными натуральными числами. Таких треугольников имеется бесконечное множество (*).

Уравнение же x +(x +1)= y , как доказано, не имеет решений в натуральных числах х, у .