Файл: Чандрасекхаран, К. Введение в аналитическую теорию чисел.pdf

Скачать файл (5,40Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 29.10.2024

Просмотров: 74

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

26	Г л. II. Сравнения

Теорема 5 может быть использована для вычисления ц>(п). Каждое целое n > 1 может быть записано в виде

так что

ф (« )= П ф (р“1)- i=i

Следовательно, чтобы вычислить ф (п), достаточно знать значения ф(ра ) для всех простых чисел р. Очевидно, Ф( р ) = р — 1. Если а > 1 , рассмотрим полную систему вы четов по модулю ра , а именно 1, 2, ..., ра . Из этих чисел точно ра~1 не будут взаимно простыми с ра , а именно кратные р числа р, 2р, 3р, ..., ра . Следовательно,

Ф(Р ) = Р — Р = Р 1		------- •
	1	р !
Таким образом,
ф («) = П ф (р “1') =	П р“Ф	— т г )>
i=i	i=i v	р‘ '

или

Ф(я) = п П

Другое важное свойство функции ф сформулировано в следующей теореме:

Теорема 6. £ ф (d) = m.

dim

Доказательство. Пусть т — р“*. Делители числа т

i=i

имеют вид П Р ;‘> где О ^Рг^а,-. Следовательно, по

1=1

теореме 5

§ 3. Число решений сравнения

£ Ф( d) =			£	Ф (П Р?‘) =		S	П Ф(Р?‘) •
d\|m			(Pi....Pr)	l==^	(Pi.... Pr) t=*
			t)<pA< a A		0< p fc< a ft
Отсюда после перегруппировки членов мы получаем
	г	“г
ф W) = П £ ф (р ?£) =
£/1л	1=1	Р^О
	Г
=	П [ ф (1)+Ф(Р/)+ -				■!■ф !>?')]		=
	1=1
=	П	[!	Ь ( Р — 1) + Р,-(Рг— I ) '1'			••• + р “,‘-1 (р — М ]=
	1=1

= ГК‘=™-

1=1

§ 3. Число решений сравнения. Мы уже видели в этой главе, что если (а, т) — 1, то линейное сравнение

= c(modm) разрешимо и имеет единственное решение. Поставим теперь вопрос о числе решений полиномиаль ного сравнения

	а0хп + aijcn_1 +	... + a„ == 0(mod р),
где а0,	а\, ..., ап — целые	числа,	п > 1	и р — простое
число.	х — какое-либо
Если	х — какое-либо	решение	этого	сравнения, то

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

Полиномиальные сравнения могут иметь решения, а могут их не иметь. Например, сравнение x2= 3 (m o d 7 ) не имеет решений.

28	Г л. II. Сравнения
С другой	стороны, по	теореме Ферма (теорема 3 )
сравнение	хр~1= 1 (mod р)

имеет р— 1 решений х = \ , 2,		р— 1.
Так как x?-l= 1 (mod р), если р ф х,			то мы имеем
xP = x (m o d р)	для всех х, xP+1= x 2(modр)		и т. д. Следо

вательно, любая степень, большая р— 1, может быть ре дуцирована и можно считать, что п<.р. Далее мы пред

положим, что (а0,	р) = \. Это условие гарантирует,	что
степень сравнения в точности равна п.
Ответ на вопрос, поставленный в начале этого пара
графа, дает
Теорема 7 (Лагранж). Сравнение
а0хп-\-а\Хп~'	...-\-ап= § (хпо&р), (а0, р) = \,	(2)

имеет не более п решений.

Доказательство. Докажем теорему индукцией по п. Для п = 1 утверждение теоремы справедливо, посколь ку (ао, р) = \. Предположим теперь, что теорема спра ведлива для п— 1, и докажем ее справедливость для п. Если сравнение (2) не имеет решений, то доказывать нечего. Если же оно имеет решение, скажем х ь то

а0х* -f tZj х " - 1 + ... + fl„ = 0(modp).

(3)

Вычитая из (2) сравнение (3), мы получим сравнение

а0(хл — х") + ах(х”- 1 — х " - 1) + ...

■••+an- i ( * — Jfi) = 0 (modp), (4)

которому, очевидно, удовлетворяет каждое решение сравнения (2). Далее, мы можем переписать (4) в виде

(х—х,) (a0x™-1+ 6 1x " -2+ ...+ 6 „ _ 1)= 0 (m o d p ),

где Ь\, Ь2.......	Ьп- ! — целые числа, зависящие только от
Xi и ао, аи	..., ап-\■ Следовательно, каждое решение

сравнения (2) должно удовлетворять или сравнению х—Xi==0(mod р),

§ 3. Число решений сравнения	29
которое дает исходное решение х = х и	или сравнению
ao*n_I+ M n_2+...+&n-i==0 (modp),	(а0, р) = 1,

которое имеет степень п— 1 и по предположению индук ции не более n— 1 решений. В таком случае сравнение

(2) может иметь самое большее п решений, что и требо валось доказать.

ГЛАВА III

АППРОКСИМАЦИЯ ИРРАЦИОНАЛЬНЫХ ЧИСЕЛ РАЦИОНАЛЬНЫМИ И ТЕОРЕМА ГУРВИЦА

§ 1. Аппроксимация иррациональных чисел. Пусть g — действительное иррациональное число. Так как мно жество рациональных чисел плотно в множестве всех действительных чисел, то для данного е > 0 найдется та кое рациональное число h/k, что |g— h/k \< е . Наша зада

ча состоит в изучении разности \|g— h/k\| как	функции
от k.	0 < \| < 1 ,
Будем предполагать в дальнейшем, что	0 < \| < 1 ,
дробь h/k несократима и £ > 0 .

Теорема 1. Если g — иррациональное число и N — положительное целое число, то существует раииональное число h/k со знаменателем kss^N, такое, что

Доказательство. Для любого действительного числа х обозначим через [х] целую часть числа х, т. е. такое целое число т , что m ^x<Cm -f-1. Из иррациональности g следует, что 0 — [ ng] <l . Пусть п принимает зна чения 1, 2, ..., N. Тогда мы получим N различных чисел ng— [ng], каждое из которых лежит в открытом интер

вале (0, 1). Рассмотрим N подинтервалов (о, — V

Каждый из этих подинтерва

лов или содержит внутри себя точно одно из чисел ng—-

— [rag], или же существует подинтервал, содержащий бо лее одного из этих чисел. В первом случае интервал

(О, содержит число mg— [mg] при некотором це

лом т, таком, что l^ m ^ A f, и, следовательно, 0 < m g —

— [mg] < — . Таким образом, 0 < g — < — ’


§ 1. Аппроксимация иррациональных чисел		31
и тем самым мы нашли рациональное число h/k,		обла
дающее требуемым свойством.
Если подинтервал	(0, — ) не содержит ни одно из
чисел ng— [ng],	то существует другой подин

тервал, содержащий по меньшей мере два таких числа, скажем ng— [ng] и mg— [mg]. Тогда мы имеем два це лых числа т и п, Q X m < .n^ .N , таких, что

| ( n g - f n g ] ) - ( m g - [ m g ] ) | < ^ ,

или

I (п — т) g— (frag] — [mg])| < у .

Если мы положим п— m = k и [ng]— [m g ]= /i, то снова получим

где k < N .

Несколько более сильный результат дает

Теорема 2. Если g — иррациональное число и N — положительное целое число, то существует рациональное

число hjk со знаменателем k^.N, такое, что

		H N + 1)'
Доказательство. Теорема может быть доказана таким
же способом, что	и теорема	1. Пусть х0= 0 , Х\,	..., xN,
*л'+1 = 1 — набор	различных	чисел, состоящий	из 0, 1

и чисел nl— [ng], п= 1, 2, ..., N,	упорядоченных по возра
станию. Разности хп+\—х „ > 0	при п = 0, 1.......	N ирра
циональны, и их сумма равна 1. Следовательно,		хотя бы

для одного	значения п мы будем иметь хп+\—хп<
<C l/(A f+l).	Тогда существует рациональное число h/k,
такое, что

h 1

32	Г л. III. Аппроксимация иррациональных чисел
Другое доказательство теоремы 2 использует после
довательности Фарея.		Если FN — последовательность
Фарея	порядка N, то,	поскольку £ иррационально, мы
имеем	Fn при любом N. Но £ лежит между двумя по

следовательными дробями а/b и c/d, принадлежащими Fn. Пусть a/b<.% <c/d. Рассмотрим медианту (а +

+ c)/(b + d). Из гл. I мы знаем, что a /b c (a + c)/(b + d) <

C c/d . Следовательно, или а /6 < £ <				(a + c)/(b + d),			или
(a + c)/(b + d)<'&,<c/d. Так как alb				и c/d — последова
тельные члены в Fn, то			(a + c)l (b + d)<£ Fn.			Значит,
bJr d'^N-\-\. Поэтому или
О < Е— ~ <	а + с	а	be — ad	b (b + d)	^	b(N +	1) ’
ь	b Т- d	Ь	b (Ь+d)
ИЛИ		а+ с	be—ad		„
				1		1
		b-\-d	d(b+d)	-------- ^	---------- .
				d(b+d)	d(N +l)

Поскольку а/b и cld принадлежат FN, они несократимы и b ^ N , d^.N . Тем самым мы получили требуемое ра циональное приближение hjk (равное а/b или c/d).

Проверим теперь справедливость теоремы 2 в слу чае, когда | рационально, скажем, £= l/m , (I, т) = 1

и m > N . Тогда £^Ё Fn и мы можем .следовать данному выше доказательству, за исключением случая, когда £ = (a-\-c)/(b-\-d). В последнем случае мы не можем по ставить в теореме знак строгого неравенства и, таким образом, получаем следующий результат:

Теорема 3. Если £ — рациональное число, N — поло

жительное целое число и i,=l/m , (I, т) = 1, где m^>N, то существует неприводимая дробь h/k со знаменателем ks^.N такая, что