5. Простые и составные числа. Основная теорема арифметики.

Определение. Натуральное числоpназываетсяпростым,еслиp>1иpне имеет натуральных делителей, отличных от1иp.

Натуральное число nназываетсясоставным,еслиn>1иnимеет по крайней мере один натуральный делитель, отличный от1иp.

Число 1не является ни простым, ни составным.

Замечание.В школьном курсе математики при определении простого и составного числа обычно «забывают» упомянуть, что- натуральные и большие единицы. При этом не упоминают и о натуральности делителей, так как в школе все делители натуральные.

Теорема 7.1.(Об основных свойствах простых чисел).

1)Любое натуральное число n>1делится хотя бы на одно простое число.

2)Если простое число pделится на натуральное числоn, то либоn=1, либоn=p.

3)Если произведение целых чисел делится на простое число p, то хотя бы один из сомножителей делится наp.

4)Если натуральное число n>1является составным, то его наименьший простой делитель не превосходит числа.

5)Если натуральное число nне делится ни на одно простое числоp, тоn- простое.

Пример 3. Докажите, что число 127 простое.

Действительно, 127 – натуральное число, большее 1. Кроме того, 11<<12 и 127 не делится ни на одно простое числоp, гдеp=2,3,5,7; 11<p<12. Значит, по свойству 5 теоремы 7.1, число 127 – простое.

Теорема 8.1. (Основная теорема арифметики). Всякое натуральное числоn, большее единицы, либо просто, либо может быть представлено, причём единственным образом, в виде произведения простых чисел с точностью до порядка следования сомножителей.

Определение. Представление натурального числаn>1в видеn=, где- различные простые числа,-неотрицательное целое число, а- натуральные числа, называетсяканоническим разложением числа.

Следствие.Каждое натуральное числоn>1может быть представлено, причём единственным образом с точностью до порядка следования сомножителей, в каноническом виде.

Процесс представления числа n>1в канонической форме называетсяфакторизацией. Общий метод факторизации заданного числа заключается в том, что числоnпробуют делить последовательно на простые числа 2, 3, 5,…,до тех пор, пока не найдётся простое числоpтакое, чтоn⋮p. Если такоеpнайдётся, то дальнейшая факторизация числасводится к факторизации числаn₁=, меньшегоn. Если же среди всех указанных выше простых чисел нет ни одного делителя числаn, то, согласно свойству 5 теоремы 7.1, само числоnпростое,n=p₁ иn=p.

Пример 4. Представить в канонической форме (каноническом виде) натуральное число=5929.

Перебираем по порядку все простые числа 2, 3, 5 и т.д. и ищем среди них наименьший простой делитель числа 5929. По признакам делимости на 2, 3, 5 число 5929 на них не делится. А 5929=7∙847=7∙n₁. Числоn₁ не делится на 2, 3, 5, поэтому делим его вновь на 7: 847=7∙121=7∙n₂;n₂не делится на 2, 3, 5, 7. Поэтому делимn₂на следующее простое числоp=11: 121=11∙11. Таким образом,n=7∙n₁=7∙7∙n₂=7∙7∙11∙11=7²∙11².

Теорема 9.1.(О распределении простых чисел в натуральном ряду).

1) (Теорема Евклида). Множество всех простых чисел бесконечно.

2) В натуральном ряду есть сколь угодно длинные интервалы, не содержащие простых чисел.

Теорема 10.1.(Решето Эратосфена).

1) Если во множестве натуральных чисел 2, 3, 4, 5, … n, зачеркнуть все числа, кратные первымrпростым числам 2, 3, 5, …,p_r, то первое (наименьшее) не зачёркнутое число будет простым.

2) Если в этом множестве вычеркнуть все числа, кратные всем простым до (т.е. выбратьrтак, чтобыp_r≤n<p_r+1), то оставшиеся не вычеркнутыми числа совпадают со множеством всех простых чиселpтаких, чтоn≥p>.

Данная теорема даёт следующий алгоритм нахождения всех простых чисел в интервале от 2доn: во множестве2, 3, 4, 5, …, n- первое число2простое. Запоминаем2и вычёркиваем все числа, кратные2. Тогда первое не вычеркнутое число3–простое. Запоминаем3и вычёркиваем из оставшихся все числа, кратные3. Следующее первое не вычеркнутое число5–простое и т.д. Продолжаем этот процесс до простого числаp_rвключительно, гдеp_r≤<p_r+1. Все оставшиеся не вычеркнутыми числа образуют множество всех простых чисел, лежащих междуиn(включая иn, если оно простое, т.е. не вычеркнуто). А вместе с запомненными ранее простыми числами 2, 3, 5, …,p_rполучится множество всех простых чисел, не превосходящих числаn.

Теорема 11.1.(Применение канонической формы).

1. Если n=- каноническая форма натурального числаn, то все натуральные делители числаnимеют видc=, где,-целые числадля всехi=1, 2, …, k.

2) Если a,b-натуральные числа, причёмa=,b=, гдеp₁, p₂, …,p_k–различные простые числа, а≥0, ≥0-целые числа (согласованное представление натуральных чиселaиb), то (a,b)=, гдедля всех; [a,b]=, гдедля всех.

Замечание. Данные формулы обосновывают известные школьные способы нахождения НОД и НОК натуральных чисел.

6. Числовые функции.

Числовые функции– это функции, заданные на множестве всех натуральных чиселNи связанные с арифметической природой натуральных чисел.

Определение.

–количество всех натуральных делителей натурального числаn.

-сумма всех натуральных делителей числаn, взятых ровно по одному разу.

-количество всех натуральных чисел, не превосходящихnи взаимно простых с числомn.

Функция называетсяфункцией Эйлера.

Пример 5.Вычислить,,.

Так как 12⋮1, 2, 3, 4, 6, 12 – все натуральные делители числа 12. Поэтому ,=1+2+3+4+6+12=28. Натуральные числа 1, 5, 7, 11 и только они не превосходят 12 и взаимно просты с 12. Значит,=4.

Теорема 12.1.Пусть- каноническое разложение числа натурального числаn>1. Тогда

Определение. Целой частьюдействительного числаαназывается наибольшее целое числоkтакое, что.Дробной частью– разность междуαи целой частьюα.

Обозначения. – целая часть числаα;- дробная часть числаα. Итак, [α]– целое число и.

Пример 6.

Следствия. 1) Для любых натуральных чиселиколичество натуральных чисел, кратныхи не превосходящих, равно. 2) Показатель, с которым простое числовходит в каноническое разложение числа, равен.

Замечание.Количество ненулевых слагаемых в данной формуле конечно.