Twitterフォローよろしくお願いします!

不定方程式②(互除法)

スポンサーリンク
スポンサーリンク

今回の問題は「不定方程式②(互除法)」です。

問題次の方程式の整数解を1つ求めよ。$${\small (1)}~44x+35y=1$$$${\small (2)}~44x+35y=3$$

 

スポンサーリンク
スポンサーリンク

不定方程式とユークリッドの互除法

Point:不定方程式とユークリッドの互除法不定方程式において、係数が大きく整数解が見つけにくいときユークリッドの互除法を用いて整数解を求めます。
\(ax+by=1\) において、
① 係数 \(a~,~b\) より、ユークリッドの互除法の計算を余りが \(1\) となるまで行います。
互除法で得た式を式変形し、代入することを繰り返して、

$$a\cdot s+b\cdot t=1$$

と式変形します。
③ この式より整数解の1つの組は$$~~~x=s~,~y=t$$となります。
 
また、右辺が定数 \(c\) のとき
\(ax+by=c\) において、
\(ax+by=1\) として考えて、上の解法の手順より、整数解の1つの組を求めます。$$~~~a\cdot s+b\cdot t=1$$② この式より、両辺を \(c\) 倍すると、$$~~~a\cdot sc+b\cdot tc=c$$これより、整数解は$$~~~x=cs~,~y=ct$$となります。

 

問題解説:不定方程式②(互除法)

問題解説(1)

問題次の方程式の整数解を1つ求めよ。$${\small (1)}~44x+35y=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$$よって、この式より整数解の1つの組は、$$~~~x=4~,~y=-5$$となります。

 

問題解説(2)

問題次の方程式の整数解を1つ求めよ。$${\small (2)}~44x+35y=3$$

問題(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$$よって、この式より整数解の1つの組は、$$~~~x=12~,~y=-15$$となります。

 

今回のまとめ

ユークリッドの互除法を用いて整数解を求める解法は、互除法の式変形が重要となります。しっかりと計算できるように練習しておきましょう。

【問題一覧】数学A:整数の性質
このページは「高校数学A:整数の性質」の問題一覧ページとなります。解説の見たい単元名がわからない...