不定方程式とユークリッドの互除法
\(ax+by=1\) において、
① 係数 \(a~,~b\) より、ユークリッドの互除法の計算を余りが \(1\) となるまで行います。
② 互除法で得た式を式変形し、代入することを繰り返して、
と式変形します。
③ この式より整数解の１つの組は$$~~~x=s~,~y=t$$となります。
また、右辺が定数 \(c\) のとき
\(ax+by=c\) において、
① \(ax+by=1\) として考えて、上の解法の手順より、整数解の１つの組を求めます。$$~~~a\cdot s+b\cdot t=1$$② この式より、両辺を \(c\) 倍すると、$$~~~a\cdot sc+b\cdot tc=c$$これより、整数解は$$~~~x=cs~,~y=ct$$となります。
問題解説：不定方程式②（互除法）
問題解説(1)
\(44\) と \(35\) について、ユークリッドの互除法を用いると、$$~~~44\div35=1\cdots9$$よって、$$~~~44=35\times1+9~~\cdots{\large ①}$$次にこのときの割った数 \(35\) を余り \(9\) で割ると、$$~~~35\div9=3\cdots8$$よって、$$~~~35=9\times3+8~~\cdots{\large ②}$$次にこのときの割った数 \(9\) を余り \(8\) で割ると、$$~~~9\div8=1\cdots1$$よって、$$~~~9=8\times1+1~~\cdots{\large ③}$$
①～③の式で問題文で与えられた式の係数の \(44~,~35\) と、それぞれの式の余りの数 \(9~,~8~,1\) は計算してはいけないので枠で囲っておきます。$$~~~\fbox{44}=\fbox{35}\times1+\fbox{9}~~\cdots{\large ①}$$$$~~~\fbox{35}=\fbox{9}\times3+\fbox{8}~~\cdots{\large ②}$$$$~~~\fbox{9}=\fbox{8}\times1+\fbox{1}~~\cdots{\large ③}$$
ここで、③の式より、$$\hspace{ 10 pt}\fbox{9}-\fbox{8}\times1=\fbox{1}$$②の式より、\(\fbox{8}=\fbox{35}-\fbox{9}\times3\) となり代入すると、$$\hspace{ 10 pt}\fbox{9}-(\fbox{35}-\fbox{9}\times3)\times1=\fbox{1}$$$$\hspace{ 18 pt}\fbox{9}-\fbox{35}\times1+\fbox{9}\times3=\fbox{1}$$\(\fbox{9}\) を共通因数としてくくると、$$\hspace{ 10 pt}\fbox{9}\times(1+3)-\fbox{35}\times1=\fbox{1}$$$$\hspace{ 35 pt}\fbox{9}\times4-\fbox{35}\times1=\fbox{1}$$次に①の式より、\(\fbox{9}=\fbox{44}-\fbox{35}\times1\) となり代入すると、$$\hspace{ 10 pt}(\fbox{44}-\fbox{35}\times1)\times4-\fbox{35}\times1=\fbox{1}$$$$\hspace{ 18 pt}\fbox{44}\times4-\fbox{35}\times4-\fbox{35}\times1=\fbox{1}$$\(\fbox{35}\) を共通因数としてくくると、$$\hspace{ 10 pt}\fbox{44}\times4+\fbox{35}\times(-4-1)=\fbox{1}$$$$\hspace{ 28 pt}\fbox{44}\times4+\fbox{35}\times(-5)=1$$よって、この式より整数解の１つの組は、$$~~~x=4~,~y=-5$$となります。
問題解説(2)
問題(1)の解より、$$~~~44\times4+35\times(-5)=1$$この式の両辺に \(3\) をかけると、$$\hspace{ 10 pt}44\times4\times3+35\times(-5)\times3=1\times3$$$$\hspace{ 35 pt}44\times12+35\times(-15)=3$$よって、この式より整数解の１つの組は、$$~~~x=12~,~y=-15$$となります。
今回のまとめ
ユークリッドの互除法を用いて整数解を求める解法は、互除法の式変形が重要となります。しっかりと計算できるように練習しておきましょう。
