Фундаменталната теорема на аритметиката — дефиниция и уникална факторизация
Фундаменталната теорема на аритметиката: ясна дефиниция, доказателство и приложения в криптографията. Как и защо всяко число има уникална факторизация — примери и методи.
Фундаменталната теорема на аритметиката (наричана още теорема за уникалната факторизация) е теорема от теорията на числата. Теоремата гласи, че всяко положително цяло число, по-голямо от 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).
Фундаменталната теорема на аритметиката е едно от най-важните и интуитивно разбираеми твърдения в теорията на числата: тя казва, че простите числа са „строителните блокове“ на всички положителни цели числа и че тези блокове са подредени по уникален начин.
Доказателство
Първият, който доказва теоремата, е Евклид. Първото подробно и правилно доказателство е в Disquisitiones Arithmeticae на Карл Фридрих Гаус.
Някои хора може да смятат, че теоремата е вярна навсякъде. Теоремата обаче не е вярна в по-общи бройни системи, като алгебричните цели числа. За първи път това е споменато от Ернст Кумер през 1843 г. в работата му върху последната теорема на Ферма. За повече информация относно това: прочетете Алгебрична теория на числата.
Доказателството се състои от две части: първо, показваме, че всяко число може да бъде записано като произведение на първични числа; второ, показваме, че ако запишем едно число като произведение на първични числа за втори път, то двата списъка на първичните числа трябва да са еднакви.
Първа част на доказателството
Показваме, че ако не всяко число, по-голямо от 1, може да се запише като произведение на първични числа, се стига до някаква невъзможност. Така че след това стигаме до заключението, че трябва да е вярно, че всяко число може да се запише като произведение на прости числа.
И така, вижте какво ще се случи, когато някой каже, че знае цяло положително число, по-голямо от 1, което не може да се запише като произведение на прости числа. В този случай ще го помолим да посочи всички числа, по-големи от 1, които не могат да бъдат записани като произведение на първични числа. Едно от тези числа трябва да е най-малкото: нека го наречем n. Разбира се, това число n не може да бъде 1. Освен това то не може да бъде просто число, защото простото число е "произведение" на едно единствено просто число: самото себе си. Така че то трябва да е произведение на числа. Следователно -
n = ab
където и a, и b са цели положителни числа, които, разбира се, са по-малки от n. Но: n е най-малкото число, което не може да се запише като произведение на прости числа. Така че трябва да е възможно a и b да се запишат като произведения на прости числа, защото и двете са по-малки от n. Но тогава произведението
n = ab
може да се запише и като произведение на първични числа. Това е невъзможно, защото казахме, че n не може да се запише като произведение на прости числа.
Сега показахме невъзможността, която съществува, ако първата част на теоремата не е вярна. По този начин вече доказахме първата част на теоремата.
Втора част на доказателството
Сега трябва да докажем, че има само един начин да запишем положително число, по-голямо от 1, като произведение на прости числа.
За тази цел използваме следната лема: ако едно просто число p дели едно произведение ab, то то дели a или b (лема на Евклид). Сега първо ще докажем тази лема. Добре, да предположим, че p не дели a. Тогава p и a са равнозначни и имаме тъждеството на Безут, което казва, че трябва да има цели числа x и y такива, че
px + ay = 1.
Умножавайки всичко с b, получаваме
pbx + aby = b,
Спомнете си, че ab може да се дели на p. Така че сега от лявата страна имаме два члена, които се делят на p. Така че членът от дясната страна също се дели на p. Вече доказахме, че ако p не дели a, то трябва да дели b. Това доказва лемата.
Сега ще докажем, че можем да запишем цяло число, по-голямо от 1, само по един начин като произведение на прости числа. Вземете две произведения на първичните числа А и В, които имат еднакъв резултат. Така че за резултата на произведенията знаем, че A = B. Вземете което и да е просто число p от първото произведение A. То дели A, така че дели и B. Като използваме няколко пъти лемата, която току-що доказахме, виждаме, че тогава p трябва да дели поне един фактор b на B. Но всички фактори сами по себе си са прости числа, така че и b е просто число. Но ние знаем, че p също е просто число, така че p трябва да е равно на b. Затова сега разделяме A на p и също така разделяме B на p. И получаваме резултат като A* = B*. Отново можем да вземем едно просто число p от първото произведение A* и да установим, че то е равно на някое число от произведението B*. Продължавайки по този начин, накрая виждаме, че простите множители на двете произведения трябва да са абсолютно еднакви. Това доказва, че можем да запишем цяло положително число като произведение на първични числа само по един уникален начин.
Свързани страници
- Фундаментална теорема на алгебрата
| Множества от цели числа, основани на делимост | ||
| Преглед |
|
|
| Форми за факторизация |
| |
| Ограничени суми на делители |
| |
| С много делители |
| |
| Свързана с аликвотна последователност |
| |
| Базово зависим |
| |
| Други комплекти |
| |
Въпроси и отговори
Въпрос: Коя е фундаменталната теорема на аритметиката?
О: Фундаменталната теорема на аритметиката е теорема от теорията на числата, която гласи, че всяко цяло положително число, по-голямо от 1, може да се запише като произведение от прости числа и има само един начин да се запише числото.
В: Как може да се използва тази теорема?
О: Тази теорема може да се използва в криптографията.
Въпрос: Какво се случва, ако двама души намерят два различни начина да запишат едно и също число?
О: Ако двама души намерят два различни начина за записване на едно и също число, тогава единственото нещо, което може да се различава, е редът, в който са записани първите числа.
В: Какво е факторизация?
О: Факторизацията е намиране на всички прости числа, които съставляват дадено число.
В: Пример за просто число ли е 6936?
О: Не, 6936 не е просто число; то може да се запише като 23 - 3 - 172.
Не, 6936 не е просто число; то може да се запише като 23 - 3 - 172.
обискирам