整数$a$, $b$の最大公約数が$1$のとき, $a$と$b$は互いに素と言います｡ 整数$a$と$b$を互いに素とします｡ すると, 任意の整数$c$に対して, $x$と$y$を変数とする方程式 \[ax+by = c\] は解$(x,y)$を持つことを証明してください｡
仮定より, $\gcd(a, b)=1$なので, ユークリッドの互除法より \[ am + bn = 1\] を満たす整数$m, n$が存在します｡
この式の両辺に$c$を掛け合わせると \[a(mc) + b(nc) = c\] となります｡ これより, $(x, y) = (mc, nc)$が方程式$ax+by=c$の解であることがわかります｡