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

Основну теорему арифметики довів Гаусс у своїй книзі 1801 року Арифметичні дослідження (лат. Disquisitiones Arithmeticae). В цій книзі, Гаусс використав основну теорему для доведення квадратичного закону взаємності.

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

Кожне натуральне число $n>1$ можна подати у вигляді $n=p_{1}\cdot \ldots \cdot p_{k}$, де $p_{1},\ldots ,p_{k}$ — прості числа, причому таке подання єдине, якщо не враховувати порядок множників.

Якщо формально домовитися, що добуток порожньої множини чисел дорівнює 1, то умову $n>1$ у формулюванні можна опустити, тоді для одиниці мається на увазі розклад на порожню множину простих: $1=1$.

Як наслідок, кожне натуральне число $n$ єдиним чином подається у вигляді

$n=p_{1}^{d_{1}}\cdot p_{2}^{d_{2}}\cdot \ldots \cdot p_{k}^{d_{k}},$ де $p_{1}<p_{2}<\ldots <p_{k}$ — прості числа, і $d_{1},\ldots ,d_{k}$ — деякі натуральні числа.

Таке подання числа $n$ називається канонічним розкладом на прості співмножники.

Наприклад,

1200 = 2⁴ × 3¹ × 5² = 5 × 2 × 5 × 2 × 3 × 2 × 2 = …

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

Ця теорема є однією із основних причин, чому число 1 не відносять до простих чисел: якби число 1 було простим, тоді розкладання на прості множники не було б унікальним; наприклад, 2 = 2 × 1 = 2 × 1 × 1 = ...

Пояснення

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

$420=2\cdot 2\cdot 3\cdot 5\cdot 7=2^{2}\cdot 3\cdot 5\cdot 7,$

$1200=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5\cdot 5=2^{4}\cdot 3\cdot 5^{2}.$

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

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

У деяких випадках твердження основної теореми арифметики застосовуються для всіх цілих чисел крім нуля. При цьому прийнято вважати, що одиниця є добутком нульової кількості простих чисел (порожній добуток), а унікальність розкладу доводиться з точністю до порядку множників та їхніх знаків.

Історія

Передумови основної теореми арифметики беруть свої витоки в Стародавній Греції. Незважаючи на те, що в давньогрецькій математиці основна теорема арифметики в сучасному формулюванні не зустрічається, в «Началах» (дав.-гр. Στοιχεῖα) Евкліда є еквівалентні їй речення. Слідуючи за Евклідом, багато математиків протягом століть вносили свій внесок у доведення основної теореми арифметики, наводячи в своїх працях близькі за змістом твердження, серед цих вчених Камаль аль-Дін аль-Фарісі, Ж. Престет, Л. Ейлер, А. Лежандр. Перше точне формулювання основної теореми арифметики і її доведення наводяться К. Гауссом у книзі «Арифметичні дослідження» (лат. Disquisitiones Arithmeticae), виданій у 1801 році. З цих пір з'явилося багато різних нових доведень теореми, що конкурують між собою за красою й оригінальністю.

Евклід (III ст. до н. е.)

Евклід заклав в «Началах» важливі основи для теорії чисел і, зокрема, основну теорему арифметики. Три речення, дуже близькі за змістом до основної теореми арифметики, можна знайти в книгах VII і IX, а саме: речення 30 з книги VII, найбільш відоме як лема Евкліда, речення 31 з книги VII і речення 14 з книги IX. Нижче вони наведені в перекладі Мордухай-Болтовського.VII.30:

Якщо два числа, множачи одне на одне, утворюють щось, а те, що виникло з них вимірюється якимось першим числом, то (останнє) виміряє й одне з початкових

VII.31:

Будь-яке складене число вимірюється якимось першим числом

IX.14:

Якщо число буде найменшим вимірюваним (даними) першими числами, то воно не виміриться ніяким іншим простим числом, крім того, що спочатку вимірило (його)

В наш час з речень VII.30 і VII.31 виводять доведення основної теореми арифметики, однак Евклід його у своїх працях не виклав. Речення IX.14 в свою чергу має багато схожого з єдиністю розкладу на прості множники, однак було відмічено, що це твердження охоплює не всі можливі випадки, наприклад, наявність хоча б одного квадрата простого числа в розкладі на прості множники.

Аль-Фарісі (XIV століття)

Відомий перський математик і фізик Камаль аль-Дін аль-Фарісі зробив значний крок вперед у вивченні основної теореми арифметики. В його праці «Меморандум для друзів про доведення дружності» (англ. Memorandum for friends on the proof of amicability) доведено існування розкладу на прості множники та надано необхідну інформацію для доведення єдиності даного розкладу. У зв'язку з тим, що найбільший інтерес для аль-Фарісі являла побудова власного доведення теореми Сабіта ібн Курри з пошуку дружніх чисел, аль-Фарісі не прагнув довести основну теорему арифметики, а займався пошуком всіх дільників складеного числа. Скрупульозно досліджуючи розкладання чисел на множники, він сформулював і довів твердження, яке є нічим іншим, як доведенням існування розкладання натурального числа на прості множники. У перекладі його твердження звучить приблизно так:

Кожне складене число може бути розкладене на скінченне число простих множників, добутком яких воно є.

У твердженні 9 аль-Фарісі сформулював принцип для визначення всіх дільників складеного числа, саме він і був необхідний математику для доведення теореми Ібн Курри; в перекладі речення звучить так:

Якщо складене число $a$ розкладено на прості множники як $a=b\cdot c\cdot d\cdot h\cdot \ldots \cdot k\cdot l$, тоді $a$ не має дільника крім $1$ і $b,c,d,...,k,l$ і добутків кожного з них з кожним, добутків трійок і т. д. аж до добутку всіх елементів без якого-небудь одного.

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

Жан Престет (XVII століття)

Результати, опубліковані Жаном Престетом[en] у книзі «Нові елементи математики» (фр. Elements de Mathématiques, 1675) підтверджують, що розкладання на прості множники розглядалася в ті часи не як щось саме по собі цікаве, а як корисний додаток — засіб для знаходження дільників заданого числа. Престет не сформулював ні існування, ні єдиності основної теореми арифметики і приділяв найбільшу увагу пошуку дільників числа. Незважаючи на це, подібно аль-Фарісі, Престет надав всю необхідну інформацію для доведення єдиності розкладу на прості множники за допомогою свого Наслідку IX, який саме по собі можна вважати еквівалентним єдиності розкладу на прості множники. Наслідок IX:

Якщо числа $a$ і $b$ прості, кожен дільник $a\cdot a\cdot b$ — це або $a$, або $a^{2}$, або $1$, або один з добутків цих трьох чисел на $b$. Тобто один з шести: $1,a,a\cdot a,1\cdot b,a\cdot b,a\cdot a\cdot b$.

Ейлер і Лежандр (XVIII століття)

У книзі «Повний посібник з алгебри» (нім. Vollstandige Einleitung zur Algebra) Леонард Ейлер опублікував результати, схожі з працями своїх попередників. Він сформулював існування розкладу числа на прості множники і надав часткове доведення цього, опускаючи деякі подробиці, у пункті 41 глави IV із першої частини першого розділу книги. У перекладі його речення звучить так:

Всі складені числа, які можуть бути розкладені на множники, подані добутком простих чисел; тобто всі їхні множники — прості числа. Бо, якщо знайти множник, який не є простим числом, він завжди може бути розкладений і поданий двома або більше простими числами.

Ейлер не формулював теорему про єдиність розкладу, але запропонував схоже твердження без доведення у пункті 65 глави IV з першого розділу першої частини. Там Ейлер неявно пояснює, що розклад числа на прості множники єдиний, говорячи, що всі дільники числа можна знайти, знаючи прості множники з розкладу даного числа [17]. Таким чином, цей пункт може вважатися еквівалентним єдиності розкладу на прості множники. У перекладі це твердження звучить так:

Коли ми розклали число на прості множники, стає дуже легко знайти всі його дільники. Бо ми, по-перше, повинні перемножувати прості множники один на одного, а потім множити їх попарно, три на три, чотири на чотири і т. д., доки ми не прийдемо до самого числа.

«Вступ до теорії чисел» (фр. Essai sur la Théorie des Nombres) Лежандра містить доведення існування розкладу на прості множники і своєрідне припущення про одиничність даного розкладу за допомогою перерахування всіх простих дільників заданого числа. Твердження Лежандра про існування розкладу звучить так:

Будь-яке складене число $N$ може бути подане як добуток деяких простих чисел $a,b,...c$, кожне з яких піднесене до певного степеня, таким чином, завжди існує розклад $N=a^{k}\cdot b^{l}\cdot \ldots \cdot c^{m}$.

Твердження, пов'язане з унікальністю розкладу на прості множники, наведене в параграфі 10 «Вступу до теорії чисел», де Лежандр мав намір знайти число всіх дільників числа і разом з тим їх суму. З цього твердження легко довести єдиність.

Карл Гаусс (XIX століття)

Перше точне формулювання теореми і її доведення наводяться в книзі Гаусса «Арифметичні дослідження» (1801). Формулювання теореми можна знайти в параграфі 16, у перекладі вона звучить так:

Складене число може бути розкладене на прості множники єдиним чином.

Доведення теореми

Теорема була практично доведена Евклідом, але єдиність розкладу не була сформульована, й, напевно, приймалась як очевидний факт. Перший повний доказ теореми був даний Карлом Гауссом, який звернув увагу на необхідність доказу неможливості співіснування різних розкладів одного числа на прості множники.

Доведення існування розкладу

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

n = ab

де обидва a та b є натуральними числами меншими за n. Далі, тому що n є найменшим з чисел, яке не можна розкласти на прості множники, доходимо висновку, що множники a та b мають розкладатись в добутки простих чисел. Але, n = ab і в такому разі само повинно бути добутком винятково простих чисел. Отримуємо суперечність.

Доведення єдиності розкладу

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

$n=p_{1}\cdot p_{2}\dots \cdot p_{r}=q_{1}\cdot q_{2}\dots \cdot q_{s}.$

Оскільки $p_{1}$ є дільником лівої частини рівності, то він також повинен бути і дільником одного з множників $q_{k}$ в правій частині. Але $q_{k}$ є простим числом, а отже повинна бути справедливою тотожність $p_{1}=q_{k}$. Скоротивши рівність на спільний множник $p_{1}=q_{k}$, проведемо аналогічне зіставлення для множника $p_{2}$, який теж буде дорівнювати одному з $q_{k}$, що залишились після спрощення. В результаті, після скорочення всіх множників $p_{i}$ в лівій стороні рівності отримуємо 1. З іншого боку, через те що всі $q_{k}$ також є простими числами, праворуч також отримаємо одиницю. Отже, числа $p_{i}$ та $q_{k}$ попарно рівні, що доводить тотожність двох розкладів.

Доведення з використанням алгоритму Евкліда

Можна довести основну теорему арифметики за допомогою наслідку з алгоритму Евкліда:

Найбільшим спільним дільником $n\cdot a$ і $n\cdot b$ є найбільший спільний дільник $a$ і $b$, помножений на $n$.

З даного наслідку можна довести лему Евкліда, також необхідну для доведення теореми:

Якщо $p$ — просте число і добуток двох чисел ділиться на $p$, то хоча б один з двох множників ділиться на $p$.

Існування: Ідея для доведення існування полягає в доведенні леми:

Розглянемо просте число $p$ і добуток $n\cdot a$. Нехай $n\cdot a$ ділиться на $p$, але $a$ не ділиться на $p$, тоді $n$ ділиться на $p$.

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

Єдиність: Нехай число n має два різних розклади на прості числа:

$n=p_{1}\cdot p_{2}\cdot p_{3}\cdot \ldots =p'_{1}\cdot p'_{2}\cdot p'_{3}\cdot \ldots$

Оскільки $p'_{1}\cdot p'_{2}\cdot p'_{3}\cdot \ldots$ ділиться на $p_{1}$, то або $p'_{1}$, або $p'_{2}\cdot p'_{3}\cdot \ldots$ ділиться на $p_{1}$. Якщо $p'_{1}$ ділиться на $p_{1}$, то $p'_{1}=p_{1}$, оскільки обидва ці числа є простими. Якщо ж $p'_{2}\cdot p'_{3}\cdot \ldots$ ділиться на $p_{1}$, то продовжимо попередні міркування. Врешті-решт дійдемо до результату, що яке-небудь із чисел $p'_{1},p'_{2},p'_{3},\ldots$ дорівнює числу $p_{1}$. Отже, врешті прийдемо до висновку, що обидва розклади числа збігаються. Таким чином доведено єдиність розкладу.

Застосування

З основної теореми арифметики можна зробити висновок про важливість в арифметиці простих чисел, на основі яких можна побудувати будь-яке ціле число.

Знаючи розклад числа на прості множники, можна отримати загальну кількість його дільників. Будь-який додатний дільник числа буде поданий тим самим набором простих чисел, але з меншими показниками степеня у відповідних множників. Так, наприклад, всі дотатні дільники числа 1200 будуть мати таку форму $2^{a}\cdot 3^{b}\cdot 5^{c}\!$ де $a\in \{0,1,2,3,4\}$, $b\in \{0,1\}$ та $c\in \{0,1,2\}$. Загальна кількість таких дільників буде дорівнювати $5\cdot 2\cdot 3=30$.

Узагальнення основної теореми арифметики на область цілих чисел дає можливість її подання в алгебричних термінах, а саме: будь-який елемент, відмінний від нульового та одиничних, можна єдиним способом розкласти на прості множники з точністю до порядку множників та їхнього множення на одиничні елементи. В такому вигляді основну теорему можна застосовувати також для інших алгебричних множин, наприклад для аналізу кілець многочленів з раціональними коефіцієнтами або гаусових чисел. Але, як показав Ернст Куммер в 1843 році, для загальніших множин єдиність розкладу на прості множники не зберігається.

• Основна теорема арифметики дає елегантні вирази для найбільшого спільного дільника і найменшого спільного кратного.

Позначимо через ${p_{i}}$ всі різні прості числа з розкладів чисел $a$ і $b$ на прості множники, a степені, з якими вони зустрічаються в цих розкладах, як ${d_{i}}$ і ${d'_{i}}$ відповідно. Варто зауважити, що ${d_{i}},{d'_{i}}$ можуть набувати тільки натуральних або нульових значень.

Тоді:

Н. С. Д.$(a,b)=p_{1}^{\min\{\,d_{1},d_{1}'\,\}}\cdot p_{2}^{\min\{\,d_{2},d_{2}'\,\}}\cdot p_{3}^{\min\{\,d_{3},d_{3}'\,\}}\cdot p_{4}^{\min\{\,d_{4},d_{4}'\,\}}\cdot \ldots =\prod p_{i}^{\min\{\,d_{i},d_{i}'\,\}},$

Н. С. К.$(a,b)=p_{1}^{\max\{\,d_{1},d_{1}'\,\}}\cdot p_{2}^{\max\{\,d_{2},d_{2}'\,\}}\cdot p_{3}^{\max\{\,d_{3},d_{3}'\,\}}\cdot p_{4}^{\max\{\,d_{4},d_{4}'\,\}}\cdot \ldots =\prod p_{i}^{\max\{\,d_{i},d_{i}'\,\}}$

• Знаючи розклад натурального числа на множники, можна відразу вказати всі його дільники.

Використаємо канонічний розклад числа, наведений на початку статті. Натуральні числа $d_{1},\cdots ,d_{k}$ — це не що інше, як кількість відповідних простих чисел $p_{1},...,p_{k}$, що зустрічаються в розкладі початкового числа. Таким чином, для пошуку всіх дільників достатньо записати добутки зі всіма можливими комбінаціями простих чисел, варіюючи кількість кожного $p_{i}$ у добутку від $0$ до $d_{i}$

Приклад: $N=1164=2\cdot 2\cdot 3\cdot 97=2^{2}\cdot 3^{1}\cdot 97^{1}$

Оскільки число 2 зустрічається в розкладі 2 рази, $d_{1}$ може набувати цілих значень від 0 до 2. Аналогічно $d_{2}$ і $d_{3}$ набувають значень від 0 до 1. Таким чином, множина всіх дільників складається з чисел $1,2,3,97,2\cdot 2,2\cdot 3,2\cdot 97,3\cdot 97,2\cdot 2\cdot 3,2\cdot 2\cdot 97,2\cdot 3\cdot 97,2\cdot 2\cdot 3\cdot 97$.

Для підрахунку загальної кількості дільників потрібно перемножити кількість всіх можливих значень у різних $d_{k}$.

У нашому випадку загальна кількість дільників дорівнює $2\cdot 2\cdot 3=12$

• Підрахунок багатьох арифметичних функцій ведеться на основі канонічного розкладу на прості множники.

Наприклад, для функції Ейлера від натурального числа справедлива формула: $\varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),\;\;n>1,$ де $p$ — просте число і пробігає всі значення, які беруть участь в розкладанні $n$ на прості співмножники.

• Обчислення добутку двох чисел можна провести таким чином:

$a\cdot b=p_{1}^{d_{1}+d_{1}'}\,p_{2}^{d_{2}+d_{2}'}\,p_{3}^{d_{3}+d_{3}'}\,p_{4}^{d_{4}+d_{4}'}\ldots =\prod p_{i}^{d_{i}+d_{i}'}.$

Приклад: $68\cdot 36=(2\cdot 2\cdot 17)\cdot (2\cdot 2\cdot 3\cdot 3\cdot )=2^{4}\cdot 3^{2}\cdot 17$

Основна теорема арифметики в кільцях

Розглянемо основну теорему арифметики в більш загальному випадку: в кільцях з нормою і в евклідових кільцях.

Основна теорема арифметики в кільці цілих гаусових чисел

Основна теорема арифметики має місце в кільці цілих гаусових чисел. Ідея доведення полягає в знаходженні алгоритму ділення з остачею в цьому кільці чисел. Кільце, в якому є алгоритм ділення з остачею, називається евклідовим. Для будь-якого евклідового кільця доведення основної теореми арифметики можна провести так само, як для натуральних чисел.

Неєдиність розкладу в кільці

Проте дія цієї теореми не поширюється на всі кільця.

Розглянемо, наприклад, комплексні числа виду $a=m+in{\sqrt {5}}$, де $m$,$n$ — цілі числа. Сума і добуток таких чисел будуть числами того ж виду. Тоді отримаємо кільце з нормою $N(a)=m^{2}+5n^{2}=|a|^{2}$.

Для числа 6 в цьому кільці існують два різних розклади: $6=2\cdot 3=(1-i{\sqrt {5}})(1+i{\sqrt {5}})$. Залишається довести, що числа $2,3,1\pm i{\sqrt {5}}$ є простими. Доведемо, що число 2 — просте. Нехай $2=(m_{1}+in_{1}{\sqrt {5}})(m_{2}+in_{2}{\sqrt {5}})$. Тоді $4=(m_{1}^{2}+5n_{1}^{2})(m_{2}^{2}+5n_{2}^{2})$. Отже, $m_{1}^{2}+5n_{1}^{2}=m_{2}^{2}+5n_{2}^{2}=2$.

Але в нашому кільці немає чисел з нормою 2, отже, такий розклад неможливий, тому число 2 — просте. Аналогічно розглядаються числа $3,1\pm i{\sqrt {5}}$.

Кільця, в яких основна теорема арифметики все ж виконується, називаються факторіальними.

Див. також

• Основна теорема алгебри
• Основна теорема аналізу

Література

• Виноградов И. М. Основы теории чисел. — Государственное издательство технико-теоретической литературы, 1952. — 180 с. — 10 000 екз.

• Жиков В.В. Основная теорема арифметики // Соросовский Образовательный Журнал. — 2000. — Т. 6, № 3. — С. 112–117.
• Калужнин Л. А. Основная теорема арифметики. — Популярные лекции по математике. — М. : Наука, 1969. — 32 с.
• Курант Р., Роббинс Г. Дополнение к главе I, § 4.2 // Что такое математика? — МЦНМО, 2000. — 568 с.

• A. Göksel Ağargün and E. Mehmet Özkan. A Historical Survey of the Fundamental Theorem of Arithmetic // Historia Mathematica. — 2001. — Т. 28. — С. 207–214. — DOI:10.1006/hmat.2001.2318.
• Д.Д. Мордухай-Болтовской, И.Н. Веселовский. Начала Евклида. Книги VII-X. — Государственное издательство технико-теоретической литературы, 1949. — 510 с.
• M.D. Hendy. Euclid and the fundamental theorem of arithmetic. — Historia Mathematica 05/1975, 1975.
• A.A. Mullin. Mathematico-philosophical remarks on new theorems anaiogous to the fundamental theorem of arithmetic. — Notre Dame Journal of Formal Logic, 1965.