Ю.В. Нестеренко - Курс лекций по теории чисел, страница 2

В 1937 году И. М. Виноградов доказал, что каждое нечётное число представимо в видесуммы трёх простых.А вот пример уравнения в целых числах (уравнение Пелля), которое очень непросто решить прямым перебором: x2 − 109y 2 = 1. Его минимальное по модулю решение (xmin , ymin ) = (158070671986249, 15140424455100).1.2. Основная теорема арифметикиТеорема 1.4 (Основная теорема арифметики). Для любого натурального m существует и единственαt1но его представление в виде m = pα1 · .

. . · pt , где pi — простые числа.Существование такого разложения легко доказывается по индукции. Мы не будем проводить его здесь.Единственность легко доказывается с помощью двух полезных лемм, приведённых ниже.Лемма 1.5 (О линейном представлении НОД). Если (a, b) = d, то существуют числа x, y ∈ Z, такиечто d = ax + by.Мы приведём два доказательства этой леммы. Одно — так называемое неэффективное (поскольку не даётявных значений x и y), а второе — эффективное (то есть даёт явный алгоритм построения чисел x и y). 1◦ Неэффективное: рассмотрим множествоM = {m = ax + by | m > 0, x, y ∈ Z} .(1)Пусть d = (a, b). Тогда, очевидно, для любого m ∈ M имеем d m.

Пусть z — минимальное числов M . Число dделит z как и всякое прочее число из M . Пусть m — произвольное число из M . Докажем, что z m. Предположим,что это не так. Разделим m на z с остатком: m = qz + m′ , 0 < m′ < z. Тогда m′ = m − qz — это линейнаякомбинация чисел из M , поэтому m′ тоже является числом из M . Это противоречитминимальности z в M .Поэтому z m. А поскольку m — произвольное число из M , то, в частности, z a и z b, поскольку a, b ∈ M .4Следовательно, z (a, b) = d.

С другой стороны, d z, поскольку z ∈ M . Значит, z = d. А так как z имеет видax + by, числа x и y найдены.2◦ Алгоритмическое: Проводим алгоритм Евклида, который выглядит так:a = q1 b + r1 ,b = q2 r1 + r2 ,...rn = qn+2 rn+1 + rn+2 ,(2)rn+1 = qn+3 rn+2 .Легко видеть, что rn+2 = (a, b). Теперь, чтобы найти x и y, нужно воспользоваться обратным ходом алгоритмаЕвклида. Именно, перепишем равенства в следующем виде:(a, b) = rn+2 = rn − qn+2 rn+1 ,rn+1 = rn−1 − qn+1 rn ,(3)...Затем последовательно выражаем остатки с большими номерами через остатки с меньшими номерами.

В итогеполучим представление вида (a, b) = rn+2 = ax + by. Лемма 1.6. Если a bc и (a, b) = 1, то a c. Имеем (a, b) = 1, значит, по предыдущей лемме найдутся x, y ∈ Z, для которых ax + by = 1. Умножим.это равенство на c, получим acx + bcy = c. По условию bc .. a, значит, левая часть равенства делится на a. Стало..быть, c . a. Вывод основной теоремы арифметики из этих лемм предоставляется читателю.2. Асимптотический закон распределения простых чиселМы будем обозначать через π(x) количество простых натуральных чисел, не превосходящих x.

Историяопределения асимптотики функции π(x) такова:• Евклид: π(x) → ∞ при x → ∞.• Эйлер:π(x)x→ 0 при x → ∞.• Чебышев (1848 г.): Если предел π(x)xln(x) существует, то он равен 1.• Адамар и Валле-Пуссен (1896 г.): π(x) ∼ lnxx .2.1. Оценки Чебышева для функции π(x)Мы докажем неравенстваaxx6 π(x) 6 b.ln xln x(1)Константы, которые получатся у нас, будут такими: a = ln22 ≈ 0.3465, а b = 5 ln 2 ≈ 3.4657. У Чебышеваконстанты были более точные: a ≈ 0.92129, b ≈ 1.10555.Лемма 2.1 (Нижняя оценка для НОК). K := [1, 2, 3, .

. . , 2n + 1] > 4n .n Рассмотрим функцию fn := x(1 − x) . Поскольку x(1 − x) < 14 всюду на отрезке [0, 1], за исключениемодной точки x = 12 , получаемZ1n1I :=x(1 − x) dx < n .(2)40Раскроем скобки, получим некоторый многочлен с целыми коэффициентами:fn = xn (1 − x)n = an xn + . . . + a2n x2n ,Проинтегрируем его:aj ∈ Z.(3)ana2n+ ...

+> 0,(4)n+12n + 1поскольку fn > 0 на (0, 1). Заметим, что число KI целое (все знаменатели убьёт множитель K). Оно положительное, поэтому по крайней мере KI > 1. Пользуясь оценкой для I, получаем, что K > 4n . I=5x6 π(x) для некоторой константы a.Теорема 2.2. При x > 6 выполнена оценка a ln(x) По всякому числу x можно однозначно определить натуральное n, такое что 2n + 1 6 x < 2n + 3.Рассмотрим K := [1, 2, 3, . . . , 2n + 1].

Рассмотрим разложение этого числа на простые множители:K = pk11 · . . . · pkr r .(5)Заметим, что каждое простое число в диапазоне от 1 до 2n + 1 входит в разложение K. Значит, r = π(2n + 1).Далее, pki i 6 2n + 1 при всех i. Следовательно, K 6 (2n + 1)π(2n+1) . С другой стороны, по предыдущей леммеимеем 4n < K. Следовательно,4n < (2n + 1)π(2n+1) .(6)Логарифмируя это неравенство, получаемπ(2n + 1) log2 (2n + 1) > n log2 4 = 2n⇒π(2n + 1) >x!2nx−3x2>>>a.

(7)log2 (2n + 1)log2 (2n + 1)log2 (2n + 1)ln xПереход, отмеченный «!», обусловлен неравенством x − 3 > x2 , справедливым при x > 6. QЛемма 2.3.p < 4x .p6x В силу монотонного возрастания функции 4x достаточно доказать это неравенство для натуральных x.Будем вести индукцию по x. При x = 2 и x = 3 это верно. Пусть теперь это неравенство верно для всех чисел,меньших чем x. Докажем, что оно верно и для x.QQЕсли x = 2m (m > 2), то всё доказано, посколькуp=p < 42m−1 < 4x .p62mp62m−1Пусть теперь x = 2m − 1. ИмеемYp6xp=Y p ·p6mYm<p62m−1p .(8)(2m−1)!Рассмотрим число Cm2m−1 = m!(m−1)! .

Заметим, что это (целое) число делится на любое простое число p, длякоторого m < p 6 2m − 1, потому что в знаменателе таких больших простых делителей не встречается. Значит,Y ..Cmp ,(9)2m−1 .m<p62m−1откуда следует, чтоYCm2m−1 >p.(10)m<p62m−1Пользуясь предположением индукции и полученной оценкой для второго множителя, получаемYp < 4 m Cm2m−1 .(11)p6xmДалее, поскольку Cm−12m−1 = C2m−1 и2m−1P2m−2Ck2m−1 = 22m−1 , имеет место оценка Cm= 4m−1 .

Пользуясь2m−1 6 2k=0Qей и неравенством (11), получаем, чтоp6xp < 4m · 4m−1 = 42m−1 = 4x , и шаг индукции полностью доказан. Теорема 2.4. π(x) 6 b lnxx для некоторой константы b. Обозначим k := π(x). Выпишем все простые числа, не превосходящие x: p1 < p2 < . .

. < pk 6 x.Перемножая очевидные неравенства i < pi по i = 1, . . . , k и используя предыдущую лемму, получаемYk! < p1 · p2 · . . . · pk =p < 4x .(12)p6xЛегко видеть, что(k!)2 = 1 · k · 2 · (k − 1) · . . . · (k − 1) · 2 · k · 1 > k k (так как каждая скобка > k).(13)k k/2 6 k! < 4x .(14)Таким образом, из (12) и (13) следует, что6Докажем, что k 6 5 logx x . Предположим, что это не так, и k > 5 logx x . Покажем, что22x> x4/5 .log2 x(15)x1> x4/5 ⇔ x1/5 > log2 x = log2 (x1/5 ) ⇔ t > log2 t,log2 x5(16)5Действительно,5а последнее неравенство всем хорошо известно. Пользуясь (15), получаем:kk/2> 5xlog2 x 52 logx2x5x> (x4/5 ) 2 log2 x = 4x ,а это противоречит (14). Итак,π(x) = k 6 5x,log2 x(17)(18)откуда следует утверждение теоремы.

Следствие 2.1. Пусть p1 < p2 < p3 < . . . — последовательность всех простых чисел. Тогда найдутсяконстанты α, β > 0, такие что αn ln n < pn < βn ln n. Пользуясь теоремами 2.2 и 2.4, получаем:apnpn6 π(pn ) = n 6 b.ln pnln pn(19)Возьмём ln от этого неравенства:ln a + ln pn − ln ln pn 6 ln n 6 ln b + ln pn − ln ln pn .(20)Теперь перемножим (19) и (20) и получим:apn γn 6 n ln n 6 bpn δnПоэтому0<α6где γn , δn → 1 при n → ∞.(21)pn6 β,n ln n(22)что и требовалось доказать.

P1Следствие 2.2.p расходится.P 1 Имеем pn 6 βn ln n, а рядn ln n расходится. 2.2. Функция Чебышева и ее связь с π(x)Определение. Функцией Чебышева называется функцияX ln x ψ(x) =ln p.ln p(23)p6xЗаметим, чтоψ(x) =X ln x p6xln pln p 6X ln xX· ln p = ln x ·1 = ln x · π(x).ln pp6xОпределение. Функцией Мангольдта называется функция:(ln p, m = pα ,Λ(m) =0иначе.Заметим, чтоhln xln pi(24)p6x(25)= # {a ∈ N : pa 6 x}. ПоэтомуXm6xΛ(m) =Xpa 6xΛ(pa ) =Xpa 6x7ln p =X ln x p6xln pln p = ψ(x).(26)Утверждение 2.5.

π(x) ∼ lnxx ⇔ ψ(x) ∼ x. Сначала докажем прямое утверждение.⇒ Пусть 12 < β < 1, тогдаπ(x) − xβ β ln x 6 π(x) − π xβ ln xβ 6XX ln x !!ln p 6 ψ(x) 6 π(x) ln x.ln pβ!ln p =xβ <p6x(27)x <p6xhixln xПереход «!» обусловлен тем, что p > xβ > x1/2 , значит, ln<2,поэтомуln pln p = 1. Что касается перехода «!!»,то он следует из неравенства (24).Итак,β ln x π(x) − xβ 6 ψ(x) 6 ln x · π(x).(28)Разделим это неравенство на x:−β ln xβπ(x)ψ(x)π(x)+66.x1−βx/ ln xxx/ ln xЗададим ε > 0. Пусть β = 1 − ε.

Тогда найдется x0 (ε), для которого если x > x0 (ε), то 1 − ε <(по предположению теоремы) и lnxεx < ε. Поэтому(1 − ε)(−ε + 1 − ε) 6(29)π(x)x/ ln x< 1+εψ(x)6 1 + ε.x(30)А это и означает, что ψ(x) ∼ x.⇐ Из неравенств предыдущего пункта не сложно составить следующее соотношение:ψ(x)π(x)1 ψ(x)ln x66+ 1−β .xx/ ln xβ xxОпять рассмотрим ε > 0. Положим β = 1−ε. Тогда найдется x0 (ε) такое, что если x > x0 (ε), то 1−ε <(по предположению теоремы) и lnxεx < ε. Поэтому1−ε6А это и означает, что π(x) ∼Введем новую функциюxln x .π(x)16(1 + ε) + ε.x/ ln x1−ε(31)ψ(x)x< 1+ε(32)ω(x) =Zxψ(t)dt.t(33)1Утверждение 2.6.