Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2002/04/kv0402spivak.pdf Дата изменения: Fri Dec 23 19:26:56 2005 Дата индексирования: Tue Oct 2 00:34:23 2012 Кодировка: Windows-1251 Поисковые слова: m 5

Уравнения Пелля
УРАВНЕНИЯ ПЕЛЛЯ

5

А.СПИВАК

мулированы, но не доказаны следующие теоремы. Теорема 2. Уравнение x 2 - 2y 2 = +1 не имеет решений в целых неотрицательных числах, кроме тех, что получаются из 'тривиального' решения (1; 0) при помощи правила x; y R x + 2 y; x + y . Теорема 3. Уравнение x 2 - 2y 2 = 7 не имеет решений в целых неотрицательных числах, кроме тех, что получаются из одного из двух 'начальных' решений ( 3; 1 ) и ( 5; 3 ) при помощи правила x; y R 3x + 4y; 2x + 3y . Теорема 5. Уравнение x 2 - 3y 2 = 1 не имеет решений в целых неотрицательных числах, кроме тех, что получаются из решения (1; 0) при помощи правила x; y R 2x + 3y; x + 2y . 2 2 Теорема 7. Уравнение x - xy - y = +1 не имеет решений в целых неотрицательных числах, кроме тех, что получаются из решения (0; 1) при помощи правила x; y R x + y; x . Можно было бы рассмотреть еще несколько примеров и сформулировать много аналогичных теорем, но пора переходить к более общим рассмотрениям.

В

ПРОШЛОМ НОМЕРЕ ЖУРНАЛА БЫЛИ СФОР-

щей. Но она, надеемся, гораздо прозрачнее. Зачем нам нужна доказанная формула? Чтобы строить из одних решений другие! Точнее говоря, формула доказывает следующую важную теорему. 2 2 Теорема 8. Если x - dy = a и z 2 - d t 2 = b , то пара чисел X; Y = xz + dyt; xt + yz удовлетворяет равенству X 2 - dY 2 = ab . И опять сформулируем и не докажем теорему о том, как устроено множество решений уравнения Пелля. Теорема 9. Если a наименьшее натуральное число, для которого существует такое натуральное число 2 2 b, что a 2 - d b 2 = 1 , то уравнение x - dy = 1 не имеет решений в целых неотрицательных числах, кроме тех, что получаются из 'тривиального' решения (1; 0) при помощи правила x; y R ax + dby; bx + ay .
Упражнения 2 2 23 21. Уравнение а) x 2 - 2y 2 = 14 ; б) x - 2y = 23 имеет бесконечно много решений в целых числах, а уравнение в) x 2 - 2 y2 - 1004 = 1001 не имеет ни одного. Докажите это. 22. Найдите наименьшее натуральное число, квадрат которого представим в виде суммы квадратов 11 последовательных а) целых; б) натуральных чисел. в) Докажите, что существует бесконечно много натуральных чисел, квадрат каждого из которых представим в виде суммы квадратов 11 последовательных натуральных чисел. 23. Пусть a , b, x , y , z, t рациональные числа, x 2 + ay 2 + bz 2 + abt 2 = 0 и хотя бы одно из чисел x, y, z и t отлично от нуля. Докажите, что существуют такие рациональные числа u , v и w , что u2 + av2 + bw2 = 0 и u2 + v2 + w2 ? 0 .

x

x 2 - dy

2


2

z 2 - dt

2

Формула = xz + dyt





2

- d xt + yz



2

Следующее вычисление пожалуй, самое главное в теории уравнений Пелля:
2

- dy

2

z

- dt

2



= x 2 z 2 - dy 2 z2 - dx 2t2 + d 2 y2t 2 =

= x 2 z 2 + 2 x z d y t + d 2 y 2t 2 dy z - 2dyzxt - dx t = xz + dyt
22 22



2

- d xt + yz .

2

Теорема существования
Теорема 10. Для любого натурального числа d, не являющегося квадратом, существуют такие натуральные числа x и y, что x 2 - dy 2 = 1. Вместе взятые, теоремы 8, 9 и 10 позволяют довольно ясно представить себе структуру множества решений уравнения Пелля. В одном из ближайших номеров журнала мы изложим четыре доказательства теоремы 10. А здесь у нас хватит сил только на то, чтобы доказать теоремы 2, 3, 5, 7 и 9. Впрочем, мы это сделаем двумя способами: сначала обойдемся без помощи иррациональностей, а затем при помощи иррациональностей изложим (по сути то же самое) доказательство и даже расскажем о решениях в целых числах уравнения x 2 - dy 2 = c .
Упражнения 24. Если d натуральное число, не являющееся квадратом, c ? 0 и уравнение x 2 - dy 2 = c имеет хотя бы одно

А вот как можно получить ту же формулу, если разложить разность квадратов на (иррациональные!) множители и переставить их разумным образом:

x

2

- dy
= =

= xz + dy t +



z x + x +
2

2

- dt

y y



= d x - y d z + t d z - t d = d z + t d Ч x - y d z - t d = x t + yz d Ч xz + d yt - xt + y z d
2

=
2

= xz + dyt



2

- d xt + yz .

Честно говоря, эта выкладка даже длиннее предыдуПродолжение. Начало см. в 'Кванте' ?3.
2 Квант ? 4


6

КВАНT 2002/?4

решение в целых числах, то это уравнение имеет бесконечно много решений в натуральных числах. Выведите это из утверждения теоремы 10. 25. а) Пользуясь утверждением теоремы 10, выясните, при каких целых a уравнение a x 2 - 1 = y 2 имеет бесконечно много решений в целых числах. б) Пусть a целое число. Пользуясь утверждением теоремы 10, выясните, при каких натуральных d уравнение x 2 - dy 2 = a 2 имеет бесконечно много решений в натуральных числах. 26. Пусть n натуральное число, n > 1. Докажите, что уравнение а) x 2 - n 2 - 1 y 2 = 1 ; б) x 2 - n 2 + 1 y 2 = 1 ; в) x - n + 2 y = 1; г) x - n - 2 y = 1 имеет бесконечно много решений в натуральных числах. 27. Докажите, что при любом натуральном a уравнение а) a 2 + 1 x 2 + 1 = y 2 ; в) д)
2 2 2

и решим ее:

(

)

мx = 2Y - X, н оy = X - Y. Легко проверить, что x 2 - 2y2 = 2Y - X



2

- 2 X - Y



2

=
2

2 2 2 = 4Y - 4 XY + X - 2 X - 2 XY + Y





= - X 2 - 2Y



2



.

(

2

)

2

(

2

)

(

2

)

2

(

)

имеет бесконечно много решений в целых числах. 28. Докажите, что ни при каком натуральном a уравнение а) a 2 + 1 x 2 + 1 = y2 - 1 ;
2

( (a (a (

+ +

)( 1) ( x 1) ( x )(

2 2

+ -

) 1) 1) )

б) a 2 - 1 x 2 - 1 = y 2 ; г) a2 - 1 x 2 - 1 = y2 - 1 ; е)
2

= y +1; = y2 - 1 ;

2

( ( (a

-

)( )( 1) ( x )

2

+

) ) 1)

= y2 - 1

б) x = ( 4a - 1) y 2 + 1 ; в) a x 2 - 1 = y 2 + 1 не имеет решений в целых числах. Указание к пунктам б) и в). Воспользуйтесь тем, что число вида y 2 + 1 не может делиться на натуральное число вида 4n 1. Доказательство последнего факта можно прочесть, например, в статье 'Суммы квадратов и целые гауссовы числа' в 'Кванте' ?3 за 1999 год. 29. Докажите следующие утверждения. а) Существует бесконечно много четверок целых чисел, в каждой из которых числа попарно различны и таковы, что x + y + z + t = = x 3 + y 3 + z 3 + t 3 = 2 . б) Уравнение xy ( x + 2) ( y + 2) = = z ( z + 2) имеет бесконечно много решений в натуральных числах. в) Существует бесконечно много таких троек натуральных чисел, что произведение любых двух из этих чисел на единицу больше квадрата натурального числа. г) Для любого натурального числа a система уравнений
м xy - 1 = a 2, п п 2 н yz - 1 = u , п 2 п zx - 1 = v о имеет бесконечно много решений в натуральных числах x, y, z, u и v. д) Для любого натурального числа n существует бесконечно много таких наборов из k = 3n2 1 последовательных натуральных чисел, что сумма их квадратов сама является квадратом натурального числа. Указание. Воспользуйтесь теоремой 10. 30 * (М618). Докажите следующие утверждения. а) Существует бесконечно много таких натуральных n, что n! делится на n2 + 1 . б) Для любого числа > 0 существует бесконечно много таких натуральных n, что [n] ! делится на n2 + 1 .

(

)

(

Доказательства теорем
Теорема 2

Понимаете, в чем идея? Каждой паре (X; Y), являющейся решением уравнения X 2 - 2Y 2 = +1 , мы сопоставляем ее 'предшественницу' пару x; y = = 2Y - X; X - Y , удовлетворяющую равенству x 2 - 2y 2 = m1 . Лемма. Если X , Y натуральные числа и X 2 - 2Y 2 = +1 , то 2Y X и X Y неотрицательные числа, причем X Y < Y. Доказательство. Будем рассуждать 'от противного'. Если 2Y X < 0, то X > 2Y и X 2 - 2Y 2 > 4Y 2 - 2Y 2 = 2Y 2 ? 2 > 1 , что противоречит равенству X 2 - 2Y 2 = +1 . Если X Y < 0 , то X < Y и X 2 - 2Y 2 < Y 2 - 2Y 2 = -Y 2 ? -1 . Наконец, если X - Y ? Y , то X ? 2Y и X 2 - 2Y 2 ? 4Y 2 - 2Y 2 = = 2Y 2 ? 2 > 1 , что вновь дает противоречие. Лемма доказана. Эта лемма основа доказательства теоремы 2. А именно, взяв любую пару (X; Y) натуральных чисел, удовлетворяющую равенству X 2 - 2Y 2 = +1 , мы можем рассмотреть ее предшественницу пару (x; y). При этом y < Y . Если x и y натуральные числа, то у пары (x; y) есть своя предшественница, у той своя, и так далее. Бесконечно этот процесс продолжаться не может: неравенство y < Y гарантирует, что начатый с пары (X; Y) процесс образования предшественниц оборвется не более чем через Y шагов. (Любитель строгости сказал бы, что здесь мы воспользовались отсутствием бесконечно убывающей последовательности натуральных чисел.) В какой момент обрывается процесс образования пар-предшественниц? Очевидно, когда очередная пара (x; y) состоит не только из натуральных чисел, проще говоря, когда одно из чисел x и y равно нулю. Число x равняться нулю не может, а вот равенство x 2 - 2 Ч 02 = +1 возможно. И возможно оно лишь при x = 1 (напоминаем: x ? 0 ). Итак, для любого решения (X ; Y) уравнения X 2 - 2Y 2 = +1 процесс образования пар-предшественниц остановится, дойдя до пары (1; 0). Проследив этот процесс в обратном направлении, т.е. не от пары (X; Y) к паре (1; 0), а от пары (1; 0) к паре (X; Y), мы видим, что он происходит по формуле x; y R x + 2 y; x + y . Доказательство теоремы 2 завершено.
Упражнения 31. На листе клетчатой бумаги размером 32 ? 40 клеток нарисован прямоугольный треугольник, вершины которого расположены в узлах клеток. На его катетах как на гипотенузах во внешнюю сторону нарисованы равнобедренные прямоугольные треугольники. Оказалось, что разность пло-

Пусть X, Y натуральные числа, удовлетворяющие равенству X 2 - 2Y 2 = +1 . Рассмотрим систему уравнений мx + 2 y = X, н оx + y = Y


УРАВНЕНИЯ

ПЕЛЛЯ

7

2

щадей этих двух треугольников отличается от площади исходного треугольника менее чем на 1/2. Найдите наибольшую возможную площадь такого треугольника. 32. Как известно, 1 + 2 = 3. Легко проверить также, что 1 + 2 + 3 + ... + 13 + 14 = 105 = 15 + 16 + 17 + 18 + 19 + 20. Найдите все такие n, что сумма первых n натуральных чисел равна сумме нескольких последующих. Теорема 3

находим x = Y и y = X Y. Очевидно,

x 2 - xy - y2 = Y 2 - Y X - Y - X - Y

=

2 2 2 2 2 2 = Y - XY + Y - X + 2 XY - Y = - X - XY - Y .





Доказательство теоремы 3 похоже на доказательство теоремы 2. Мы рассматриваем систему м3x + 4 y = X, н о2 x + 3y = Y, находим из нее x = 3X 4Y и y = 3Y 2X, замечаем, что

x 2 - 2y2 = 3X - 4Y



2

- 2 3Y - 2 X



2

= X 2 - 2Y 2 ,

Лемма. Если X, Y натуральные числа, удовлетворяющие равенству X 2 - XY - Y 2 = +1 , то X ? Y , причем равенство выполнено лишь в случае X = Y = 1. Доказательство. Как всегда, рассуждаем 'от противного'. Если X < Y, то X 2 - XY - Y 2 < -Y 2 ? -1 , что несовместимо с условием X 2 - XY - Y 2 = +1 . Если же X = Y, то X 2 - XY - Y 2 = - X 2 . Очевидно, - X 2 не равняется 1, а - X 2 = -1 лишь при X = 1. Лемма доказана. Теперь читатель, надеемся, самостоятельно завершит доказательство теоремы 7.
Упражнение 33 (М39). а) Целые неотрицательные числа x, y удовлетворяют уравнению x 2 - mxy + y 2 = 1 (где m данное натуральное число, m > 1) тогда и только тогда, когда x и y соседние члены последовательности a0 = 1 , a1 = 1 , a2 = m , a3 = m2 - 1 , a4 = m3 - 2m , a5 = m4 - 3m2 + 1 , ..., в которой ak + 2 = mak +1 - ak для всех k ? 0 . Докажите это. б) Рассмотрим случай m = 3. Очевидно, a0 = 0 , a1 = 1 , a2 = 3 , a3 = 3 Ч 3 - 1 = 8 , a4 = 3 Ч 8 - 3 = 21 . Возникает гипотеза, что для любого n число an это (2n)-й член последовательности Фибоначчи. Докажите эту гипотезу. Теорема 9

а затем формулируем и доказываем следующую лемму. Лемма. Если X, Y натуральные числа, удовлетворяющие равенству X 2 - 2Y 2 = 7 , и выполнено неравенство Y ? 6 , то 3X 4Y и 3Y 2X тоже натуральные числа, причем 3X 4Y < X. Доказательство. Рассуждаем 'от противного'. Если 4 16 2 2 2 Y3X - 4Y ? 0 , то X ? 3 Y и 7 = X - 2Y ? 9 3 2 - 2Y < 0 . Если 3Y - 2X ? 0 , то X ? Y и X 2 2 Y2 92 2 2 - 2Y ? Y - 2Y = > 7 . Наконец, если 3X 4 4 - 4Y ? X , то X ? 2Y и X 2 - 2Y 2 ? 4Y 2 - 2Y 2 = 2Y 2 > > 7 , что вновь дает противоречие. Лемма доказана. Дальнейшее доказательство проводится почти так же, как и доказательство теоремы 2. Чтобы понять, где может остановиться процесс образования пар-предшественниц, достаточно разобрать случаи Y = 1, 2, 3, 4, 5. Сделав это, вы найдете, как и следовало ожидать, два решения: (3; 1) и (5; 3).
Теорема 5

Идея доказательства уже была применена нами четырежды. Применим же ее в пятый раз. Рассмотрим систему уравнений мxz + dyt = X, н оxt + yz = Y. Чтобы найти x, домножим первое уравнение на z, второе на dt и вычтем затем второе уравнение из первого: zX - dt Y = x z 2 - dx t 2 = x , поскольку z 2 - dt 2 = 1 . Аналогично, чтобы найти y, домножим первое уравнение на t, второе на z и вычтем второе уравнение из первого:

Доказательство теоремы 5 похоже на доказательства теорем 2 и 3. Мы рассматриваем систему

м2 x + 3y = X, н оx + 2 y = Y,
находим из нее x = 2X 3Y и y = 2Y X, замечаем, что

Xt - Yz = dyt 2 - yz2 ,
откуда y = Yz Xt. Лемма. Если X, Y натуральные числа, удовлетво2 2 ряющие равенству X - dY = 1 , а z наименьшее натуральное число, для которого существует такое 2 2 натуральное число t , что z - d t = 1 , то zX - dtY ? 0 и Yz - Xt ? 0 , причем Yz Xt < Y. Доказательство. Рассуждаем 'от противного'. Если dtY zX dtY < 0, то X < и, следовательно, z 2 2 ж dtY ц2 2 dt - z 2 < 0. 1 = X 2 - dY 2 < з ч з z ч - dY = dY ч з и ш z2 Если Yz Xt < 0, то

x 2 - 3y2 = 2X - 3Y



2

- 3 2Y - X



2

= X 2 - 3Y 2 ,

а затем формулируем и не доказываем (надеясь на читателя) следующую лемму. Лемма. Если X, Y натуральные числа, причем X 2 - 3 Y 2 = 1 , то 2X 3Y и 2Y X неотрицательные числа, причем 2Y X < Y. Окончание доказательства как в теореме 2.
Теорема 7

Из системы

мx + y = X, н оx = Y

X 2 - dY 2 >

Y 2 z2 Y 2 z 2 - d Y 2t 2 Y2 - dY 2 = = 2 ? 1. t2 t2 t

2*


8

КВАНT 2002/?4

(Последнее неравенство следует из того, что наименьшему z отвечает и наименьшее t.) Если же Yz - Xt ? Y , то X ? Yz - Y t и

X - dY ?

2

2

Y 2 z - 1 t
2 2

2

Указание. Воспользуйтесь утверждениями теоремы 10 и предыдущим пунктом. 37 (М1225). Докажите, что а*) если для натуральных чисел a и b число a 2 + b 2 ab - 1 натуральное, то оно равно 5; б) уравнение x 2 - 5xy + y 2 + 5 = 0 имеет бесконечно много решений в натуральных числах. 2n-1 щ й 38. Для любого натурального n число к3 + 11 ъ декл ъы лится на 2n и не делится на 2n +1 . Докажите это. 39. Для любого (не)четного натурального n число йж цn щ ж + 5 чn ж 3 - 5 чn ц ц кз 3 + 5 ч ъ з ч ъ - 1 = з3 ч ч з кз ч з 2 чъ з 2 ч +з 2 ч -2 з ч ч з з кз и шъ и ш и ш лк ы является (упятеренным) квадратом натурального числа. Докажите это. 40. а) Существуют такие иррациональные числа > 1 и > 1 , что ни при каких натуральных m и n целые части чисел m и n не совпадают. Докажите это. б) Придумайте такую последовательность иррациональных чисел 1, 2, 3, K , что равенство йк m щъ = йк n щъ , где r, s, m и n натуральные числа, л r ы л sы верно лишь при r = s и m = n.
yy Уравнение Cx 1 = Cx-1

- dY =

2





z2 - 2 z + 1 - dt2 2 - 2z = Y2 ?0. 2 t t2 Лемма доказана. Дальнейшее доказательство проводится в точности так, как доказательство теоремы 2.
=Y
Упражнения 34*. Докажите следующие утверждения. а) Для любого простого числа p существуют такие целые числа x и y, что x 2 - 34y 2 ? -1 mod p . б) Если p нечетное простое число, n натуральное, x и y такие целые числа, что x 2 - 34 y 2 + 1 делится на pn , то существуют такие целые числа z и t, что
+ pn z - 34 y + pnt + 1 делится на pn +1 . в) Если n > 2 натуральное число, x и y такие целые числа, что n n +1 x 2 - 34 y 2 + 1 делится на 2 и не делится на 2 , то число 2 2 n-1 +1 - 34y + 1 делится на 2n . г) Если m1 и m2 x+2 взаимно простые натуральные числа, для которых существуют такие ц елые числа x1 , y1 , x2 и y2 , что 2 2 2 2 x1 - 34y1 ? -1 m od m1 и x2 - 34y2 ? -1 mo d m2 , то су-

x



2





2



ществуют такие целые числа x и y , что x 2 - 34y 2 ?

?-1 mod mm2 . д) Для любого натурального m сравнение 1 x 2 - 34y 2 ? -1 mod m имеет решения в целых числах x и
y. е) Уравнение x 2 - 34y 2 = -1 не имеет решений в целых числах. Замечание. Ситуация, когда сравнения имеют решения, а уравнение не имеет, не столь уж редка. Например, для любого натурального числа m сравнение 3x + 1 2x + 1 ? ? 0 mo d m имеет решения в целых числах, а уравнение 3x + 1 2x + 1 = 0 не имеет целых решений. Тем интереснее знать, что 34 наименьшее натуральное число d, для которого все сравнения вида x 2 - dy 2 ? -1 mo d m имеют решения, а уравнение x 2 - dy 2 = -1 целочисленных решений не имеет. (Проверьте это!) 35. Докажите следующие утверждения. а) Если a, b такие натуральные числа, что
2 2

Разберем еще один пример. Он, возможно, покажется вам слишком специальным. Но, в конце концов, если y y уравнение Cx -1 = Cx-1 никак не заинтересовало вас и вы уверены, что оно не заинтересует вас никогда, то перейдите сразу к следующему разделу статьи. y y К уравнению Cx -1 = Cx-1 можно прийти, рассматривая 14-ю строку треугольника Паскаля: 1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1.
m Коротко расскажем о числах сочетаний Cn тем, кто с ними еще не знаком. В n-й строке треугольника Паскаля на m-м месте стоит число m Cn =

n! , m ! n - m !



3+ 2



2001

= a 3 + b 2 , то

3a - 2b = 1 . б) Если a и b такие натуральные числа, что 3a 2 - 2b2 = 1 , то для некоторого нечетного натурального

причем нумерация чисел в каждой строке, как и нумерация самих строк, начинается с нуля. Основное правило образования треугольника Паскаля таково: сумма любых двух соседних чисел некоторой строки равна числу следующей строки, которое расположено 'ниже них и между ними'; другими словами, для любых натуральных чисел m и m, где m ? n , верно равенство
m Cn -1 m m + Cn = Cn +1 .

числа n имеем a 3 + b 2 =

36. Докажите следующие утверждения. а) Существует бесконечно много таких пар натуральных чисел a и b, что a 2 + 1 делится на b, а b 2 + 1 делится на a. б) Если x < y натуральные числа и x 2 + y 2 + 1 = 3xy , то x = 2n-1 и y = 2 n+1 , где n некоторое натуральное число. в) Если a, a2 + b2 + 1 натуральные числа, то c = 3. г) Если bи c= ab два натуральных числа таковы, что увеличенный на единицу квадрат любого из них делится на другое, то произведение этих чисел на единицу больше квадрата их разности. д) Уравнение x 2 - n2 - 4 y 2 = -4 не имеет решений в натуральных числах при натуральном n ? 3 . Докажите это. е) Уравнение x 2 - n2 - 4 y 2 = -1 не имеет решений в натуральных числах при натуральном n ? 3 . Докажите это.



3 + 2 .

n

Очевидно, 1001 + 2002 = 3003. Это означает, что 4 5 6 C14 + C14 = C14 . Последнее равенство можно записать в виде
5 6 C15 = C14 . m m m И вообще, любое равенство вида Cn -2 + Cn -1 = Cn m1 m можно записать в виде Cn+1 = Cn . y-1 y Теорема 11. Равенство Cx = Cx-1 выполнено тогда и только тогда, когда x = 2k 2k +1 и y = 2k-12k , где k некоторое натуральное число. Мы докажем это довольно неожиданное утверждение двумя способами. Первый заимствован из статьи А.Ширm mшова 'Об уравнении Cn = Cn+11 ' ('Квант' ? 4 за 1977 год). Прежде всего выразим числа сочетаний










УРАВНЕНИЯ

ПЕЛЛЯ

9

через факториалы: x - 1! x! = y - 1! x - y + 1! y ! x - 1 - y! . После очевидных преобразований получаем

схема работает. Первым делом раскроем скобки и приведем подобные:

x 2 - 3xy + y2 + x - y = 0 .
Теперь освободимся от членов первой степени. Для этого выполним замену x = X + a, y = Y + b, получив уравнение

xy = x - y + 1 x - y .
Теперь применим некоторый специальный трюк. Обозначим буквой d наибольший общий делитель чисел x и y. Тогда x = ad и y = bd, где a и b взаимно просты. Подставив выражения для x и y в уравнение, после сокращения на d получим равенство
abd = ad - bd + 1a - b .

X 2 + 2aX + a 2 - 3XY - 3aY - 3bX - 3ab + Y 2 +
+ 2bY + b2 + X + a - Y - b = 0 ,

и приравняем коэффициенты при X и Y к нулю:

Поскольку числа a b и ab взаимно просты и поскольку числа d и ad bd + 1 тоже взаимно просты, то

мa = b + d, п мab = ad - bd + 1, п п п т.е. нb + d b = b + d d - bd + 1. н п пd = a - b, п о п о
Последнее уравнение после упрощений приобретает вид b2 + bd - d2 = 1 . Его решения в натуральных числах нам известны из предыдущего номера журнала: b = 2k-1 и d = 2k , где k натуральное число. Таким образом,

м2a - 3b + 1 = 0, п п н п-3a + 2b - 1 = 0. п о
Решив эту систему, находим a = 1/5 и b = 1/5. При этих значениях a и b уравнение принимает вид

X 2 - 3XY + Y 2 =
где X = x +

1 1 и Y = y - . Домножив обе части 5 5 уравнения на 20, получаем 20 X 2 - 60XY + 20Y 2 = 4,
5 4 X 2 - 12 X Y + 9Y

1 , 5

мx = ad = 2k-1 + 2k 2k = 2k 2 п п н пy = bd = 2k-12k , п о

k+1,



2

-

25Y 2 = 4,

как и было обещано. Например, при k = 1, 2, 3 имеем, соответственно, (x; y) = (2; 1), (15; 6), (104; 40).
Замечание. Строго говоря, надо бы проверить, что всякая пара чисел x; y = 2k2k +1; 2k-12k удовлетворяет равенству x - y + 1 x - y = xy . Немного подумав, можно понять, что это очевидно: двигаться 'снизу вверх' по только что изложенному решению даже легче, чем 'сверху вниз'. Впрочем, можно обойтись и без использования интеллекта:
x - y = 2
k +12k

2 2 5Y - 5 2 X - 3Y = -4,

z 2 - 5t 2 = -4 ,
где z = 5Y = 5y 1 и t = 2X 3Y = 2x 3y + 1. Пора воспользоваться следствием из теоремы 7. А именно, все решения уравнения z 2 - 5t 2 = +4 в натуральных числах даются формулой z; t = n+1 + + n-1; n . При этом знаку '+' соответствуют четные n, а знаку '' нечетные. Осталось понять, при каких нечетных n число z = n+1 + n-1 дает остаток 4 при делении на 5. Выпишем остатки от деления нескольких первых чисел Фибоначчи на 5:
6 8 3 3 7 13 3 4 8 21 1 2 9 34 4 1 10 55 0 3 11 89 4 4 12 144 4 2 13 233 3 1 14 377 2

- 2

k-12k

= 2

k +1

- 2

k-1



2k = 2 2

k

и
x - y + 1 = 2k + 1 , 2

n n n mod 5 n-1 + n так что

+1

mod 5

1 1 1 1

2 1 1 3

3 2 2 4

4 3 3 2

5 5 0 1

2 (Мы воспользовались тождеством 2 k + 1 = 2 k+12 k-1 , которое является частным случаем тождества упражнения 20,а.)

x - y + 1 x - y = 2k + 12k = 2 k2 2 2

k +12 k-12 k

= xy .

Закономерность очевидна: n ? 3 mod 4 . z + 1 n-1 + n+1 + 1 = Итак, y = и 5 5

Мы решили уравнение

x - y + 1x - y = xy ,
применив довольно неожиданный трюк. Но есть и другой стандартный способ. А именно, есть стандартная схема, по которой решают в целых числах уравнения второй степени. Давайте посмотрим, как эта
3 Квант ? 4

t + 3y - 1 n + 3 = x= 2

n-1 + n 5 2

+1

+1

-1

=

=

n+1 + n+3 - 1 , 5

где n ? 3 m od 4 . Обозначив n = 4k 1, запишем эти + 4k+2 - 1 = 2k 2k+1 и формулы в виде x = 4k 5


10
y= 4
k-2

КВАНT 2002/?4

+ 4k + 1 = 2k-12k (мы воспользовались 5 m тождеством 2m + 2m+2 - -1 = 5m m+1 см. упражнение 42). Теорема 11 доказана.
Упражнения 41. Докажите, что если х, у натуральные числа, удовлетворяющие равенству x 2 - 3xy + y 2 + x - y = 0 и неравенству x ? y , то 2x ? 3y . 42. Докажите а) сравнение n+3 + n+5 ? n-1 + n+1 mod 5 ; 2 2 2 2 б) тождества 2 m = m+1 - m-1 и 2m +1 = m + m +1 ; m в) тождество 2 m + 2 m+2 = 5mm+1 + -1 .
2 n 43 (М905). Уравнение 4x + x + 1 = y относительно натуральных чисел x и y а) имеет бесконечно много решений при n = 2; б) не имеет решений, если n ? 2 и n натуральное число. Докажите это. 2

Лемма 4. Пусть a наименьшее натуральное число, для которого существует такое натуральное число b, что a 2 - db2 = 1 . Если x, y целые числа и 1 < x +

+ y d < a + b d , то x 2 - dy2 ? 1 . Доказательство. Предположим противное: x 2 - dy2 = 1 . Тогда в силу лемм 1 и 2 числа x и y положительны. В силу леммы 3 имеем x < a. Получили противоречие. Следующая теорема это другая формулировка теоремы 9. Теорема 12. Пусть a наименьшее натуральное число, для которого существует такое натуральное число b, что a 2 - db2 = 1 . Если x, y целые числа, x 2 - d y 2 = 1 и x + y d > 0 , то для некоторого целоn го числа n верно равенство x + y d = a + b d .
Доказательство. Обозначим q = a + b d . Поскольку числа a и b натуральные, то q > 1. Рассмотрим возрастающую геометрическую прогрессию:

Использование иррациональностей
Неравенства, неравенства, неравенства... Есть ощущение какого-то фокуса, когда все сходится, но причина удачи спрятана и не видна наивному зрителю. Сейчас мы докажем теорему 9 заново. Надеемся, этим мы поможем вам вполне уяснить доказательство этой теоремы. 2 2 Лемма 1. Если x - dy > 0 и x + y d > 0 , то x > 0. Доказательство.

1 < q < q2 < q 3 < q4 < q5 < K
Она стремится к бесконечности. А убывающая геометрическая прогрессия 1 1 1 1 1 1> > 2 > 3 > 4 > 5 >K qq q q q стремится к нулю. Поэтому существует такое целое n, что
q
n-1

x2 - dy2 >0. 2x = x + y d + x+y d Есть и другой способ 'от противного'. Предположим, что x ? 0 . Тогда обе части неравенства y d >-x можно возвести в квадрат:
dy > x ,
2 2

< x + y d ? qn .
n-1

Рассмотрим число

E = x + y d : q

.

Очевидно, 1 < E ? q . Поскольку

что противоречит неравенству x 2 - dy 2 > 0. Лемма 2. Если x 2 - dy2 = 1 и x + y d > 1 , то y > > 0. Доказательство. Пусть y ? 0 . Тогда

a -b d 1 1 = = = q a + b d a - b d a + b d
= то

x - y d ? x + y d > 1.
Произведение чисел x - y d и x + y d , каждое из которых больше 1, не может равняться 1. Лемма 3. Если a 2 - db2 = x 2 - dy 2 и x + y d < < a + b d , причем числа a, b, x и y неотрицательные, то x < a и y < b. Доказательство.
x 2 - dy 2 a 2 - db 2 = x-y d . < x+y d a +b d Сложив неравенства

a -b d = a -b d , a 2 - db 2

E = x + y d a - b d



n-1

.

Воспользовавшись формулой

r

+ s d u + v d = ru + dsv + rv + su d ,

a -b d =

мы заключаем, что число E представимо в виде E = z + t d , где z, t целые числа. Переходя к сопряженным числам, получаем

z - t d = x - y d a + b d
Следовательно,



n-1

.

-x + y d < -a + b d
и

z 2 - dt 2 = z + t d z - t d =
= x + y d x - y d a - b d = x2 -

x +y d < a +b d ,
получаем 2 y d < 2b d . Дальнейшее очевидно.



a dy2 a 2

n-1

+b d - db
2

n-1

n-1

= = 1.


УРАВНЕНИЯ

ПЕЛЛЯ

11

Итак, числа z и t целые, 1 < z + t d ? a + b d и z 2 - d t 2 = 1 . В силу леммы 4 это возможно лишь в случае равенства z + t d = a + b d , т.е. в случае

x + y d = qn ,
что и требовалось доказать.
Упражнение 44. Пусть a наименьшее натуральное число, для которого существует такое натуральное число b, что a 2 - db 2 = 1 . Если x, y целые числа и x 2 - dy 2 = 1 , то для некоторого целого числа n имеем x + y d =

видны. Докажем второе. Пусть z; t О M. Тогда c z -t d = , z +t d так что

z-t d < c
и, следовательно,

z=

z

+ t d + z - t d 2



<

q+ c , 2 q+ c 2d
.

= + a + b d



n

. Докажите это. Уравнение x 2 - dy 2 = c

t=

z

+ t d - z - t d 2



<

Доказательство теоремы 12 могло показаться довольно длинным. Не вполне ясно, что проще: жонглировать неравенствами или иррациональностями. Оказывается, однако, что использованное при доказательстве теоремы 12 рассуждение позволяет выяснить, как устроены решения в целых числах уравнения x 2 - dy2 = c . Напомним обозначения. Как и прежде, d натуральное число, не являющееся квадратом; a наименьшее натуральное число, для которого существует такое натуральное число b, что a 2 - db2 = 1 ; q = a + b d ; наконец, c некоторое целое число, c ? 0 . Пусть x и y ц елые числа, x 2 - dy2 = c и x + y d > 0 . Рассмотрим числа вида qn , где n пробегает множество всех целых чисел. Поскольку lim q n = 0 и lim qn = +? , то существует такое целое число n, что
n R-? n R+?

Теорема 13 доказана.
Упражнения 45. Уравнение x 2 - 11y 2 = 17 не имеет решений в целых числа. Докажите это. 46. Найдите все наборы а) 11; б) 23 последовательных чисел, сумма квадратов которых является квадратом целого числа. 47. Найдите все такие натуральные числа х, что число, получаемое зачеркиванием последней цифры числа x 2 , тоже является квадратом натурального числа. (А.Балахонкин и Ф.Кац, девятиклассники школы 131, Казань). 48. Решите в целых числах уравнение а) x 2 - 17y 2 = -16 ; б) x 2 - n 2 + 1 y = -1 , где n натуральное число. 49. Если уравнение x 2 - dy 2 = -1 имеет решение в натуральных числах х и у, то выбрав из таких решений то, 2 где х наименьшее возможное, получим а) q = x + y d ; б) M = 1. Докажите это. 50. При a ? 2 уравнение x 2 - a 2 + 1 y 2 = -a 2 имеет не менее трех серий решений, т.е. множество М для него состоит не менее чем из трех элементов. Докажите это. 51. Пусть р простое число, p 1( mod 4 ) , a наибольшее (существующее в силу теоремы 10) натуральное число, для которого существует такое натуральное число b, что a 2 pb 2 = 1 . Докажите, что а) a нечетно; б) для некоторых 2 натуральных чисел u и v верны равенства a + 1 = 2u , 2 2 2 a + 1 = 2 pv и b = 2uv ; в) u pv = 1 . 52*. Решите в натуральных числах уравнение













q

n-1

< x + y d ? qn .

Рассмотрим число
E = x+y d :q





n-1

.

Легко понять, что E представимо в виде

E = z +t d ,
где z и t целые числа. При этом
z 2 - dt 2 = c

(* ) ( ** )

а) 3 s = 2r + 1 ; б) x 2 + 2y = 3z . 53. Решите в целых числах уравнение а) x 2 + 8xy + y 2 + 2 x - 4y + 1 = 0 ; б) 3u 2 + 11uv + 9v 2 + u + v = 0 .

и

1< z +t d ? q .

(Продолжение следует)
Информацию о журнале 'Квант' и некоторые материалы из журнала можно найти в ИНТЕРНЕТЕ по адресам: Курьер образования http://www.courier.com.ru Vivos Voco! http://vivovoco.nns.ru (раздел 'Из номера') Московский детский клуб 'Компьютер' math.child.ru

Теорема 13. Рассмотрим всевозможные пары целых чисел (z; t), удовлетворяющие условиям ( * ) и ( ** ). Верны следующие утверждения. 1) Если множество M таких пар пусто, то уравне2 2 ние x - dy = c не имеет решений в целых числах x и y. 2) Множество M конечно. 3) Все целочисленные решения уравнения 2 x - dy2 = c можно получить из формул x + y d = = + z + t d q n , где z; t О M, а n целое число. Доказательство. Первое и третье утверждения оче-





3*