Důkaz. Nechť $M_{a,b}=\{ax+by|x,y\in \mathbb{Z}\}$. Taková množina je uzavřená na sčítání a násobení (důkaz triviální). Nechť $u=\min (M_{a,b}\cap \mathbb{N})$. $u$ musí být dělitelné $\gcd (a,b)$, jelikož je součtem dvou čísel, která jsou jím dělitelná. Předpokládejme sporem, že $u\nmid a$. Potom ale $a-(amodu)\in M_{a,b}$, což je spor s minimalitou $u$. Tedy $u|a$ a analogicky $u|b$, z čehož plyne $u\le \gcd (a,b)$. Jelikož zároveň $\gcd (a,b)|u$, musí být $u=\gcd (a,b)$, čímž je důkaz hotov.

Důkaz. $M_{a,b}=\{ax+by|x,y\in \mathbb{Z}\}=\{(a-b)x+b(x+y)|x,y\in \mathbb{Z}\}=\{(a-b)x+bz|x,z\in \mathbb{Z}\}=M_{a-b,b}$