Определение Множество натуральных чисел

Доказательство. Сначала докажем, что разложение существует. Пусть n Z\{-l,0,l}. Доказывать будем индукцией по |n|. Если |n| = 2, то n= ε-2, где ε= ±1, — база индукции. Пусть для всех чисел а Z \ {-1,0,1}, |а| < |n|, уже доказано существование нужного представ­ления. Докажем, что для n такое представление тоже возможно.
Если |n| — простое число, то, обозначив его |n| ⁼ p₁, получим п = ±|n| = ±εp₁, где ε= ±1.
Пусть теперь число п составное, |n| > 1, то есть существует нетри­виальный делитель а (a≠±1, а≠±п) числа n. Тогда существует такое целое число b, что n =ab, где b ≠ ±1, b ≠ ±n. Поскольку |n| > 1, справед­ливо равенство для абсолютных величин: |n| = |ab| = |а| • |b| > |а|.
Аналогично |n| >|b| поэтому к числам а и b применимо предполо­жение индукции:
a = ε₁p₁p₂...p_k, b = ε₂q₁q₂...q_l
где числа р_i, q_i простые, ε₁, ε₂ ±1.
Произведение ab дает требуемое представление. Существование представления доказано.
Теперь докажем единственность.
Пусть n = ε₁p₁p₂...p_k = ε₂q₁q₂...q_l, где числа р_i, q_i простые, ε₁, ε₂ ±1.Тогда ε₁= ε₂ = 1 при n > 0 ε₁= ε₂ = -1 при n< 0.
Далее, p₁p₂...p_k = q₁q₂...q_l, тогда по свойству 5 простых чисел k = l и числа q₁q₂...q_l можно перенумеровать так, что p₁= q₁, p₂= q_2,… p_k= q_l.
Представление числа n Z\{-l,0,1} в виде n = εp₁^α1 p₂ ^α2...p_s ^αs, где ε=±1, p₁p₂...p_s — различные простые числа, α_i≥ 1 для i= 1, 2, .... s, s ≥1, называется каноническим разложением числа n.
1.4.2. Распределение простых чисел
Следующие две теоремы называются теоремами Евклида о про­стых числах.
Теорема1.12. Простых чисел бесконечно много.
Доказательство. Проведем от противного. Пусть утверждение не­верно и p₁, р₂, .... р_s — все простые числа. Составим новое число: п=р₁р₂...р_s+1 и представим его в виде n= εp₁^α1p₂^α2...p_s^αs . Перенумеруем простые числа так, чтобы α1=0. Тогда число n= εp₁^α1p₂^α2...p_s^αs =р₁р₂...р_s+1. Левая часть делиться на р₁ и правая часть следовательно делиться на р₁. Отсюда р₁= 1 — не простое число. Противоречие доказывает теорему. □
Теорема1.13. Существуют сколь угодно длинные отрезки на­турального ряда, не содержащие простых чисел, то есть для любого k≥1 существует такое n N, что числа n+ 1,n+ 2,…, n+k - составные.
Доказательство. Рассмотрим число n = (k+1)!+1. При k≥1 вы­полняется неравенство n≥3. Тогда n+1 = (k+1)! + 2 = 1∙2∙...∙(k+1)+2 делится на 2 (и не равно 2), n+2 = (k+1)! + 3 = 1∙2∙3∙...∙(k+1)+3 делится на 3 (и не равно 3) и т.д. Число n+k = (k+1)! + (k+1) = 1∙2∙...∙(k+1)+(k+1) делится на k+1 (и не равно k+1).□

Если выписать подряд все простые числа, то можно заметить, что относительная плотность их убывает: от 1 до 10 — четыре простых чис­ла, то есть 40 % целых чисел являются простыми, от 1 до 100 — 25 про­стых чисел (25 %), от 1 до 1000 — 168 простых чисел (17 %), от 1 до 10⁵ — 9 592 простых числа (менее 10 %).

Обозначим число всех простых чисел, не превосходящих x. Из первой теоремы Евклида о простых числах следует, что при . Еще в XVIII веке Л. Эйлер установил, что простых чисел «мно­го» в том смысле, что , и в то же время большинство натуральных чисел — составные, поскольку .

В 1851-52 году П.Л.Чебышев показал, что функция растет так же, как функция , а именно, что существуют такие постоянные и , что для любого х ≥2 выполняется неравенство

В 1896 году Ж. Адамаром и Ш. Ла Валле Пуссеном независимо
был получен асимптотический закон распределения простых чисел:


Глава 2


СРАВНЕНИЯ С ОДНИМ НЕИЗВЕСТНЫМ


2.1. Отношение сравнимости
Определение2.1. Пусть . Целые числа аи bна­зываются сравнимыми по модулю т (обозначается ), если разность делится на т.
Отношение сравнимости обладает следующими свойствами.

1. 
   Рефлексивность: ).
   

1. 
   Симметричность: если , то .
   
2. 
   Транзитивность: если , и , то .
   

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

Доказательство. Из определения отношения сравнимости имеем: делится на т, делится на m. Тогда, по свойству 2 делимо­сти, сумма и разность делятся на т, откуда делится на т. □

5. 
   Сравнения можно почленно перемножать: если , , то .
   

Доказательство. Покажем, что разность делится на т. Прибавим к этому выражению и вычтем из него число . Получим: . Так как оба слагаемых в последней сумме делятся на т, то и вся сумма делится на т. □

6. 
   Обе части сравнения и модуль можно разделить на их общий делитель: если , то .
   

Доказательство. Выражение означает, что раз­ность ас−bс делится на тс, то есть, по определению делимости, суще­ствует такое целое число d, что ас − bc = mcd. Вынесем общий множи­тель c за скобки: (a − b)c = mcd. Тогда а − b = md, то есть a−bделится на m. □

7. 
   Обе части сравнения можно разделить на их общий делитель d, если d взаимно прост с модулем.
   

Доказательство. Пусть , где a = a₁d, b = b₁d, НОД(d, m)=l. По определению отношения сравнимости разность - делится на т. Числа d и mвзаимно просты, значит, по свойству 2 взаимно простых чисел, разность делится на т. □

8. 
   Если m₁ —делитель числа т и , то .
   
9. 
   Если — полином с целыми коэффициентами и , то .
   

Отношение, обладающее свойствами рефлексивности, симметрич­ности и транзитивности, называется отношением эквивалентности. Та­ким образом, отношение сравнимости является отношением эквивалентности на множестве целых чисел.
Отношение эквивалентности разбивает множество, на котором оно определено, на классы эквивалентности. Любые два класса эквивалент­ности либо не пересекаются, либо совпадают.
Классы эквивалентности, определяемые отношением сравнимости, называются классами вычетов по модулю т. Класс вычетов, содержа­щий число а, обозначается a(mod т) или и представляет собой мно­жество чисел вида a+km, где ; число а называется представителем этого класса вычетов.
Множество классов вычетов по модулю m обозначается , со­стоит ровно из т элементов и относительно операций сложения и умно­жения является кольцом классов вычетов по модулю т.
Определение 2.2. Полной системой вычетов по модулю m называется совокупность m целых чисел, содержащая точно по одному представителю из каждого класса вычетов по модулю m. Совокупность чисел 0, 1, 2,…, m−1 называется системой наименьших неотрицательных вычетов. Совокупность чисел
при нечётном m;
при чётном m
называется системой абсолютно наименьших вычетов по модулю т. Каждый из абсолютно наименьших вычетов по абсолютной ветчине не превосходит половины модуля. Часть полной системы вычетов, состоя­щая из чисел, взаимно простых с модулем, называется приведенной сис­темой вычетов.
Определение2.3. Функция , ставящая в соответст­вие каждому натуральному числу т количество натуральных чи­сел, меньших т и взаимно простых с т, называется функцией Эйлера. При этом полагают .
Таким образом, функция Эйлера задаст число элементов при­веденной системы вычетов по модулю т.
Теорема 2.1(Эйлер). Пусть число m>1 натуральное. Тогда для любого целого числа а, взаимно простого с т, выполняется сравне­ние .
Доказательство [2]. Пусть — приведенная система
вычетов по модулю т, составленная из наименьших неотрицательных
вычетов. Сопоставим каждому из чисел его наименьший неотрицательный вычет , где , то есть , ,..., , и покажем, что сис­темы вычетов и совпадают с точностью до порядка элементов.
Действительно, поскольку НОД(а, т)=1 (по условию теоремы) и НОД( , m) = 1 для всех i=1,2,..., (по определению приведенной системы вычетов), то по свойству 3 взаимно простых чисел НОД( , т) = 1 для всех i=1, 2,..., . Из сравнения следует существование такого целого числа z_i ,что где i = 1, 2,..., . Тогда, согласно лемме 1.6, НОД( т)= НОД( , т)=НОД( т)= 1, то есть наименьшие неотрицательные вычеты вза­имно просты с числом т. Значит, каждому из чисел соответствует не­которое число .
Осталось показать, что все числа различны. Дейст­вительно, если выполняется равенство , то . Числа аит взаимно просты, поэтому можем поделить обе части сравнения на а. Получим . Но — наименьшие неотрицательные вычеты, тогда должно выполняться равенство , а это не так. Значит, и среди чисел нет одинаковых, и эти две системы вычетов совпадают.
Перемножаем: .Поскольку , поделим обе части предыдущего срав­нения на одно и то же число (а это сделать можно, так как система при­веденная, и произведение взаимно просто с т), получаем . □
Теорема 2.2 (малая теорема Ферма). Пусть число p простое, число а целое, а не делится на р. Тогда .

Рассмотрим способ вычисления функции Эйлера.

Теорема2.3. Если число р простое, число n натуральное, то .
Доказательство. Число р простое, тогда любое число а, не пре­восходящее и не взаимно простое с , делится на р, то есть является элементом множества Р = {р, 2р, ..., }. Функция Эйлера будет
задавать число элементов множества {р, 2р, ..., }\Р. Это число равно .
Из свойства мультипликативности функции Эйлера и теоремы 2.3 следует, что если число n > 1 и —его каноническое раз­ложение, то

Эту формулу называют формулой Эйлера. С ее помощью можно

дать еще одно доказательство первой теоремы Евклида о простых числах (теорема 1.12). Как и ранее, предположим, что p₁, p₂,…, p_s — все
простые числа, и составим число N=p₁p₂...p_s. Тогда должно выполняться равенство = 1 (все числа, не превосходящие N, должны делиться
хотя бы на одно из простых чисел р₁, р₂,…, р_s,). Но по формуле Эйлера