Bizonyítás

Először azt mutatjuk meg, hogy egy tetszőleges $n\neq 0$ egész számnak mindig véges sok osztója van. Elegendő azt az esetet vizsgálni, amikor $n$ pozitív. Ha ugyanis $n$ negatív, akkor egyrészt a 15.9. Lemma 1. pontja miatt az ellentettje pozitív lenne, amely a 16.8. Tétel 1. pontja alapján $n$ asszociáltja lenne, azaz pontosan ugyanazok lennének az osztói, mint $n$-nek.

Az általánosság megsértése nélkül feltehetjük tehát, hogy $0\lt n$. A 17.2. Lemma miatt ekkor $n$ egyetlen osztója sem lehet nagyobb $n$-nél. Ebből következik, hogy $n$-nek legfeljebb $n$ darab pozitív osztója lehet. A 16.2. Tétel 8. pontja miatt ekkor azonban ezek ellentettjei is osztók, amelyek a 15.9. Lemma 1. pontja alapján mind negatívak lennének.

Tekintve, hogy a pozitív és negatív egész számok a $0$-val együtt lefedik a teljes $\Z$ halmazt, valamint a 16.2. Tétel 4. pontja miatt $0 \nmid n$, ezért $n$-nek biztosan nincs ezeken kívül több osztója, így azok száma biztosan nem több $2n$-nél – azaz valóban véges. Ebből azonnal következik, hogy a tételben szereplő $a$ és $b$ egész számok közös osztóinak száma is legfeljebb $2n$, azaz szintén véges.

Igaz továbbá, hogy az $1$ minden egész számnak osztója, hiszen ő a $\Z$ gyűrű egységeleme, és így a 16.3. Definíció utáni megjegyzés alapján egyúttal egység is. Az $a$ és $b$ közös osztóinak halmaza tehát – azonkívül, hogy véges – nem üres, így biztosan van az elemei között legnagyobb. A legnagyobb közös osztó tehát valóban létezik.

∎