Учебник по теории чисел Ильиных АП

Доказательство. По теореме 1 сравнение имеет единственное решение. Рассмотрим число x0 = aϕ(m)−1b и подставим его в правую часть сравнения. Получим aaϕ(m)−1b = aϕ(m)b ≡ b (mod m), т.е. x0 — решение сравнения.

Теорема доказана.

Однако, полученная формула (7) не является удобной для использования, так как число aϕ(m)−1b может быть весьма большим. Решение сравнения по модулю m желательно иметь в виде a¯, где 0 6 a < m.

Более удобные формулы будут получены с помощью теории непрерывных дробей.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Лекция 11. Непрерывные дроби.

Пусть α —произвольное действительное число. Рассмотрим q1 = [α] — целую часть от числа α. Поэтому q1 — наибольшее целое число не превосходящее α. Запишем число α в виде α = q1 + α0, где α0 = α − q1 — дробная часть от α.

Тогда 0 6 α0 < 1. Если α0 6= 0 (т.е. α / Z), то представим α0 в виде α0 = 1 ,

α1

где α1 > 1. Тогда

α = q1	+	1				(1)
		α1
Повторив данные действия для α1, запишем α1 = q2 +						1	. Подставив в (1),
получим						α2
	1
α = q1 +
	q2 +		1
			α2

Применим те же действия к α2, и т.д. Возможен один из следующих случаев 1) или 2).

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

1) Некоторое число αn является целым и процесс оборвется. Получим

α1 = q1 +			1		(2)
	q2 +		1
			1
	q3		+ ... +
			1

qn−1 + qn

2) Никакое число αi не является целым и процесс бесконечен. Этот случай

	отображаем записью
	α = q1 +	1	(3)
		1

q2 + q3 + ...

Выражения в правых частях (2) и (3) называем непрерывной дробью, соответствующей числу α.

Вслучае 1) имеем конечную непрерывную дробь, которую обозначаем [q1, q2, . . . , qn]

Вслучае 2) имеем бесконечную непрерывную дробь [q1, q2, q3, . . . ].

ТЕОРЕМА 1 Действительное число α тогда и только тогда представимо в виде конечной непрерывной дроби, когда оно является рациональным числом.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Доказательство. Пусть α представимо в виде конечной непрерывной дроби (2). Начнем свертывать эту дробь с конца, приводя к общему знаменателю.

Вместо q

1

запишем дробь

a1

qnqn−1 + 1

. Далее преобразуем

n−1

+

=

qn

b1

qn

qn−2 +

1

= qn−2 +

b1

1

a1

qn−1 +

qn

a2

a

, где a, b Z, т.е. α — рациональное число.

к виду

и т.д. Получим α =

b2

b

Обратно, пусть α =

a

— произвольное рациональное число. Для представ-

b

ления числа α в виде конечной дроби применяется алгоритм Евклида. Разделим a на b. Получим a = bq1 + r1, где 0 6 r1 < b. Тогда

a	= q1	+	r1	= q1	+	1
b			b				b
						r1

Далее разделим b на r1, получим b = r1q2 + r2, откуда

b		r2	1
	= q2 +		= q2 +				.
r1		r1			r1

r2

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

и

a		= q2 +	1
b			1
			q2 +
					r1
					r2

Продолжая процесс делений в алгоритме Евклида, для некоторого n получим,

a = bq1 + r1 b = r1q2 + r2

r1 = r2q3 + r3 (4)

. . .

rn−3 = rn−2qn−1 + rn−1 rn−2 = rn−1qn

что некоторое qn — целое. Тогда rn−2 = qn — целое число, процесс обры-

rn−1

вается. Мы получили представление α в виде конечной дроби. При этом α = [q1, q2, . . . , qn].

Теорема доказана.

ЗАМЕЧАНИЕ. Числа q1, q2, . . . , qn из конечной непрерывной дроби (2)— это неполные частные из алгоритма Евклида для чисел a и b.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

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

Свойства непрерывных дробей. Пусть число α представлено в виде конечной непрерывной дроби (2) или бесконечной дроби (3).

Отбросим в непрерывной дроби выражение, стоящие после q1. Получим

дробь

P1 = q1 . Q1 1

Отбросывая выражение, после q2, имеем дробь

P2 = g2q1 + 1.

Q2 q2

Отбросим выражение, после q2. Получим дробь P3 и т.д.

Q3

Дроби P1 , P2 , . . . называются подходящими дробями для числа α.

Q1 Q2

Подходящая дробь с номером i имеет числитель Pi и знаменатель Qi. При этом

P1 = q1, Q1 = 1 P2 = q2q1 + 1, Q2 = q2, . . .

(5)

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Дополнительно определим дробь P0 , где P0 = 1, Q0 = 0, она потребуется

Q0

для единообразия формул.

СВОЙСТВО 1 Для числителей и знаменателей подходящих дробей, справедливы формулы

Pi = qi · Pi−1 + Pi−2,	(6)
Qi = qi · Qi−1 + Qi−2,	(7)

где i > 2.

Доказательство формул индукцией по числу i. Пусть i = 2. Нужно проверить, что

P2	= q2	· P1 + P0,	(8)
Q2	= q2	· Q1 + Q0.	(9)

По (5) имеем P1 = q1, Q1 = 1 P2 = q2q1 + 1, Q2 = q2. Кроме того, мы задали P0 = 1, Q0 = 0. Подставив эти зачения в (8) и (9), получим верные равенства.

Пусть утверждение верно для числа i, т.е. справедивы равенства (6) и (7). Проверим выполнение утверждения для числа i + 1, т.е. справедивость ра-

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

венств

Pi+1 = qi+1 · Pi + Pi−1,

(10)

Qi+1 = qi+1 · Qi + Qi−1.

(11)

Подходящая дробь

Pi+1

получается из подходящая дроби

Pi

заменой в бук-

Qi+1

Qi

венном выражении для Pi выражения qi на выражение qi

+

1

. Поэтому в

дроби

qi+1

qi · Pi−1 + Pi−2

Pi

=

Qi

qi · Qi−1 + Qi−2

заменим букву qi на выражение qi +

1

.

Получим

qi+1

1

Pi+1

qi +

· Pi−1

+ Pi−2

qi+1(qiPi−1 + Pi−2) + Pi−1

=

qi+1

=

(12)

1

Qi+1

qi +

· Qi−1

+ Qi−2

qi+1(qiQi−1 + Qi−2) + Qi−1

qi+1

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

По индукции верны равенства (6) и (7). Применяя их, получаем

	Pi+1	=	qi+1Pi + Pi−1	(13)
	Qi+1
			qi+1Qi + Qi−1
и равенства (10) и (11), что и нужно.
СВОЙСТВО 2 Для всех i = 1, 2, . . . справедливо равенство
Pi · Qi−1 − Pi−1 · Qi = (−1)i.				(14)
Доказательство индукцией по i. Пусть i = 1. Имеем P1 · Q0 − P0				· Q1 =

q1 · 0 + 1 · 1 = −1, что и нужно. Пусть утверждение верно для числа i, т.е. верно равенство (14). Проверим истинность утверждения для числа i + 1, т.е. справедливость равенства

Pi+1 · Qi − Pi · Qi+1 = (−1)i+1.

По (10) и (11) имеем

Pi+1 · Qi − Pi · Qi+1 = (qi+1Pi + Pi−1) · Qi − Pi · (qi+1Qi + Qi−1) =

= Pi−1Qi − PiQi−1 = −(PiQi−1 − Pi−1Qi) = (−1)(−1)i = (−1)i+1,

что и нужно.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

СВОЙСТВО 3 Подходящие дроби Pi несократимы.

Qi

Доказательство от противного. Пусть d = (Pi, Qi) и d > 1. Тогда d делит левую часть равенства Pi · Qi−1 − Pi−1 · Qi = (−1)i, а, поэтому и делит правую часть (−1)i = ±1, противоречие.

Из свойства 2 получается формула для разности двух соседних подходящих дробей.

СВОЙСТВО 4 Для всех i = 1, 2, . . . справедливо равенство

				Pi	Pi−1	=	(−1)i	.		(15)
			Qi
					− Qi−1		QiQi−1
Доказательство. Имеем
	Pi	Pi−1	=		Pi · Qi−1 − Pi−1Qi				=	(−1)i	.
	Qi
		− Qi−1			QiQi−1					QiQi−1

Отсюда получаем расстояние между двумя соседними подходящими дробями

	Pi		Pi−1		1
Qi		− Qi−1			= QiQi−1 .

СВОЙСТВО 5 Пусть Pi подходящая дробь для числа α с номером i,

Qi

отличная от последней дроби ( т.е. от самого числа α ). Тогда

След Пред Стр Начало Оглавление Обратно Меню Экран Выход