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

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