Реферат: по математике «Уравнения Пелля»

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

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

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

средняя общеобразовательная школа №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 не равны нулю одновременно.
Ответим сначала на вопрос, имеет ли линейное уравнение хотя бы одно решение.

Обозначим через в наибольший общий делитель чисел а и 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 -1} q_n + r_n ,

r_{n -1} =r_n q_{n +1} . Тогда в = НОД (а, b) = НОД (b, r₁ ) = ... = НОД (r_{n -1} , r_n ) = r_n .
Покажем теперь, как найти решение уравнения (2) с помощью цепочки равенств (3). Выразим d=r_n из предпоследнего равенства. В полученное выражение подставим значение r_{n -1} из предыдущего равенства и т. д. Продолжая этот процесс, в конце концов получим выражение в в виде левой части уравнения (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).

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

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

аx+bу=0 (5)

Осталось решить это уравнение. Снова введём d=НОД (a,b). Тогда a=a’d, b=b’d, где НОД (a’, b’)=1. Уравнение (5) перепишется в виде

a’x= - b’у,

а так как а’х делится на b’ и a’ взаимно просто с b’ , то х делится на b’ .

Значит, х=b’ t, откуда у=- a’ t.

Теперь можем резюмировать. Если с не делится на НОД (a,b), то уравнение (1) решений не имеет. Если же с делится на НОД (a,b), то уравнение (1) имеет бесконечно много решений, получаемых по формулам

х=х₀ +, у=у₀ -,

где t – произвольное число, d= НОД (a,b), а (x_0, y₀ ) – частное решение, которое может быть найдено с помощью алгоритма Евклида.

§2. Уравнения Пелля.

1. Что такое уравнение Пелля?
Определение: Уравнения Пелля — это уравнения вида

х² - mу² =1, (6)
где т — целое положительное число, не являющееся точным квадратом.

Они представляют собой класс диофантовых уравнений второй степени и связаны со многими важными задачами теории чисел. Прежде всего сделаем два замечания. Во-первых, при любом т. уравнение (6) имеет по крайней мере два решения: х = 1, у = 0. Эти решения мы назовём тривиальными. Во-вторых, поскольку при изменении знака у х или у левая часть уравнения (6) не изменится, достаточно ограничиться нахождением только неотрицательных решений (т. е. решений с неотрицательными х и у).

Решая уравнение Пелля, мы будем отвечать на три вопроса.
1) Существует ли хотя бы одно нетривиальное решение?
2) Если да, то как его найти?
3) Как описать все решения?

Заметим, что ограничение на параметр т является естественным. Если т - точный квадрат, то уравнение (6) не имеет нетривиальных решений.

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

2. Пример уравнения: х² - 2y² =1.

Рассмотрим уравнение Пелля при m=2: х² - 2y² =1.
Несложная выкладка показывает, что если пара (х, у) является решением рассматриваемого уравнения, то пара (3х + 4у, 2х + 3у) тоже его решение. Действительно,
(3х + 4у)² — 2(2х + Зy)² = (9х² + 24ху + 16у² ) —
— 2(4х² + 12ху+9у² )= x² — 2у² . Поэтому если х² - 2у² = 1, то и (Зх+4у)² – 2 (2х+Зу)² = 1.

Значит, исходя из тривиального решения х₀ = 1, y₀ = 0, мы можем получить бесконечную последовательность (нетривиальных) решений (x_{i ,} у_i ) с помощью рекуррентной формулы (х_i ,у_i ) = f (x_{i -1} ,y_{i -1} ), где f (х, у) = (3х + 4у, 2х + 3у). Вот несколько первых её членов: (3,2), (17,12), (99,70), (577,408).

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

Неотрицательные решения уравнения Пелля можно естественным образом упорядочить, для этого рассмотрим на координатной плоскости множество точек, удовлетворяющих соотношению х² - 2у² = 1, лежащих в первой координатной четверти. Это - график функции у=, определённой при х 1 (рис. 3).

Рис.3. График функции у=.

Будем говорить, что точка на этом графике тем больше, чем дальше она находится от точки (1,0). Поскольку функция монотонна, большей из двух точек графика будет та, у которой больше как абсцисса, так и ордината. Неотрицательные решения уравнения Пелля суть целые точки на графике. Поэтому неравенство (х’, у’) < (х”, у”) для двух различных неотрицательных решений (х’, у’) и (х”, у”) означает, что х’ < х” (и, тем самым, у’ < у”).

Отображение f является монотонным относительно введённого упорядочения. Действительно, для неотрицательных х’, у’, х” и у”
из неравенств х’ < х” и у’ < у” очевидным образом следуют неравенства 3х’ + 4у’ < 3х” + 4у” и 2х’ + 3у’ < 2х” + 3у”. Любое монотонное отображение имеет обратное, также являющееся монотонным. Обратным к f является отображение g (х,у) = (3х — 4у, 3у — 2х). Оно также переводит любое решение уравнения в решение.

Предположим, что существует решение (х’, у’) уравнения х² - 2у² = 1, не совпадающее ни с одним из членов построенной последовательности (х_i ,у_i ). Поскольку х_i и y_i неограниченно возрастают, решение (х’,у’) лежит между какими-то двумя решениями из последовательности: (х_i ,у_i ) < (х’,у’) < (х+1,у+1). Применяя к этому двойному неравенству монотонное отображение g последовательно i раз, получим (х₀ ,у₀ )<(х’,у’)<(х₁ ,у₁ ), где g (х’,у’) тоже решение уравнения. Однако нетрудно убедиться, что между решениями (1,0) и (3,2) других решений рассматриваемое уравнение не имеет. Полученное противоречие доказывает, что любое неотрицательное решение принадлежит последовательности (х_i , у_i ).

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

График уравнения x² -my² =1- это гипербола (рис. 4), асимптотами которой являются прямые . Чтобы убедится в этом, разложим левую часть уравнения на множители:

и введём новую (косоугольную) систему координат, направив ось Ох’ вдоль прямой , а ось Оу’- вдоль прямой . В системе координат Ох’у’ уравнение нашей кривой запишется в привычном виде: х’у’= const.

Рис.4. График уравнения x² -my² =1

При любом m гипербола проходит через точку (1, 0) и симметрична относительно обеих координатных осей.

Вместе с гиперболой х² - mу² = 1, рассмотрим серию кривых l_{n ,} задаваемых уравнениями х² - m у² =n, где п — всевозможные целые числа (рис. 5). Кривые l _n при n0 представляют собой гиперболы, а l ₀ — это пара прямых у =, являющихся общими асимптотами этого семейства гипербол.

Рис.5 Графики уравнений х² - m у² =n.

Поскольку для любой целой точки величина х² - ту² является целым числом, каждая целая точка попадает на один из графиков l_n . Так как т не является точным квадратом, на l ₀ (паре асимптот) лежит лишь начало координат. Все остальные целые точки лежат на гиперболах.

С каждой гиперболой l_n связана сопряжённая ей гипербола l _{- n} . Если мы выберем на одной из гипербол пару центрально-симметричных относительно начала координат точек, то на сопряжённой гиперболе можно выбрать такую пару центрально-симметричных точек, чтобы все четыре точки были вершинами параллелограмм со сторонами, параллельными асимптотам. Такие пары точек будем называть сопряжёнными друг другу. Действительно, если в системе координат, оси которой идут вдоль асимптот, пара симметричных точек имеет координаты (х’, у’) и (-х’, -у’), то сопряжённой ей в той же системе координат является пара симметричных точек (х’,-у’) и (-х’,у’).

4. Общее решение уравнения Пелля.

Если уравнение Пелля имеет хотя бы одно нетривиальное решение, то, умножая его многократно на себя, можно найти бесконечно много решений. При этом все решения можно найти аналогично тому, как мы действовали в частном случае m =2. Двигаясь по графику уравнения (рис.6) из точки (1,0) в направлении положительных значений y , находим первое нетривиальное решение. Это решение назовём основным .

Рис.6. График уравнения x² -3y² =1

Теорема 1. Все нетривиальные положительные решения получаются многократным умножением основного решения на себя.

Доказательство. Рассмотрим последовательность (x₁ ,y₁ ), (x₂ ,y₂ ), …, (x_n ,y_n ),… решений, получаемых из основного решения (x₁ ,y₁ ) последовательным умножением на него. Предположим, что на графике уравнения между двумя её членами (x_n ,y_n ) и (x_{n +1} ,y_{n +1} ) имеется некоторое решение. Умножив его на (x₁ ,-y₁ ), получим новое решение, лежащее между (x_{n -1} ,y_{n -1} ) и (x_n ,y_n ). Действительно, умножение на (x₁ ,-y₁ ) является обратной операцией к умножению на (x₁ ,y₁ ). Проделав такую операцию n раз, получим решение, лежащее между (1,0) и (x₁ ,y₁ ). Это противоречит тому, что (x₁ ,y₁ ) – основное решение.

Теорема 2. Любое уравнение Пелля имеет нетривиальное решение.

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

Введем понятие цепных дробей.

Любое нецелое число можно представить в виде, где -целое число, а>1. Действительно, в качестве нужно взять целую часть числа , а в качестве - обратное число к его дробной части . Такое представление единственное , поскольку из условия >1следует, 0<<1, поэтому – дробная часть , а значит, - целая часть . Если число оказалось нецелым , то его в свою очередь можно представить в виде и т.д. В результате мы получим представление числа в виде

.

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

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

Теорема 3. Если несократимая дробь такова, что , то является подходящей дробью числа .

Теорема 4. Пусть (х, у) – положительное решение уравнения Пелля. Тогда является подходящей дробью .

Доказательство: Так как х>у>0 и >1, то х+у>2у.

Значит, 1=х² – mу² = (х - у)(х+у)>(х - у)· 2у.

Разделим полученное неравенство на 2у² :

- <.

Поскольку (х,у) – положительное решение уравнения Пелля, левая часть этого неравенства положительна и дробь несократима. Поэтому, согласно теореме 3, она является подходящей дробью числа .

Итак, положительные решения уравнений Пелля следует искать только среди пар, составленных из числителя и знаменателя какой-нибудь подходящей дроби числа . Возникает вопрос, какие именно подходящие дроби соответствуют решениям уравнения Пелля. Ответ на него дает теорема, которая приводится без доказательства.

Теорема 5. Пусть n – длина периода последовательности элементов цепной дроби для числа . Тогда числитель и знаменатель подходящей дроби числа являются решением уравнения Пелля тогда и только тогда, когда ее номер имеет вид kn-1 (т.е. дает при делении на n остаток n-1) и нечетен.

Заключение.

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

Для достижения целей

- была изучена научная литература;

- были детально изучены основные термины и утверждения исследуемого раздела, а также их доказательства;

- были рассмотрены примеры.

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

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

1. Бугаенко В.О. Уравнения Пелля. - М.: МЦНМО, 2001. (Серия: Библиотека "Математическое просвещение". Вып. 13)