3. Канонічний розклад складеного числа

У цьому розкладі [3.1] числа на прості множники деякі з них не можуть повторюватись. Якщо p₁ ,p₂ ,…p_s – різні прості множники, а α₁, α₂,..., α_і – їхня кратність, то вираз a= [3.2] називається канонічним розкладом числа а. Процес подання цілих чисел у вигляді канонічного розкладу називається факторизацією.

Розкладання натурального числа а на прості множники є громістким процесом, бо зводиться до випробування всіх простих дільників числа а, які не перевищують .

Приклад. Розкласти на прості множники 997. 31< <32. отже. Треба випробувати всі прості числа . Оскільки кожне з них не є дільником числа 997. то число 997 – просте.

Із канонічного розкладу числа випливають такі твердження:

1. Якщо a= - канонічний розклад числа, то всі дільники цього числа мають вигляд: [3.3], де , ( I=1, 2,…, s).

Доведення. Дійсно, всяке число [3.2] ділиться на [3.3]. Це очевидно із даних розкладів. Навпаки, нехай , тоді , де і ціле. Отже, всі прості дільники числа входять до канонічного розкладу числа а з показниками, не більшими за , тобто . Тому всі дільники числа а матимуть вигляд [3.3].

Нехай дано два натуральних числа a і b. Їхні канонічні розклади: a= , b= . Причому і можуть бути і нулем.

2. Найбільший спільний дільник чисел a і b матиме вигляд:

( a, b)= , де .

3. Найменше спільне кратне чисел a і b матиме вигляд: [ a, b]= , де .

Ці твердження є очевидними. З них безпосередньо випливає тотожність:

ab=( a, b)[a, b].

4. Нескінченність множини простих чисел. Решето Ератосфена

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

Доведення. Допустимо протилежне, тобто, що кількість простих чисел скінчена і дорівнює n. Позначимо їх p₁ ,p₂ ,…p_n. Візьмемо їх добуток P= p₁ p₂ …p_n. Тоді число Q=P+1 або само просте (більше від будь-якого p_і), або має ділитись на деяке просте число, відмінне від p₁ ,p₂ ,…p_n ( бо число 1 не має дільників, відмінних від самого себе. Тобто 1 не ділиться на жодне з p_і). Отже. Існує принаймні одне просте число, відмінне від p₁ ,p₂ ,…p_n. А це суперечить припущенню. Теорему доведено.

Для складання таблиці простих чисел, які не перевищують даного натурального числа N. Є простий спосіб, який називаються решетом Ератосфена.

Виписуємо підряд одне за одним числа натурального ряду: 1, 2, 3,…, N. Перше, більше від 1, число цього ряду є 2. воно просте. Його залишаємо. А всі числа, кратні 2, викреслюємо. Друге число, більше від 2, є 3. воно просте, його залишаємо, а всі числа, кратні 3 викреслюємо. І так далі. Коли в натуральному ряді вже викреслено всі числа, кратні простим, меншим від простого р, то всі числа, менші за , будуть прості. Дійсно, всяке складене а, менше за , ми вже викреслили, як кратне його найменшому простому дільнику, який не перевищує і менший за р.

Отже: 1) викреслювання кратних простому числу р треба починати з .

2) складання таблиці простих чисел, що не перевищують N, закінчено тоді, якщо викреслено всі складені числа, кратні простим числам, які не перевищують .

Даний метод є громіздким для великих N, але він є по суті єдиним загальним методом послідовного виділення простих чисел у натуральному ряді.

Теорема Діріхле . арифметична прогресія, у якої перший член і різниця взаємно прості, містить нескінченне число простих чисел.

Умова (a₁, d) є суттєвою, бо якщо (a₁, d) , то всі члени послідовності діляться на і прогресія тоді містить ( найбільше) одне просте число.

Деякі частинні випадки теореми Діріхле про нескінченність множини простих чисел в арифметичній прогресії: множини простих чисел виду 4t+1, 4t+3, 6t+1, 6t+5 нескінченні.