Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2002/06/13.pdf Дата изменения: Fri Dec 23 19:27:08 2005 Дата индексирования: Tue Oct 2 00:10:14 2012 Кодировка: Windows-1251 Поисковые слова: m 8

УРАВНЕНИЯ

ПЕЛЛЯ

13
1 - {b} 1 , N +1

Упражнения 55. Выполнив еще пять шагов циклического метода, найдите решение 488422 - 67 59672 = 1 . 56. а) Выполните вычисления для d = 67, применяя английский метод. б) Сравнив английский и циклический методы для d = 67 и для нескольких других значений d, сформулируйте гипотезу о взаимосвязи этих двух методов.

то годится a = [b ] ; если же

то можно взять a = [b ] + 1. Лемма доказана.
Упражнения 57. Для любых чисел 1, 2 , K , k и любого натурального числа N существуют такие целые числа b1, b2, K , bk и a, хотя бы одно из которых отлично от нуля, что абсолютные величины чисел b1, b2, K , bk не превосходят N и 1 b11 + b22 + K + bkk - a ? k . N +1 Докажите это. 58. Для любых чисел 1, 2 , K , k и любого натурального числа N существует такое натуральное число b, что b ? N k и дробные части чисел b1, b2, K , bk не превосходят 1/N. Докажите это. Доказательство теоремы 10

Если вы решили эти два упражнения, то убедились, что индийский и английский методы позволяют найти решение для d = 67. Однако ни для английского, ни для индийского метода нет никаких очевидных причин, по которым равенство с правой частью 1 должно обязательно получиться в общем случае. Есть и много других вопросов. Например, если эти методы дадут нам какоето решение уравнения Пелля, можно ли утверждать, что это решение наименьшее из возможных? Я уверен, что попытка самостоятельно разобраться в этих вопросах будет очень полезной. Любитель компьютеров может начать с написания английской и индийской программ, которые вычислят приведенную выше таблицу. А вот для обоснования циклического или английского метода (а лучше бы обоих!) вам придется создать чуть ли не целую теорию! Но даже если у вас ничего не получится (а у большинства, вы уж не обижайтесь, действительно ничего не получится, поскольку задача очень сложна даже для тех, кто успешно справляется с 'Задачником 'Кванта'), это будет очень полезно.

Положим = d . Для любого натурального n > 1 в силу леммы существуют такие натуральные числа an и bn , что bn < n и 1 an - bn d ? . n Очевидно,
2 2 an - dbn = an - bn d Ч an + bn d ?

?

Доказательство существования
Приближения иррациональных чисел рациональными

1ж1 1 ц an - bn d + 2bn d ? з + 2n d ч < 1 + 2 d . n иn ш n

Теорему 10 можно доказать, рассматривая приближения числа d рациональными числами. Для этого сначала сформулирую и докажу следующую лемму. Лемма. Для любого вещественного числа и любого натурального числа N существуют такие целое число a и натуральное число b, что b N и
b - a 1 . N +1

2 2 Итак, величина an - dbn может принимать лишь конечное число значений. Но n можно брать сколь угодно 1 большим! И при этом в силу неравенства an - bn d ? n при n R ? имеем bn R ? . Значит, хотя бы для одного целого числа c, по модулю меньшего 1 + 2 d , существует бесконечно много пар натуральных чисел an ; bn , для которых 2 2 an - dbn = c .

Доказательство. Рассмотрим числа 0 и 1, а также дробные части чисел , 2 , ..., N . Если бы все расстояния между этими (N + 2)-мя числами были больше 1/(N + 1), то получилось бы противоречие. Значит, какое-то из расстояний не превосходит 1/(N + 1). Если

Зафиксируем одно из таких чисел c. Рассмотрим остатки от деления чисел an и bn на |c|. Поскольку количество остатков конечно, то существуют такие две 5 разные пары натуральных чисел a; b и A; B , что и
a2 - db2 = c = A2 - dB
2

{b2 } - {b1}
где 1 b1 < b2 N , то



1 , N +1

a? A b?B

mod c mod c

, .

(Продумайте это!) Рассмотрим частное

(b2

- [b2 ]) - (b1- [b1

])



1 , N +1

так что достаточно взять b = b2 - b1 и a = [b2 ] - [b1] . Остальные два случая столь же очевидны: если

a -b d A+ B d A+B d = = a +b d a2 - db2 aA - bBd + aB - Ab = c









d

.

{b}
4 Квант ? 6

-0

1 , N +1

5 На самом деле даже не две, а бесконечно много, но нам это не нужно.