2元1次不定方程式の整数解とユークリッドの互除法
2元1次不定方程式の整数解
\[ ax+by=c \] \(a,b\)は互いに素とする。
解を1つ見つける。
その解を\(\left(x,y\right)=\left(x_{0},y_{0}\right)\)とすると元の不定方程式は\(a\left(x-x_{0}\right)+b\left(y-y_{0}\right)=0\)となる。
\(t\in\mathbb{Z}\)として\(x-x_{0}=bt,y-y_{0}=-at\)が一般解となる。
\[ ax+by=c \] \(a,b\)は互いに素とする。
解を1つ見つける。
その解を\(\left(x,y\right)=\left(x_{0},y_{0}\right)\)とすると元の不定方程式は\(a\left(x-x_{0}\right)+b\left(y-y_{0}\right)=0\)となる。
\(t\in\mathbb{Z}\)として\(x-x_{0}=bt,y-y_{0}=-at\)が一般解となる。
\(a,b\in\mathbb{Z}\)として、2元1次不定方程式
\[ ax+by=\gcd\left(a,b\right) \] を満たす整数解\(x,y\in\mathbb{Z}\)を1つ求めるには次のようにすればよい。
\(a_{0}=a,b_{0}=b\)として、\(r_{n}\in\left\{ 0,1,\cdots,q_{n}-1\right\} ,a_{n+1}=b_{n},b_{n+1}=r_{n}\)とすると、
\[ a_{0}=q_{0}b_{0}+r_{0} \] \[ a_{1}=q_{1}b_{1}+r_{1} \] \[ a_{2}=q_{2}b_{2}+r_{2} \] \[ \vdots \] \[ a_{N-1}=q_{N-1}b_{N-1}+r_{N-1} \] \[ a_{N}=q_{N}b_{N}+r_{N} \] \begin{align*} a_{N+1} & =q_{N+1}b_{N+1}+r_{N+1}\\ & =q_{N+1}b_{N+1} \end{align*} となり、最後に余り\(r_{N+1}\)が0になる。
このとき、ユークリッドの互除法より、
\begin{align*} \gcd\left(a,b\right) & =\gcd\left(a_{0},b_{0}\right)\\ & =\gcd\left(a_{1},b_{1}\right)\\ & =\cdots\\ & =\gcd\left(a_{N+1},b_{N+1}\right)\\ & =\gcd\left(q_{N+1}b_{N+1},b_{N+1}\right)\cmt{\because a_{N+1}=q_{N+1}b_{N+1}}\\ & =b_{N+1}\\ & =r_{N}\\ & =a_{N}-q_{N}b_{N}\cmt{\because a_{N}=q_{N}b_{N}+r_{N}}\\ & =b_{N-1}-q_{N}r_{N-1}\cmt{\because a_{n+1}=b_{n},b_{n+1}=r_{n}}\\ & =b_{N-1}-q_{N}\left(a_{N-1}-q_{N-1}b_{N-1}\right)\cmt{\because a_{N}=q_{N}b_{N}+r_{N}}\\ & =-q_{N}a_{N-1}+\left(1+q_{N}q_{N-1}\right)b_{N-1}\\ & =-q_{N}b_{N-2}+\left(1+q_{N}q_{N-1}\right)r_{N-2}\cmt{\because a_{n+1}=b_{n},b_{n+1}=r_{n}}\\ & =-q_{N}b_{N-2}+\left(1+q_{N}q_{N-1}\right)\left(a_{N-2}-q_{N-2}b_{N-2}\right)\cmt{\because a_{N}=q_{N}b_{N}+r_{N}}\\ & =\left(1+q_{N}q_{N-1}\right)a_{N-2}-\left(q_{N}+q_{N-2}+q_{N}q_{N-1}q_{N-2}\right)b_{N-2}\\ & =\left(1+q_{N}q_{N-1}\right)b_{N-3}-\left(q_{N}+q_{N-2}+q_{N}q_{N-1}q_{N-2}\right)r_{N-3}\cmt{\because a_{n+1}=b_{n},b_{n+1}=r_{n}}\\ & =\left(1+q_{N}q_{N-1}\right)b_{N-3}-\left(q_{N}+q_{N-2}+q_{N}q_{N-1}q_{N-2}\right)\left(a_{N-3}-q_{N-3}b_{N-3}\right)\cmt{\because a_{N}=q_{N}b_{N}+r_{N}}\\ & =-\left(q_{N}+q_{N-2}+q_{N}q_{N-1}q_{N-2}\right)a_{N-3}+\left(1+q_{N}q_{N-1}+q_{N}q_{N-3}+q_{N-2}q_{N-3}+q_{N}q_{N-1}q_{N-2}q_{N-3}\right)b_{N-3}\\ & =\cdots \end{align*} となり、計算を続けると、
\begin{align*} \gcd\left(a,b\right) & =x\left(q_{1},q_{2},\cdots,q_{N}\right)a_{0}+y\left(q_{0},q_{1},q_{2},\cdots,q_{N}\right)b_{0}\\ & =x\left(q_{1},q_{2},\cdots,q_{N}\right)a+y\left(q_{0},q_{1},q_{2},\cdots,q_{N}\right)b \end{align*} となるので、\(x,y\)を求めることができる。
\[ ax+by=\gcd\left(a,b\right) \] を満たす整数解\(x,y\in\mathbb{Z}\)を1つ求めるには次のようにすればよい。
\(a_{0}=a,b_{0}=b\)として、\(r_{n}\in\left\{ 0,1,\cdots,q_{n}-1\right\} ,a_{n+1}=b_{n},b_{n+1}=r_{n}\)とすると、
\[ a_{0}=q_{0}b_{0}+r_{0} \] \[ a_{1}=q_{1}b_{1}+r_{1} \] \[ a_{2}=q_{2}b_{2}+r_{2} \] \[ \vdots \] \[ a_{N-1}=q_{N-1}b_{N-1}+r_{N-1} \] \[ a_{N}=q_{N}b_{N}+r_{N} \] \begin{align*} a_{N+1} & =q_{N+1}b_{N+1}+r_{N+1}\\ & =q_{N+1}b_{N+1} \end{align*} となり、最後に余り\(r_{N+1}\)が0になる。
このとき、ユークリッドの互除法より、
\begin{align*} \gcd\left(a,b\right) & =\gcd\left(a_{0},b_{0}\right)\\ & =\gcd\left(a_{1},b_{1}\right)\\ & =\cdots\\ & =\gcd\left(a_{N+1},b_{N+1}\right)\\ & =\gcd\left(q_{N+1}b_{N+1},b_{N+1}\right)\cmt{\because a_{N+1}=q_{N+1}b_{N+1}}\\ & =b_{N+1}\\ & =r_{N}\\ & =a_{N}-q_{N}b_{N}\cmt{\because a_{N}=q_{N}b_{N}+r_{N}}\\ & =b_{N-1}-q_{N}r_{N-1}\cmt{\because a_{n+1}=b_{n},b_{n+1}=r_{n}}\\ & =b_{N-1}-q_{N}\left(a_{N-1}-q_{N-1}b_{N-1}\right)\cmt{\because a_{N}=q_{N}b_{N}+r_{N}}\\ & =-q_{N}a_{N-1}+\left(1+q_{N}q_{N-1}\right)b_{N-1}\\ & =-q_{N}b_{N-2}+\left(1+q_{N}q_{N-1}\right)r_{N-2}\cmt{\because a_{n+1}=b_{n},b_{n+1}=r_{n}}\\ & =-q_{N}b_{N-2}+\left(1+q_{N}q_{N-1}\right)\left(a_{N-2}-q_{N-2}b_{N-2}\right)\cmt{\because a_{N}=q_{N}b_{N}+r_{N}}\\ & =\left(1+q_{N}q_{N-1}\right)a_{N-2}-\left(q_{N}+q_{N-2}+q_{N}q_{N-1}q_{N-2}\right)b_{N-2}\\ & =\left(1+q_{N}q_{N-1}\right)b_{N-3}-\left(q_{N}+q_{N-2}+q_{N}q_{N-1}q_{N-2}\right)r_{N-3}\cmt{\because a_{n+1}=b_{n},b_{n+1}=r_{n}}\\ & =\left(1+q_{N}q_{N-1}\right)b_{N-3}-\left(q_{N}+q_{N-2}+q_{N}q_{N-1}q_{N-2}\right)\left(a_{N-3}-q_{N-3}b_{N-3}\right)\cmt{\because a_{N}=q_{N}b_{N}+r_{N}}\\ & =-\left(q_{N}+q_{N-2}+q_{N}q_{N-1}q_{N-2}\right)a_{N-3}+\left(1+q_{N}q_{N-1}+q_{N}q_{N-3}+q_{N-2}q_{N-3}+q_{N}q_{N-1}q_{N-2}q_{N-3}\right)b_{N-3}\\ & =\cdots \end{align*} となり、計算を続けると、
\begin{align*} \gcd\left(a,b\right) & =x\left(q_{1},q_{2},\cdots,q_{N}\right)a_{0}+y\left(q_{0},q_{1},q_{2},\cdots,q_{N}\right)b_{0}\\ & =x\left(q_{1},q_{2},\cdots,q_{N}\right)a+y\left(q_{0},q_{1},q_{2},\cdots,q_{N}\right)b \end{align*} となるので、\(x,y\)を求めることができる。
\(a\)と\(b\)は互いに素な整数とする。
\(ax+by=1\)のタイプの不定方程式は\(a\)と\(b\)に対しユークリッドの互除法を使うと解が1つ求まる。
\(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-\left(7-4\right)\\ & =7\times\left(-1\right)+4\times2\\ & =7\times\left(-1\right)+\left(11-7\right)\times2\\ & =11\times2+7\times\left(-3\right) \end{align*} となる。
これより、\(\left(x,y\right)=\left(2,-3\right)\)が一つの解となる。
別解
\begin{align*} 11 & =-7\times-1+4-7\\ & =4\times-2+14\\ & =3\times1+1 \end{align*} となるので、\begin{align*} 1 & =4-3\\ & =4-\left(7-4\right)\\ & =7\times\left(-1\right)+4\times2\\ & =7\times\left(-1\right)+\left(11-7\right)\times2\\ & =11\times2+7\times\left(-3\right) \end{align*} これより、\(\left(x,y\right)=\left(2,-3\right)\)が一つの解となる。
別解2
\begin{align*} 11x+7y=1 & \Leftrightarrow\left(7+4\right)x+7y=1\\ & \Leftrightarrow7\left(x+y\right)+4x=1\\ & \Leftrightarrow7z+4x=1\cmt{z=x+y}\\ & \Leftrightarrow\left(4+3\right)z+4x=1\\ & \Leftrightarrow4\left(z+x\right)+3z=1\\ & \Leftrightarrow4z'+3z=1\cmt{z'=z+x}\\ & \Leftrightarrow\left(3+1\right)z'+3z=1\\ & \Leftrightarrow3\left(z'+z\right)+z'=1\\ & \Leftrightarrow3z''+z'=1\cmt{z''=z'+z} \end{align*} となるので、\(z''=0,z'=1\)が解の1つとなる。これより、
\begin{align*} 1 & =z'\\ & =z+x\\ & =x+y+x\\ & =2x+y \end{align*} \begin{align*} 0 & =z''\\ & =z'+z\\ & =\left(2x+y\right)+\left(x+y\right)\\ & =3x+2y \end{align*} となり、これを解くと、\(\left(x,y\right)=\left(2,-3\right)\)となる。
従って、解の1つは\(\left(x,y\right)=\left(2,-3\right)\)となる。
ページ情報
タイトル | 2元1次不定方程式の整数解とユークリッドの互除法 |
URL | https://www.nomuramath.com/gh7ca8oy/ |
SNSボタン |
二元不定方程式
\[
ax+by=c
\]
オイラーの規準
\[
QR(a,p)\overset{p}{\equiv}a^{\frac{p-1}{2}}
\]
(*)原始根定理
\[
\varphi(p-1)
\]
(*)平方剰余の相互法則と補充法則
\[
QR(p,q)QR(q,p)=\left(-1\right)^{\frac{p-1}{2}\frac{q-1}{2}}
\]