A számelmélet alaptétele

A számelmélet alaptétele azt mondja ki, hogy minden 1-nél nagyobb természetes szám egyértelműen felbontható prímszámok szorzatára. Például a 15 felbontható két prímszám szorzatára: 3 · 5, a 30 három prímszám szorzatára: 2 · 3 · 5, a 16 pedig négy prímszám szorzatára: 2 · 2 · 2 · 2. Az ilyen szorzatot prímtényezős felbontásnak nevezzük. Azt mondjuk tehát, hogy a 10 prímtényezős felbontása 2 · 5.

Magának a prímszámnak a legegyszerűbb a prímtényezős felbontása, mert azt már nem kell tovább bontani. A 7 prímtényezős felbontása egyszerűen 7.

Számítsd ki a prímtényezős felbontást

Mit mond ki a számelmélet alaptétele

A számelmélet alaptétele, más néven az aritmetika alaptétele tehát két dolgot állít:

• minden 1-nél nagyobb természetes számhoz meg tudjuk találni a prímtényezős felbontást,
• minden számnak pontosan egy egyedi prímtényezős felbontása van.

Bizonyítsuk be, hogy ez valóban így van.

A létezés bizonyítása

Először bebizonyítjuk, hogy minden 1-nél nagyobb természetes számnak valóban létezik legalább egy prímtényezős felbontása. Ehhez a teljes indukciót használjuk. A teljes indukció első lépése az lesz, hogy kimondjuk: a legkisebb 1-nél nagyobb természetes szám, vagyis a 2, prímszám.

Most megmutatjuk, hogy ha már van egy 2, …, n számokból álló sorozatunk, amelynek minden számához található prímtényezős felbontás, akkor ha a sorozathoz hozzávesszük az n + 1 számot, ehhez az új számhoz is létezik prímtényezős felbontás. Először nézzük meg ezt egy példán.

Az elején a 2, …, n sorozatunk kissé torz, mert csak egy számot tartalmaz, a 2-t. Azt mondjuk, hogy ha ehhez a sorozathoz hozzávesszük az n + 1 számot, vagyis a 3-at, akkor ehhez a számhoz létezni fog prímtényezős felbontás. Mivel a 3 prímszám, természetesen létezik hozzá prímtényezős felbontás – maga a 3.

A 2, …, n sorozatunknak most két tagja van: 2, 3. Vegyük hozzá a sorozathoz a 4-et. A 4 nem prímszám, tehát felbontható két másik természetes szám szorzatára, amelyek nagyobbak 1-nél, de kisebbek 4-nél. Ezek a számok viszont mind benne vannak a sorozatunkban! A sorozatban pedig csak olyan számok vannak, amelyeknek van prímtényezős felbontásuk! Tehát a 4-nek is van prímtényezős felbontása: 2 · 2.

Visszatérve az általános bizonyításhoz, azt írhatjuk, hogy a 2 prímszám, tehát van prímtényezős felbontása. Tegyük fel most, hogy a 2, …, n sorozat minden száma felbontható prímszámok szorzatára – ez az indukciós feltevésünk. Ekkor az n + 1 szám vagy prímszám, és akkor triviálisan felbontható prímszámokra, vagy összetett szám. Ehhez a számhoz tehát léteznek olyan a, b számok, hogy

$$n+1=a\cdot b$$

és természetesen ezek a természetes számok kisebbek, mint n + 1, és nagyobbak, mint 1:

$$\begin{array}{rcl}a>1,& & a<n+1\\ b>1,& & b<n+1\end{array}$$

Az a, b számok tehát benne vannak a 2, …, n sorozatban. Ennek a sorozatnak minden számához viszont létezik prímtényezős felbontás (ez az indukciós feltevésünk), vagyis felírhatjuk, hogy

$$\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}$$

ahol az összes p_i és q_j prímszám, a p₁ · p₂ · … · p_i és a q₁ · q₂ · … · q_j pedig a két szám prímtényezős felbontása. Mivel azt mondtuk, hogy az n + 1 felbontható az n + 1 = a · b szorzatra, egyúttal igaz, hogy

$$\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}$$

Az n + 1 szám tehát felbontható a p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j prímszámszorzatra, vagyis az újonnan hozzávett n + 1 számnak is van prímtényezős felbontása. Ebből következik, hogy minden 1-nél nagyobb természetes számnak van legalább egy prímtényezős felbontása.

Az egyértelműség bizonyítása

Mutassuk meg most, hogy egyetlen 1-nél nagyobb természetes számnak sincs több prímtényezős felbontása. A tételt indirekt bizonyítással bizonyítjuk. Feltesszük, hogy a tétel nem igaz, tehát feltesszük, hogy létezik egy 1-nél nagyobb n természetes szám, amelynek két különböző prímtényezős felbontása van:

$$\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}$$

Tegyük fel egyúttal, hogy az összes olyan szám közül, amelynek több prímtényezős felbontása van, az n a legkisebb. Vagyis nincs olyan kisebb természetes szám, amelynek egynél több prímtényezős felbontása lenne. Mivel a q₁ az egyik prímszám, amely osztja az n-et, természetesen az is igaz, hogy a q₁ osztja a p₁ · p₂ · … · p_i szorzatot.

Ezután használnunk kell Eukleidész lemmáját. Ez azt mondja ki, hogy ha egy p prímszám osztja két egész szám a · b szorzatát, akkor p osztja az a és a b számok közül legalább az egyiket. Példa: a 3 prímszám osztja a 84-et. A 84-et felbonthatjuk a 12 · 7 szorzatra. Eukleidész lemmája szerint a 3 osztja a 12 és a 7 közül legalább az egyiket – ebben az esetben a 12-t.

Ennek a lemmának a segítségével mondhatjuk, hogy ha a q₁ osztja a p₁ · p₂ · … · p_i szorzatot, akkor a p₁, p₂, …, p_i számok közül is kell osztania legalább az egyiket. Feltehetjük – az általánosság megszorítása nélkül –, hogy a q₁ osztja a p₁-et. A p₁ viszont szintén prímszám. Mikor oszthat egy prímszám egy másik prímszámot? Például melyik prímszám osztható a 7-tel? Megint csak a 7. Nem oszthat másik prímszámot, mert akkor az nem lenne prímszám. Tehát szükségképpen p₁ = q₁.

Ez azt jelenti, hogy mindkét prímtényezős felbontásban van egy azonos prímszám: a p₁, illetve a q₁. Osszuk el mindkét egyenletet a p₁-gyel, illetve a q₁-gyel:

$$\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}$$

Mivel p₁ = q₁, a bal oldalon ugyanazt a számot kapjuk, jelöljük például m-mel. Tehát

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

A jobb oldalon csak egyszerűsítjük a törteket:

$$\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}$$

Az m biztosan természetes szám, amely kisebb, mint az n, mert az m úgy keletkezett, hogy az n-et elosztottuk az egyik prímtényezőjével. Az egyenletek jobb oldalán viszont mindkét esetben az m prímtényezős felbontása áll. Sikerült tehát találnunk egy másik, az n-nél kisebb m számot, amelynek szintén két különböző prímtényezős felbontása van. Ez pedig ellentmond annak a feltevésünknek, hogy az n a legkisebb olyan szám, amelynek egynél több egyedi prímtényezős felbontása van.

Az egyetlen magyarázat tehát az, hogy nem létezik „legkisebb szám, amelynek egynél több prímtényezős felbontása van”. És az, hogy nem létezik „legkisebb szám, amelynek egynél több prímtényezős felbontása van”, azt jelenti, hogy nincs egyetlen olyan szám sem, amelynek több prímtényezős felbontása lenne – minden 1-nél nagyobb egész számnak tehát pontosan egy egyedi prímtényezős felbontása van.