>>585
p,qが0でない整数でc=(p,q)としたとき
ap+bq=c
なる整数a,bが存在
から直ちに出る

これ自体はユークリッドの互除法そのまんま