Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/s43/math/uroki/2010_2011/10mat_1011/spec/10-chakravala.pdf Дата изменения: Sun Sep 2 21:16:12 2012 Дата индексирования: Tue Feb 5 07:14:08 2013 Кодировка: Windows-1251

Гимназия 1543, 10-В класс, 4 сентября.

Уравнение Пелля и индийские математики.
Уравнение Пелля.

Уравнением Пелля
где

называется уравнение в целых числах вида:

x2 - dy 2 = 1, dN
не является точным квадратом. Для удобства будем рассматривать только положительные решения (решения с отрицательными значениями переменных получаются из неотрицательных тривиальным образом, решение будет неинтересно). Среди положительных решений особняком стоит т.н.

минимальное

(1, 0)

для нас

решение с наименьшим

x

(и

y

,

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

Для произвольных чисел

x

1,

x

2,

y
2 1

1,

y2

и

d

выполнено тождество:

(x -

2 dy1

2 )(x - dy2 ) = (x1 x2 + dy1 y2 )2 - d(x1 y2 + x2 y1 )2 .
уравнения Пелля, то и

2 2

Из этого тождества следует, что если

решение (назов?м его произведением решений

(x1 , y1 ) и (x2 , y2 ) решения (x1 , y1 ) и (x2 , y2 ); для

(x1 x2 + dy1 y2 , x1 y2 + x2 y1 )



такого умножения выполняются переместительный

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

s-1 1

решение

s = (x0 , y0 ) некое (положительное) решение (x1 , -y1 ). Рассмотрим решение s = ss- 1

уравнения Пелля, а s1 = (x1 , y1 ) минимальное. 1 . Возвед?м вторую компоненту этого решения в

2 2 22 22 2 2 (x1 y0 - x0 y1 )2 = x2 y0 + x2 y1 - 2x0 y0 x1 y1 = (1 + dy1 )y0 + (1 + dy0 )y1 - 2x0 y0 x1 y1 = y0 + y1 - 2y0 y1 (x0 x1 - dy0 y1 ). 1 0
Докажем, что

x0 x1 > dy0 y

1 . Если бы это было неверно, то было бы выполнено

x0 x1 - dy0 y1

0,

а также:

x x
положительности Поэтому

2 0 x1 2 1 x0

- dx0 y0 y1 - dx1 y0 y1

0 0. 0
и

Последние два неравенства легко переписываются в виде:

x1 + dy0 (y0 x1 - y1 x0 ) y

x0 + dy1 (y1 x0 - y0 x1 )

0

. В силу

2 0 . Значит, решение (|x1 x0 - dy1 y0 |, |x1 y0 - x0 y1 |) имеет -1 меньшую вторую (а, следовательно, и первую) компоненту, чем решение s. Таким образом, умножая это решение на s1 ,
что меньше беря модуль обеих компонет и повторяя эти действия, получим в итоге решение с нулевым Осталось заметить, что операция, обратная к умножению на компонент, выполненная перед умножением на знаков. Таким образом, решение

x0 и x1 оба неравенства одновременно 2 2 (x1 y0 - x0 y1 )2 < y0 + y1 - 2y0 y1 = (y0 - y1 )2 ,

не могут иметь место.

y

. А такое решение одно:

(1, 0).

s-1 1

это умножение на

s1

эквивалентна умножению на

s1

или

s-1 1

s1

, а замена знаков каких-то

, иногда с последующей заменой

(x0 , y0 )

получено из решения

(1, 0)

пут?м умножения на какую-то степень

s1

, возможно, с после-

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

s1

имеют те же модули компонент, что и соответствующие

положительные степени (докажите самостоятельно!), получаем, что все нетривиальные положительные решения уравнения Пелля исчерпываются положительными степенями минимального решения.
Чакравала.

Сама задача поиска минимального решения зачастую представляет большую трудность. Она была решена между 7 и 11 веками, решение было изложено в трудах индийского математика Бхаскары I I в 12 веке под названием чакравала (колесо). А вот первое полное доказательство того, что метод работает, появилось только в 30х годах 20 века. Само доказательство несколько громоздко, поэтому изложено не будет, в отличие от метода. Тождество Брахмагупты позволяет перемножать не только решения уравнения Пелля, но и решения более общего уравнения:

x2 - dy 2 = z .
Произведением решений простыми на Метод чакравала решения уравнения Пелля состоит в следующем: бер?тся произвольное решение

x

и

y

(обычно

z

(докажите, что так

(x1 x2 + dy1 y2 , x1 y2 + x2 y1 , z1 z2 ). (x, y , z ) с взаимно (1, 0, 1)) и умножается на решение (t, 1, t2 - d), прич?м t > 0 подбирается так, чтобы x + y t делилось 2 2 сделать можно), а |t - d| был минимально возможным. Новая тройка (xt + y d, x + y t, z (t - d))
и назов?м тройку (тоже решение)

(x1 , y1 , z1 )

(x2 , y2 , z2 )

превращает уравнение в верное равенство:

(xt + y d)2 - d(x + y t)2 = z (t2 - d).
Деля равенство на Так как

z

2

, получаем, что решением уравнения также является тройка простые, то

xt + y d).

Из равенства

x(x + y t) - y (xt + y d) = z , а z и y взаимно (xt + y d)2 - d(x + y t)2 = z (t2 - d)

следует, что и

xt + y d t2 - d

делится делится

xt + y d x + y t t2 - d , , . |z | |z | z на z (более того, z есть НОД x + y t и на z . Поэтому новая тройка состоит из z

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

(x, y , z )

, и шаг алгоритма повторяется. В некоторый момент в качестве

окажется число 1 (это утверждение останется без доказательства).