2元1次不定方程式の整数解とユークリッドの互除法
2元1次不定方程式の整数解
\[ ax+by=c \]
\(a,b\)は互いに素とする。
解を1つ見つける。
その解を\((x,y)=(x_{0},y_{0})\)とすると元の不定方程式は\(a(x-x_{0})+b(y-y_{0})=0\)となる。
\(t\in\mathbb{Z}\)として\(x-x_{0}=bt,y-y_{0}=-at\)が一般解となる。
\(a\)と\(b\)は互いに素な整数とする。
\(ax+by=1\)のタイプの不定方程式は\(a\)と\(b\)に対しユークリッドの互除法を使うと解が1つ求まる。
(*)
\(11x+7y=1\)
の不定方程式は11と7に対しユークリッドの互除法を使うと
\begin{align*} 11 & =7\times1+4\\ 7 & =4\times1+3\\ 4 & =3\times1+1 \end{align*}
となるので、これを逆に使っていくと、
\begin{align*} 1 & =4-3\\ & =4-(7-4)\\ & =7\times(-1)+4\times2\\ & =7\times(-1)+(11-7)\times2\\ & =11\times2+7\times(-3) \end{align*}
となる。
これより、\((x,y)=(2,-3)\)が一つの解となる。
(*)-2
\begin{align*} 11 & =-7\times-1+4-7\\ & =4\times-2+14\\ & =3\times1+1 \end{align*}
となるので、
\begin{align*} 1 & =4-3\\ & =4-(7-4)\\ & =7\times(-1)+4\times2\\ & =7\times(-1)+(11-7)\times2\\ & =11\times2+7\times(-3) \end{align*}
これより、\((x,y)=(2,-3)\)が一つの解となる。
ページ情報
タイトル | 2元1次不定方程式の整数解とユークリッドの互除法 |
URL | https://www.nomuramath.com/gh7ca8oy/ |
SNSボタン |