5. Основну теорему арифметики називають також теоремою про існування та єдиність розкладу будь-якого натурального числа на добуток простих множників. Ця теорема використовувалась ще у стародавній Греції, але була сформульована і доведена видатним німецьким математиком К.Гауссом у 1801 році.
Теорема: будь-яке, більше за одиницю, натуральне число а, або просте, або може бути однозначно розкладене в добуток простих чисел з точністю до порядку розміщення співмножників.
Доведення: доведення складається з двох частин. У першій частині доведемо існування такого розкладу. Якщо аєN і a>1, то можливі два випадки : а) число а – просте, тоді розклад існує; б) число а – складене, тоді воно має найменший простий дільник. Нехай це буде число р1. Виходячи із цього, маємо а р1 і а=р1b, де bєN, причому число 1<р1< b.
Число b може бути або простим, або складеним. Якщо число b – просте, то ми вже можемо представити число а у вигляді добутку двох простих чисел рb, тобто розклад існує. Якщо b – складене число, то воно має простий дільник. Нехай це буде число р2. Виходячи із цього, маємо а р2 і а=р1р2с, де сєN, причому число 1<р2<с. Отже, а=р1·р2·с. Знову число с може бути або простим, або складеним. Якщо число с – просте, то число а буде представлятися у вигляді добутку трьох простих чисел. Якщо число c – складене, то ми одержимо ще один простий дільник р3. Оскільки с< b<а, то цей процес завжди буде закінчуватися, а тому завжди буде існувати розклад числа а у вигляді добутку простих множників (І).
Не виключеним є випадок, коли деякий із множників в розкладі (1) повторюється, а тому в загальному випадку розклад числа на прості множники записують так: (ІІ). Розклад (ІІ) називається канонічним розкладом натурального числа а у добуток простих множників. В цьому розкладі р1, р2, р3,...,рk – прості множники, розміщені в порядку зростання; a1, a2, a3,...,ak– це натуральні числа, які показують, скільки разів повторюється той чи інший множник. Існування доведено.
У другій частині доведемо єдиність такого розкладу методом від супротивного, припустивши, що існує два різних розклади у вигляді (І), тобто а=р1·р2·р3·…·рк (ІІ) і а=q1·q2·q3·…·qn (III). Врахуємо, що р1<р2<р3<…<рк і q1<q2<q3<…<qn. У даних розкладах рі і qі – різні, але серед них будуть однакові. Для визначеності припустимо, що p1¹q1 i p1<q1.
Утворимо нове число b=p1·q2·q3·…·qn (IV). Легко бачити, що число а в записі (1) ділиться націло на p1. Оскільки , то . Використовуючи записи (III) і (IV), винесемо добуток q2·q3·…·qn за дужки: (a-b)=(q1–p1)·q2·q3·...·qn. Ми показали, що вираз . Оскільки р1 - просте число, то вираз ((q1-p1) q2· q3· qn) p1. Числа q2, q3,…qn - прості і жодне із них не може ділитися на р1. Тоді на p1 повинна ділитися різниця (q1–p1) р1. Разом з тим, оскільки р1 р1, то , бо p1¹q1 і ці числа прості. Отже, для того, щоб (q1–p1) р1 потрібно, щоб q1-p1=0, тоді q1=p1. Ми прийшли до суперечності із вибором p1 і q1. Ця суперечність говорить, що наше припущення про неєдиність розкладу було хибним. Отже, якщо розклад існує, то він єдиний. Теорема доведена повністю.
Доведена теорема є теоретичною основою представлення будь-якого натурального числа у вигляді добутку простих множників. Покажемо це на прикладі такої вправи: „Представити число 1224 у канонічному розкладі, тобто розкласти в добуток простих множників”.