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

Основна теорема арифметики стверджує, що кожне натуральне число, більше за 1, можна єдиним способом розкласти на добуток простих чисел. Наприклад, число 15 можна розкласти на добуток двох простих чисел 3 · 5, число 30 — на добуток трьох простих чисел 2 · 3 · 5, а число 16 — на добуток чотирьох простих чисел 2 · 2 · 2 · 2. Такий добуток називаємо розкладом на прості множники. Отже, розклад числа 10 на прості множники — це 2 · 5.

Найпростіший розклад на прості множники мають самі прості числа, бо їх уже не потрібно розкладати далі. Розклад числа 7 на прості множники — це просто 7.

Що стверджує основна теорема арифметики

Основну теорему арифметики іноді називають також фундаментальною теоремою арифметики. Вона стверджує дві речі:

• для кожного натурального числа, більшого за 1, ми можемо знайти розклад на прості множники,
• кожне число має рівно один розклад на прості множники.

Доведемо, що це справді так.

Доведення існування

Спочатку доведемо, що для кожного натурального числа, більшого за 1, справді існує принаймні один розклад на прості множники. Скористаємося методом математичної індукції. Першим кроком індукції буде те, що найменше натуральне число, більше за 1, тобто число 2, є простим.

Тепер покажемо, що коли для послідовності чисел 2, …, n розклад на прості множники знайти можна, то й після додавання до цієї послідовності числа n + 1 розклад існуватиме і для цього нового числа. Спочатку покажемо це на прикладі.

На початку наша послідовність 2, …, n трохи вироджена, бо містить лише одне число — двійку. Ми стверджуємо, що коли додати до неї число n + 1, тобто число 3, то для нього розклад на прості множники існуватиме. Оскільки 3 є простим числом, то розклад для нього, звісно, існує — це саме число 3.

Тепер наша послідовність 2, …, n має два члени: 2, 3. Додаємо до неї число 4. Число 4 не є простим, тому його можна розкласти на добуток двох інших натуральних чисел, більших за 1, але менших за 4. Усі такі числа вже є в нашій послідовності! А в цій послідовності є лише числа, які мають розклад на прості множники! Отже, і число 4 мусить мати розклад на прості множники: 2 · 2.

Повернімося до загального доведення. Число 2 є простим, тож має розклад на прості множники. Припустімо тепер, що кожне число з послідовності 2, …, n можна розкласти на прості множники — це наше індуктивне припущення. Тоді число n + 1 або просте, і тоді його тривіально можна розкласти на прості числа, або складене. Тоді для нього існують числа a, b такі, що

$$n+1=a\cdot b$$

При цьому ці натуральні числа, звісно, менші за n + 1 і більші за 1:

$$\begin{eqnarray} a > 1,&\quad&a < n+1 \\ b > 1,&\quad&b < n+1 \\ \end{eqnarray}$$

Отже, числа a, b належать до послідовності 2, …, n. Але для кожного числа цієї послідовності існує розклад на прості множники (це наше індуктивне припущення), тобто можемо записати

$$\begin{eqnarray} a&=&p_1\cdot p_2 \cdot \ldots \cdot p_i\\ b&=&q_1\cdot q_2 \cdot \ldots \cdot q_j\\ \end{eqnarray}$$

Усі p_i і q_j — прості числа, а p₁ · p₂ · … · p_i і q₁ · q₂ · … · q_j — їхні розклади на прості множники. Оскільки ми вже сказали, що n + 1 розкладається на добуток n + 1 = a · b, то водночас маємо

$$\begin{eqnarray} n+1&=&a\cdot b\\ &=&p_1\cdot p_2 \cdot \ldots \cdot p_i\cdot q_1\cdot q_2 \cdot \ldots \cdot q_j \end{eqnarray}$$

Число n + 1 розкладається на добуток простих чисел p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j, тобто й нове число n + 1 має розклад на прості множники. Звідси випливає, що кожне натуральне число, більше за 1, має принаймні один розклад на прості множники.

Доведення єдиності

Покажемо тепер, що для жодного натурального числа, більшого за 1, не існує кількох розкладів на прості множники. Цю теорему доведемо методом від супротивного. Припустімо, що теорема хибна, тобто що існує натуральне число n, більше за 1, яке має два різні розклади на прості множники:

$$\begin{eqnarray} n&=&p_1\cdot p_2 \cdot \ldots \cdot p_i\\ n&=&q_1\cdot q_2 \cdot \ldots \cdot q_j \end{eqnarray}$$

Припустімо також, що з усіх чисел, які мають кілька розкладів на прості множники, число n є найменшим. Тобто не існує меншого натурального числа, яке мало б більше ніж один розклад на прості множники. Оскільки q₁ — одне з простих чисел, що ділять число n, то, звісно, q₁ ділить і число p₁ · p₂ · … · p_i.

Далі нам потрібна лема Евкліда. Вона стверджує: якщо просте число p ділить добуток двох цілих чисел a · b, то p ділить принаймні одне з чисел a або b. Приклад: просте число 3 ділить число 84. Число 84 можна розкласти на добуток 12 · 7. Лема Евкліда стверджує, що просте число 3 ділить принаймні одне з чисел 12 або 7 — у цьому випадку воно ділить число 12.

Використавши цю лему, можемо сказати, що коли q₁ ділить p₁ · p₂ · … · p_i, то воно мусить ділити й принаймні одне з чисел p₁, p₂, …, p_i. Можемо припустити, без втрати загальності, що q₁ ділить число p₁. Але p₁ теж просте число. Коли просте число може ділити інше просте число? Наприклад, яке просте число ділиться на просте число 7? Знову лише саме число 7. Воно не може ділити інше просте число, бо тоді те число не було б простим. Отже, мусить бути p₁ = q₁.

Це означає, що в обох розкладах на прості множники є одне й те саме просте число: p₁, відповідно q₁. Поділімо обидві рівності на p₁, відповідно на q₁:

$$\begin{eqnarray} \frac{n}{p_1}&=&\frac{p_1\cdot p_2 \cdot \ldots \cdot p_i}{p_1}\\ \frac{n}{q_1}&=&\frac{q_1\cdot q_2 \cdot \ldots \cdot q_j}{q_1} \end{eqnarray}$$

Оскільки p₁ = q₁, у лівій частині отримаємо те саме число, позначмо його, скажімо, m. Отже,

$$m=\frac{n}{p_1}=\frac{n}{q_1}$$

У правій частині просто скоротимо дроби:

$$\begin{eqnarray} m&=&p_2 \cdot p_3 \cdot \ldots \cdot p_i\\ m&=&q_2 \cdot q_3 \cdot \ldots \cdot q_j \end{eqnarray}$$

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

Єдине пояснення — що не існує жодного «найменшого числа з більш ніж одним розкладом на прості множники». А те, що не існує «найменшого числа з більш ніж одним розкладом на прості множники», означає, що не існує жодного числа з кількома розкладами: кожне ціле число, більше за одиницю, має рівно один розклад на прості множники.