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.

∎