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

Основната теорема на аритметиката ни казва, че всяко естествено число, по-голямо от 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 е малко особена, защото съдържа само едно число – числото 2. Твърдим, че когато към тази редица добавим числото 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{array}{rcl}a>1,& & a<n+1\\ b>1,& & b<n+1\end{array}$$

Числата a, b следователно са част от редицата 2, …, n. За всяко число от тази редица обаче съществува разлагане на прости множители (това е нашето индукционно предположение), т.е. можем да запишем

$$\begin{array}{rcl}a& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ b& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

където всички p_i и q_j са прости числа, а p₁ · p₂ · … · p_i и q₁ · q₂ · … · q_j са съответно техните разлагания на прости множители. Тъй като казахме, че n + 1 се разлага на произведението n + 1 = a · b, е изпълнено и

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

Числото n + 1 следователно се разлага на произведението от прости числа p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j, т.е. и новодобавеното число n + 1 има разлагане на прости множители. Оттук следва, че всяко естествено число, по-голямо от 1, има поне едно разлагане на прости множители.

Доказателство на единствеността

Нека покажем сега, че за всяко естествено число, по-голямо от 1, не съществува повече от едно разлагане на прости множители. Тази теорема ще докажем с доказателство от противното. Ще допуснем, че теоремата не е вярна, т.е. че съществува естествено число n, по-голямо от 1, което има две различни разлагания на прости множители:

$$\begin{array}{rcl}n& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ n& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

Допускаме още, че от всички числа, които имат повече разлагания на прости множители, 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{array}{rcl}\frac{n}{p_1}& =& \frac{p_1\cdot p_2\cdot \dots \cdot p_i}{p_1}\\ \frac{n}{q_1}& =& \frac{q_1\cdot q_2\cdot \dots \cdot q_j}{q_1}\end{array}$$

Тъй като p₁ = q₁, отляво получаваме едно и също число, нека го означим например с m. Следователно

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

Отдясно просто съкращаваме дробите:

$$\begin{array}{rcl}m& =& p_2\cdot p_3\cdot \dots \cdot p_i\\ m& =& q_2\cdot q_3\cdot \dots \cdot q_j\end{array}$$

Числото m със сигурност е естествено число, което е по-малко от числото n, защото m е получено, като сме разделили n на един от простите му множители. Отдясно и в двете равенства обаче имаме разлагане на числото m на прости множители. Т.е. успяхме да построим друго число m, което е по-малко от числото n и което също има две различни разлагания на прости множители. Това обаче противоречи на допускането ни, че n е най-малкото число, което има повече от едно разлагане на прости множители.

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