по математике «Уравнения Пелля» (стр. 1 из 3)

Министерство образования и науки

Российской Федерации

Муниципальное образовательное учреждение

средняя общеобразовательная школа №33

Реферат

по математике

«Уравнения Пелля»

Выполнил:

ученик 9 «А» класса

Петров Алексей Андреевич

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

учитель математики Фоменкова Татьяна Анатольевна

Тверь, 2010

Оглавление

Введение ………………………………………………………………………3

Глава 1. Линейные диофантовы уравнения…………………………………4

1.1 Что такое линейные диофантовы уравнения……………………………4

1.2 Алгоритм Евклида…………………………………………………..........4

1.3 Графический способ решения линейного диофантова уравнения …...6

1.4 Общее решение линейного диофантова уравнения …………………...8

Глава 2. Уравнения Пелля…………………………………………………...9

2.1 Что такое уравнения Пелля ……………………………………………..9

2.2 Пример: уравнение х² – 2у²=1 ……………………………………..........10

2.3 График уравнения Пелля …………………………………………..........11

2.4 Общее решение уравнения Пелля ………………………………………13

2.5 Решение уравнения Пелля, основанное на цепных дробях …………...14

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

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

Введение

С понятием «уравнение» на уроках математики мы знакомимся ещё в начальной школе, а задача «решить уравнение», вероятно, наиболее часто встречающаяся задача.

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

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

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

На протяжении более трех веков человечество пыталось решить эти уравнения и до сих пор современные математики ищут наиболее эффективные методы решений уравнений Пелля и знаменитого уравнения Ферма: хⁿ+уⁿ=zⁿ , n>2.

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

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

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

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

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

1. Что такое линейные диофантовы уравнения.

Определение: Линейные диофантовы уравнения — это диофантовы уравнения вида

ах+bу=с, (1)
где а, b и с — некоторые целые числа, причём а и b не равны нулю одновременно.
Ответим сначала на вопрос, имеет ли линейное уравнение хотя бы одно решение.

Обозначим через d наибольший общий делитель чисел а и b. Если число с не делится на d, то решений нет, поскольку при любых х и у левая часть (1) делится на d, а правая — не делится.
Пусть теперь с = kd. В этом случае решение существует. Чтобы это доказать, достаточно показать, что имеет решение уравнение
ах+bу=d. (2)
Действительно, умножив решение (т. е. каждое из чисел х и у) уравнения (2) на k, получим решение уравнения (1).

Один из методов нахождения решения уравнения (2) основан на алгоритме Евклида.

2. Алгоритм Евклида.
Алгоритм Евклида служит для нахождения наибольшего общего делителя двух целых положительных чисел. Он основан на следующем простом наблюдении. Если а = bq+r (где q - частное, а r - остаток от деления а на b), то НОД (а, b) = НОД (b, r). Действительно, из формулы деления с остатком следует, что любой общий делитель чисел b и r является также делителем числа а, а любой общий делитель чисел а и b является также делителем числа r. Поэтому множества общих делителей пар чисел (а, b) и (b, r) совпадают, а значит, совпадают и их наибольшие общие делители.
Применение алгоритма Евклида заключается в последовательном делении с остатком. Сначала мы делим большее из двух чисел на меньшее. На каждом следующем шаге мы делим число, которое на предыдущем шаге было делителем, на число, которое было остатком. Так поступаем до тех пор, пока не получим нулевой остаток. Это обязательно произойдёт через конечное число шагов, поскольку остатки всё время уменьшаются. Последний ненулевой остаток и будет наибольшим общим делителем исходных чисел.
Алгоритм Евклида, применённый к паре чисел (а, b), где а > b, может быть записан в виде цепочки равенств
a=bq₁ + r_1,

b=r₁q₂ +r₂,

r₁=r₂q₃ + r₃, (3)

……………

r_n-2=r_n-1q_n + r_n,

r_n-1=r_nq_n+1. Тогда d = НОД (а, b) = НОД (b, r₁) = ... = НОД (r_n-1, r_n) = r_n.
Покажем теперь, как найти решение уравнения (2) с помощью цепочки равенств (3). Выразим d=r_n из предпоследнего равенства. В полученное выражение подставим значение r_n-1 из предыдущего равенства и т. д. Продолжая этот процесс, в конце концов получим выражение d в виде левой части уравнения (2).
Для примера рассмотрим уравнение 355х + 78у = 1.

1. Сначала найдём наибольший общий делитель чисел 355 и 78 с помощью алгоритма Евклида:
355= 78 • 4+43,
78=43•1+35,
43= 35•1+ 8,
35=8•4+3,
8=3•2+2,
3= 2•1 + 1,
2=1•2.
Итак, НОД (355, 78) = 1. Перепишем полученные равенства в виде
43=355 - 78•4,
35=78 - 43•1,
8=43 - 35•1,
3=35 - 8•4,
2=8 - 3•2,
1=3 - 2•1.
2. Теперь пойдём по цепочке равенств снизу вверх:
1 = 3 - 2•1 = 3 - (8 - 3•2) •1 = 3•3 - 8 = (35 - 8•4) •3 - 8 =
= 35•3 - 8•13 = 35•3 - (43 - 35•1) •13 = 35•16 - 43•13 = (78 - 43•1)•16 - 43•13 = 78•16 - 43•29 = 78•16 - (355—78•4) •29 = 78•132 - 355•29.
Найдено решение: х = -29, у = 132.
Нам осталось ответить на вопрос: как, зная одно решение линейного диофантова уравнения, найти все? Чтобы ответить на него, разберём сначала один пример.

3. Графический способ решения линейного диофантова уравнения.
Рассмотрим пример: уравнение 3х + 5у =22.
Подбором легко найти одно из решений этого уравнения, например, х=4, у =2. Применение алгоритма Евклида приводит к другому решению: х = 44, у = -22.
Нарисуем на координатной плоскости график уравнения — множество точек (х, у), таких что х и у удовлетворяют этому уравнению. Этот график представляет собой прямую (рис. 1), которую мы обозначим через l. На ней нужно найти все точки с целыми координатами (которые мы для простоты будем называть целыми точками). Из рисунка видно, что точки (4,2) и (-1,5) лежат на прямой l и на отрезке между этими точками других целых точек нет. Конечно, ссылка на график не является доказательством. Однако доказать это несложно: непосредственно проверяем, что указанные пары чисел удовлетворяют уравнению, а при у =3 и у =4 значения х, получаемые из уравнения, оказываются нецелыми.
Заметим, что если пара (х₀, у₀) — решение уравнения, то пара (х₀-5, у₀+3) тоже решение:
3(х₀ - 5)+ 5(у₀ +3) =3х₀ – 15 + 5у₀ + 15 = 3х₀ + 5у₀ = 22.

Преобразование (х, у) → (х-5, у+3), (4)
во-первых, сохраняет прямую l (оно является параллельным переносом вдоль неё), во-вторых, переводит целые точки в целые, и поэтому любое решение уравнения переводит в решение.

Рис. 1 График уравнения 3х + 5у =22.

Применяя к уже найденному решению преобразование (4), т. е. прибавляя к х число (-5), а к у число 3, мы получим ещё одно решение, потом ещё одно и т.д. Точки, соответствующие этим решениям, располагаются на прямой 1 через равные расстояния (см. рис. 1). Ясно, что можно двигаться и в обратную сторону.
Таким образом, мы нашли бесконечную серию решений
х=4 – 5t, у=2 + 3t, где t — любое целое число.

Докажем, что любое решение имеет такой вид.

Рассуждаем от противного: пусть на прямой 1 между точками (4 – 5t, 2 + 3t) и (4 -5(t+1), 2+3(t+1)) найдётся целая точка. Применяя несколько раз параллельный перенос (4), если t < 0, или обратный ему перенос, если t > 0, мы получим, что на интервале между точками (4,2) и (-1,5) тоже есть целая точка. Противоречие.
Итак, мы нашли все решения уравнения и доказали, что других нет.

4. Общее решение линейного диофантова уравнения. Перейдём теперь к рассмотрению общего случая. Рассмотрим графики уравнений (1) при фиксированных а и b и пробегающем всевозможные целые значения параметре с. Это — бесконечное множество параллельных прямых l_с, причём каждая целая точка принадлежит ровно одной такой прямой (рис.2).

Рис. 2. Графики уравнений ах+bу=d.

Введём на координатной плоскости «сложение» точек:

(х₁ , y₁) + (х₂, y₂)= (х₁₊ х₂, y₁₊ y₂).
Введённая операция сложения целых точек определена также на подмножестве целых точек. Действительно, сумма двух целых точек является целой точкой.
Эта операция имеет естественную геометрическую интерпретацию: она соответствует сложению векторов с началами в начале координат и концами в данных точках. Как и обычное сложение, сложение точек имеет обратную операцию — вычитание.
Чтобы найти общее решение уравнения (1), нужно к его частному решению добавить общее решение уравнения