5. Прості і складені числа. Нескінчена множина всіх простих чисел. Основна теорема арифметики.

Розглянемо натуральні числа з точки зору кількості їх дільників. Очевидно утворюються 3 категорії

{1}- має 1 дільник

{2,3,5,7…}- мають 2 дільники

{4, 6, 8,…}- мають більше 2 дільників

Натуральне число називається простим, якщо воно має точно два дільники 1 і само себе. Якщо дільників більше число наз складеним. 1 – ні просте, ні складене.

Властивості п.ч

1. Якщо р-п.ч і р:а , а≠1, аєN, то а=р

Д-ня За означенням простого числа а може дорівнювати або 1, або р, оскільки за умовою а≠1, то а=р

2. якщо ab:p де a, bєN, p-просте число то або a:p, або b:p

Д-ня Справді, кожен із співмножників або взаємно простий з р, або ділиться на р. Але якби всі множники були взаємно прості з р то їх добуток був би взаємно простий з р, тому хоч один з множників ділиться на р.

3. Для довільного натурального а і простого числа р або а:р, або (а,р)=1

Д-ня. Справді, НСД (а,р) як дільник числа р може дорівнювати або р або1. У першому випадку а ділиться на р, у другому- а і р взаємно прості.

4. Найменший неодиничний дільник натурального числа є числом простим.

Д-ня. Нехай а – задумане число, якщо а – просте число, то його найменший дільник який ≠1, =а. Нехай а – складене число, і n₁- його найменший натуральний дільник ≠1. Тоді число можна представити а=n₁а₁, а₁єZ. Припустимо, що n₁- складене число, тоді існує n₂єN, n₂≠1 таке, що n₁::n₂, і n₁≠n₂ у такому випадку число n₂ буде також дільником числа а, меншим за n₁, що суперечить вибору числа n₁, отже n₁- п. ч.

5. Найменший простий дільник складеного числа не перевищує кореня квадратного з цього числа.

Д-ня. Нехай а-складне число, р-його найменший простий дільник. Тоді а=рb, bєZ, р≤ b. Тоді а=рb≥р², р≤

6. Якщо кожне просте число р≤не є дільником числа а, то а- просте число.

Теорема: Множина простих чисел нескінчена

Доведення: Нехай множина простих чисел скінчена і складається лише з чисел: . Розглянемо,m – складене, а раз так, то воно повинно мати простий дільник, але m не ділиться на жодне з рі, тобто m не може бути складеним, а значить є простим, що суперечить припущенню.

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

Д-ня:

1) n- просте то n=n і є шуканий розклад

2) будемо вважати, що n – складене, позначимо через р₁ його найменший не одиничний дільник, тоді n можна розкласти на множники

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

Доведемо єдність цього розкладу. Припустимо супротивне: існує ще один розклад , - прості числа., k=m тоді , а отже оскільки ліва частина рівності ділиться на р1, тому на р1 ділиться і права частина, а отже одне з qі=р1, нехай це буде q1. Скоротимо обидві частини рівності на р1, отримаємо, повторимо ці міркування для чисел р2, р3, …, рm. Якщо вважати, що m≠s, і наприклад, <s після скорочення одержимо . Оскільки q_і натуральні, то , тобто m≥s, аналогічно переконуємося в тому, що випадок s<m неможливий, тому m=s і р₁=q₁, р₂=q₂, … р_m=q_s ▲

Зберемо в степені однакові множники: ,канонічний запис цього числа.