a1,a2,⋯,an hepsi birden 0 olmayan tamsayılar olmak üzere şu kümeyi tanımlayalım.
A={a1b1+a2b2+⋯+anbn:b1,b2,⋯bn∈Z}∩N+
Eğer ki her i için ai=bi alırsak A kümesinin bir elemanı bulunmuş olur yani A kümesi boş değil. Boş olmayan her doğal sayıların alt kümesi olan bir kümenin bir en küçük elemanı vardır. A kümesinin en küçük elemanına d diyelim o zaman d=a1b1+⋯+anbn olur. ai sayılarını d'ye bölelim.
a1=dq1+r1,d>r1≥0
a2=dq2+r2,d>r2≥0
⋮
an=dqn+rn,d>rn≥0
Şimdi ri sayılarını yalnız bırakalım. Herhangi bir rm sayısı için
rm=am−dqm=am−(a1b1+⋯+anbn)qm=a1(−b1qm)+⋯+am(1−bmqm)+⋯+an(−bnqn) olur. Bu rm sayısı 0'dan büyük olursa ∈A olacağından çelişki çıkar. Çünkü biz d'yi A'nın en küçük elemanı seçmiştik ve rm<d olduğundan en küçük elemandan daha küçük eleman bulmuş oluruz. Yani rm=0 olmalıdır.
Böylece m={1,2,⋯,n} için am=dqm yazabiliriz.
Herhangi bir c∈N ve c/a1,a2,⋯,an sayısı alalım. Bu c sayısı a1b1+a2b2+⋯+anbn sayısınıda böler. Dolayısıyla d'yide böler. a1,a2,⋯,an sayılarının her ortak böleni d'yide böldüğünden d=(a1,a2,⋯,an) olur.