Bizonyítás
Először nézzük azt az esetet, amikor n pozitív, azaz n\gt 0. Ekkor ugye |n|=n a 17.19. Definíció alapján. Tegyük fel, hogy n-nek létezik 1-nél nagyobb, de |n|=n-nél kisebb osztója, és mutassuk meg, hogy ekkor n összetett. Jelöljük ezt a feltételezett osztót k-val. Azaz teljesülnek az alábbiak:
A k|n oszthatóság a 16.1. Definíció alapján azt jelenti, hogy létezik olyan l egész szám, hogy teljesül az alábbi egyenlet:
A 16.11. Definíció alapján azt kell bizonyítani, hogy ez a szorzat n-nek egy nemtriviális felbontása, azaz sem k, sem pedig l nem egység, és nem is asszociáltja n-nek.
Egyrészt a 16.5. Tétel alapján az egész számok \Z gyűrűjében az 1-en és a -1-en kívül nincs más egység. Mivel 1 pozitív, ezért a 15.12. Definíció utáni megjegyzés alapján -1 negatív. Emiatt k biztosan nem lehet egység, hiszen ő maga pozitív, továbbá határozottan nagyobb 1-nél.
Másrészt a 16.10. Tétel alapján n-nek mindössze két asszociáltja van, méghozzá önmaga, és az ellentettje, azaz -n. Mivel n pozitív, ezért a 15.12. Definíció utáni megjegyzés alapján -n negatív. Emiatt viszont k biztosan nem lehet n asszociáltja sem, hiszen ő maga pozitív, továbbá határozottan kisebb n-nél.
A k egész szám tehát egy olyan osztója n-nek, amely se nem egység, se nem asszociáltja n-nek. Most ugyanezt kellene megmutatni a fenti szorzat másik tényezőjéről, azaz l-ről is. Ez viszont automatikusan teljesül a 16.12. Tétel miatt. Ha ugyanis l egység lenne, akkor ez alapján k szükségképpen n-nek asszociáltja lenne. Ha viszont l asszociáltja lenne n-nek, akkor k szükségképpen egység lenne. Mindkét esetről láttuk, hogy nem ez a helyzet. Megtaláltuk tehát n-nek egy nemtriviális felbontását, így ő a 16.11. Definíció alapján valóban összetett.
Visszafelé: Tegyük most fel indirekt, hogy n összetett ugyan, ám mégsem létezik olyan osztója, amely 1-nél nagyobb, de |n|=n-nél kisebb. Mivel összetett, így a 16.11. Definíció alapján létezik valamilyen nemtriviális felbontása. Például:
Egyrészt, mivel n\neq 0, ezért a 16.2. Tétel 4. pontja alapján k és l egyike sem lehet 0. Másrészt, mivel a fenti felbontás ugye nemtriviális, ezért egyikük sem lehet egység, továbbá egyikük sem lehet asszociáltja n-nek. Harmadrészt, indirekt feltevésünk miatt egyikük sem eshet az 1 és az |n|=n közötti számtartományba. Végül negyedrészt a 17.2. Lemma alapján egyikük sem lehet nagyobb n-nél. Összefoglalva tehát k és l mindketten negatívak, határozottan kisebbek -1-nél, továbbá -n-től különbözőek. Ezt mutatja a 23.2. ábra.
Az n=kl egyenlet miatt azonban a 15.1. Tétel 4. pontja alapján teljesül az alábbi egyenlet is:
A k és l egész számok ellentettjei tehát szintén osztói n-nek, mindketten pozitívak, határozottan nagyobbak 1-nél, továbbá n-től különbözőek. Ezt az alábbi a 23.3. ábra.
A 17.2. Lemma miatt az n-nél nagyobb számtartományt ismételten kizárhatjuk. Így végülis indirekt feltételezésünkkel ellentétben mégiscsak találtunk két olyan osztót – nevezetesen a -k és -l egész számokat –, amelyek 1-nél nagyobbak, de |n|=n-nél kisebbek.
Végezetül nézzük most azt az esetet, amikor n negatív, azaz n\lt 0. Ekkor egyrészt a 15.12. Definíció utáni megjegyzés alapján -n pozitív. Másrészt pedig a 16.8. Tétel 1. pontja alapján ő n-nek asszociáltja, azaz pontosan ugyanazok az osztói, mint n-nek. Így n akkor és csak akkor prím, ha -n is, amelyre viszont pozitivitása miatt szóról szóra alkalmazható a fenti gondolatmenet.
∎