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ボタン