Основна теорема на аритметиката, формулировка, доказателство
Тази статия дава теоретична основа за разлагане на числа на прости множители -основната теорема на аритметиката. Тук даваме неговата формулировка и даваме доказателство на основната теорема на аритметиката.
Навигация в страницата.
Помощни теореми
Основната теорема на аритметикатапотвърждава възможността за разлагане на всяко цяло число, по-голямо от едно, на прости множители. Преди да го заявим и докажем, ще разгледаме две спомагателни теореми.
Всяко положително и неединично цяло число a или се дели на просто число p, или a и p са взаимно прости числа.
Най-големият общ делител на a и p дели p. Тъй като p е просто число по условието, само 1 и p са неговите положителни делители, следователно gcd(a, p) е равно или на 1, или на p. В първия случай gcd(a, p)=1 , откъдето следва, че числата a и p са взаимно прости. Във втория случай gcd(a, p)=p и тъй като a се дели на gcd(a, p) , тогава a се дели на p.
Ако произведението на няколко цели положителни неедни множители се дели на просто число p, тогава поне един множител се дели на p.
Всеки от множителите според предишната теорема е взаимно прост на p или се дели на p. Ако всички множители са взаимно прости с p, тогава произведението на тези множители ще бъде взаимнопросто с p, поради свойствата на взаимно простите числа. Следователно поне един от множителите се дели на p .
Основна теорема на аритметиката
Сега имаме необходимия арсенал от знания, който ни позволява да докажемосновната теорема на аритметиката.
Всяко цяло число, по-голямо от 1, може да се разложи на произведение на прости множители и товаразлагането е уникално, ако не се вземе предвид редът на факторите.
Нека a е цяло число, по-голямо от едно.
Нека първо докажем възможността за разлагане на числото a на прости множители.
Нека p1 е най-малкият положителен и различен от 1 делител на a . По силата на теоремата, доказана в раздела за таблицата на простите числа, числото p1 е просто. Тогава по дефиницията за делимост съществува цяло число a1 такова, че a=p1 · a1 . Ако a1 е по-голямо от едно, тогава има неговия най-малък прост делител p2 , откъдето a1=p2 a2 и a=p1 p2 a2 . Ако a2 е по-голямо от едно, тогава неговият най-малък прост делител p3 съществува, така че a2=p3 a3 , откъдето a=p1 p2 p3 a3 . И така продължаваме този процес, докато получим an=1, което е неизбежно, тъй като a, a1, a2, … е последователност от намаляващи положителни цели числа. Така че винаги можем да получим разлагане на числото a на прости множители под формата a=p1·p2·…·pn (за n=1 имаме a=p1 , това разлагане съответства на случая, когато числото a е просто).
Остава да се докаже уникалността на полученото разлагане.
Да приемем, че в допълнение към разлагането a=p1 p2 ... pn има друго разлагане на числото a на прости множители q1, q2, ..., qm във формата a=q1 q2 ... qm . Тогава трябва да е вярно равенството p1·p2·…·pn=q1·q2·…·qm. Нека покажем, че за n≠m това равенство е невъзможно, докато за n=m произведенията p1·p2·…·pn и q1·q2·…·qm са идентично равни.
Дясната страна на последното равенство се дели на q1 , тогава по силата на предходната теорема поне един от множителите p1, p2, …, pn трябва да се дели на q1 . Да предположим, че p1 се дели на q1, но тъй като числата p1 и q1 са прости, тогава p1 се дели на q1 само когато q1=p1 . Това ни позволява да намалим двете страни на равенството p1·p2·…·pn=q1·q2·…·qm с q1=p1 , получаваме p2·…·pn=q2·…·qm . Като спорим по подобен начин за p2 и q2, стигаме доравенство p3·…·pn=q3·…·qm . И така продължаваме, докато всички множители се редуцират във всяка част от равенството. За n≠m получаваме или равенството 1=qn+1·…·qm , или равенството pm+1·…·pn=1 , които са невъзможни за прости числа qn+1, …, qm и pm+1, …, pn . Ако n=m , тогава получаваме идентичността 1=1 , което показва идентичното равенство на разширенията a=p1·p2·…·pn и a=q1·q2·…·qm . Това доказва уникалността на разлагането на число на прости множители.
В заключение отбелязваме, че основната теорема на аритметиката често се нарича теорема за разлагането на числата на прости множители.