$\forall a,b \in\mathbb{Z},\exist x,y\in\mathbb{Z},ax+by=\gcd(a,b)$

设 $g = \gcd(a,b)$,则有 $k_1g =a,k_2g=b,\gcd(k_1,k_2)=1$

$k_1gx+k_2gy=g$

$k_1x+k_2y=1$

$k_1x-1=-yk_2$

$k_1x\equiv1 \pmod {k_2}$

根据欧拉定理，取 $x=k_1^{\varphi(k_2)-1}$，则 $y$ 显然存在。