5. Прості і складені числа.

Цілі невід’ємні числа

1 2 3 і > безліч

Одиниця Прості Складені Нуль

числа числа

К₁ К₄

К₂ К₃

Наведена схема ілюструє класифікацію цілих невід’ємних чисел за кількістю дільників числа.

Означення простого і складеного числа .

Просте число р має два дільники:

Складене число має більше двох дільників.

Число нуль має безліч дільників.

Число 1 має 1 дільник:

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

Доведення методом від супротивного. Нехай – скінченна множина простих чисел, чисельність її дорівнює n . Утворимо число яке згідно припущення не просте, а складене, а тому ділиться на деяке просте число р, яке знаходиться серед чисел Нехай це р₁. Таким чином

за припущенням; – за подільністю добутку. А тому різниця за подільністю різниці. Але ця різниця дорівнює 1, а тому ,що неможливо. Отже, припущення про те, що множина простих чисел – скінченна, є хибне. Таким чином, множина простих чисел – нескінченна. Теорема доведена.

Цю теорему називають теоремою Евкліда, бо вона вперше зустрічається в ІХ книзі «Начал» («Початків») Евкліда, хоч ймовірно факт про нескінченність простих чисел був відомий і до нього.

Чим далі від початку натурального ряду, тим рідше зустрічаються прості числа, і між двома сусідніми простими числами може бути як завгодно багато складених. Наприклад,

- відрізок натурального ряду,який складається з (n-1) послідовних складених чисел. Ясно, що n можна вибрати як завгодно велике.

Відомі дуже великі числа – близнята, тобто такі, різниця між якими дорівнює 2. Наприклад, 109 999 49 і 109 999 51.

Перші таблиці простих чисел склав древньогрецький математик Ератосфен з допомогою розробленого ним методу, який називається решето Ератосфена (у ІІІ ст. до н.е.). Суть методу: слід виписати всі числа від 1 до n. Потім викреслювати послідовно числа, кратні 2, потім кратні 3 і т. д. Внаслідок чого залишаються невикреслені числа, які є простими.

Наприклад, в межах 30 є такі прості числа:

 , 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30.

Отже, прості числа на відрізку [1; 30] такі:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

6. Основна теорема арифметики натуральних чисел.

Теорема: складене число розкладається в добуток простих чисел з точністю до порядку їх слідування.

Доведення. Нехай а – складене, тоді

, якщо q₁ – просте, теорема доведена. Якщо q₁ – складене, то міркуючи аналогічно, дістанемо, що таке, що , а це означає, що , внаслідок чого . Далі знову, якщо q₂ – просте, теорема доведена. Якщо ж ні, то після скінченного числа n кроків остаточно дістанемо

. Теорема доведена.

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

.

Обидва добутки рівні, а оскільки числа p_i та q_i прості, то серед них знайдуться рівні. Нехай це буде число . Поділивши всі 3 частини рівності на , дістанемо:

Продовжуючи цей процес n разів, дістанемо в лівій частині число 1 і в правій число , а отже, і в середній частині буде число 1, що свідчить про те, що множників однакова кількість, тобто n=s. Отже, теорема доведена.