Фундаменталната теорема на аритметиката (наричана още теорема за уникалната факторизация) е теорема от теорията на числата. Теоремата гласи, че всяко положително цяло число, по-голямо от 1, може да се запише като произведение на прости числа (или самото цяло число е просто число). Теоремата също така казва, че такова представяне е уникално — освен възможната промяна на реда на множителите, няма друг различен начин за представяне на числото като произведение на прости числа. Намирането на простите множители на дадено число се нарича факторизация.

Дефиниция и уточнения

Прости числа са цели числа по-големи от 1, които нямат дивизори различни от 1 и самото число. Числата, които имат такива допълнителни делители, се наричат съставни. Числото 1 не се смята за просто и не участва в съществената част на факторизацията (той е т.нар. единица в множеството на целите числа).

Формулировка: за всяко цяло n > 1 съществуват прости числа p1, p2, ..., pk и положителни цели степени a1, a2, ..., ak такива, че n = p1a1·p2a2·...·pkak, и това представяне е уникално, с точност до подредбата на множителите.

Примери

  • 6936 = 23·3·172.
  • 1200 = 24·3·52.
  • 13 е просто число, следователно неговата факторизация е просто 13.

Кратка скица на доказателство

Съществуване (индукция): ако n е просто, готово. Ако n е съставно, има нетривиален делител a с 1 < a < n и b = n/a също с 1 < b < n. По индукционна хипотеза и a, и b имат представяне като произведение на прости числа, затова и n = a·b има такова представяне.

Уникалност (с помощта на лемата на Евклид): важно твърдение е: ако p е просто число и p дели произведение ab, то p дели a или p дели b. Това следва от свойствата на най-големия общ делител (може да се докаже чрез равенството на Безоут: ако gcd(p,a)=1, тогава съществуват x,y с xp+ya=1 и оттук p | b). С помощта на тази лема се показва, че ако имаме две факторизации на едно число, от първото просто число в едната факторизация следва, че то трябва да се среща и в другата; повтаряйки процедурата по премахване на съвпадащите прости множители, стигаме до заключение, че двете факторизации съдържат едни и същи прости множители със същите степени (само в различен ред).

Приложения

Фундаменталната теорема е основен инструмент в цялата теория на числата и има множество приложения: от доказателства на свойства на делимостта и най-големите общи делители, до изчисления на функцията на Мьебиус и разпад на идеали в по-общи структури. Тя също така стои в основата на съвременната криптография, например в алгоритъма RSA, където сигурността се базира на практическата трудност при факторизация на много големи числа (особено продукт на две големи прости числа).

Обобщения и ограничения

Фундаменталната теорема важи за целите числа Z, но в по-общи комутативни пръстени не винаги е валидна. Пръстените, в които всяко ненулево ненулево ненитовско елемент има уникална факторизация в неприводими елементи (до асоцииране и ред), се наричат пръстени с уникална факторизация (UFD). Пример за пръстен, където уникалната факторизация се проваля, е Z[√-5]: там 6 може да се факторизира по два несравними начина 6 = 2·3 = (1+√-5)·(1-√-5), които не са свързани чрез асоциирани множители.

Бележки за практическа факторизация

  • Теоремата гарантира съществуване и уникалност, но не дава ефективен алгоритъм за намиране на простите множители на големи числа. За практическа факторизация се използват различни алгоритми (напр. пробно делене, факторизация на квадрати, Pollard's rho, квадратични и генерални числени решетки и др.).
  • Проверка дали едно число е просто има ефективни методи (напр. детерминираните тестове като AKS и вероятностни като Miller–Rabin).

Фундаменталната теорема на аритметиката е едно от най-важните и интуитивно разбираеми твърдения в теорията на числата: тя казва, че простите числа са „строителните блокове“ на всички положителни цели числа и че тези блокове са подредени по уникален начин.