3. Основна теорема арифметики

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

Теорема 6. (Основна теорема арифметики). Кожне відмінне від 1 натуральне число р можна записати у вигляді добутку простих чисел і притому єдиним способом, якщо не брати до уваги порядок розміщення співмножників.

Доведемо спочатку можливість запису натурального числа q ? 1 у вигляді добутку простих чисел. Для натурального числа 2 це можливо, бо число 2 просте, тобто його можна вважати добутком простих чисел з числом співмножників, що дорівнює одиниці. Припустимо, що це можливо для всякого натурального числа k, такого, при якому 2 < k < п, і доведемо, що в такому разі і натуральне число п можна записати у вигляді добутку простих чисел. Справді, якщо натуральне число п просте, то воно є добутком простих чисел з числом співмножників, що дорівнює одиниці. Якщо ж число п складене, то воно має дільник k₁ відмінний від 1 і від п. Отже,

n = k₁• k₂,

де k₂ - натуральне число, відмінне від 1. Тоді 2 ? k₁ < n, 2 ? k₂ < n. Через те що за припущенням кожне з чисел k₂ і k₂ записується у вигляді добутку простих чисел, то й число n = k₁• k₂ записується у вигляді добутку простих чисел. Отже, внаслідок принципу математичної індукції будь-яке натуральне число п можна записати у вигляді добутку простих чисел.

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

Нехай число п двома способами записано у вигляді добутку простих чисел, тобто

п = p₁ p₂ ... р_r і

п = q₁ q₂ ... q_s,

де r ? 2, s ? 2 і всі числа р_i і q_k прості. Доведемо, що ці записи можуть відрізнятися лише порядком співмножників, тобто що r = s і при належному виборі нумерації співмножників р_i = q_і, і = 1, 2, ..., s. Доводитимемо це індукцією по п. Для числа 2 правильність цього твердження очевидна. Число 2 є добуток простих чисел з числом співмножників, що дорівнює одиниці. Нехай твердження правильне для всякого числа k, такого, що 2 ? k < п. Доведемо, що в такому разі твердження правильне і для числа п. Справді, оскільки п = p₁ p₂ ... р_r і п = q₁ q₂ ... q_s, то

p₁ p₂ ... р_r = q₁ q₂ ... q_s(2)

Ліва частина цієї рівності ділиться на просте число p₁. Отже, і права частина її ділиться на просте число p₁. Звідси за теоремою 2 принаймні один із співмножників q₁ q_z, ..., q_s ділиться на просте число р₁. Змінивши, якщо потрібно, нумерацію множників q₁ q_z, ..., q_s, ми вважатимемо, що на p₁ ділиться співмножник q₁. Оскільки q₁ є просте число і ділиться на відмінне від 1 просте число р₁, то q₁ = р₁.

Поділивши обидві частини рівності (2) на число р₁ = q₁ дістанемо рівність p₂ p₃ ... р_r = q₂ q₃ ... q_s

Число n₁ = p₂ p₃ ... р_r = q₂ q₃ ... q_s задовольняє умову 2 ? n₁ < п. Тому за припущенням для нього твердження правильне, тобто r - l=s-l, і при відповідній нумерації р₂ = q₂. pз = q₃, … , p_s = q_s Звідси випливає, що r = s і при відповідній нумерації p_i = q_i, і = 1, 2, ..., s.

Отже, внаслідок принципу математичної індукції, всяке відмінне від 1 натуральне число n єдиним способом записується у вигляді добутку простих чисел. Цим теорему доведено.

Зауважимо, що запис n = p₁ p₂ ... p_s натурального числа п у вигляді добутку простих чисел p₁ , p₂ ... p_s називають також розкладом числа п у добуток простих множників, або розкладом на прості множники.

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