ax+by=1 の整数解（互除法の利用）（A）

互除法を用いて 1 つの解を求める． \[ 17=12\cdot 1+5,\quad 12=5\cdot 2+2,\quad 5=2\cdot 2+1 \] 逆にたどると \begin{align*} 1&=5-2\cdot 2=5-(12-5\cdot 2)\cdot 2=5\cdot 5-12\cdot 2\\ &=(17-12)\cdot 5-12\cdot 2=17\cdot 5+12\cdot(-7) \end{align*} よって $17\cdot 5+12\cdot(-7)=1$．与式から辺々引いて \[ 17(x-5)+12(y+7)=0 \qquad 17(x-5)=-12(y+7) \] 17 と 12 は互いに素であるから，$x-5$ は 12 の倍数で，$x-5=12k$（$k$ は整数）とおくと $y+7=-17k$ よって $x=12k+5$，$y=-17k-7$（$k$ は整数）