このページは、「ユークリッドの互除法と1次不定方程式」の練習問題アーカイブページとなります。
この問題の解き方の詳細は↓
ユークリッドの互除法と1次不定方程式 で確認できます。
問題アーカイブ01
問題アーカイブ01次の方程式の整数解をすべて求めよ。
\({\small (1)}~34x+29y=3\)
\({\small (2)}~41x-15y=5\)
\({\small (1)}~34x+29y=3\)
\({\small (2)}~41x-15y=5\)
数研出版｜数学A[104-901] p.158 練習20
▼ より詳しい解説を開く
\({\small (1)}~34x+29y=3\) について、まず \(34x+29y=1\) を考える。\(34\) を \(29\) で割ると、
\(\begin{array}{rr}1~\\29~)~\overline{34~}\\\underline{29~}\\5~\end{array}\)
余り \(5\) より、\(29\) を \(5\) で割ると、
\(\begin{array}{rr}5~\\5~)~\overline{29~}\\\underline{25~}\\4~\end{array}\)
余り \(4\) より、\(5\) を \(4\) で割ると、
\(\begin{array}{rr}1~\\4~)~\overline{5~}\\\underline{4~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}34-29 \cdot 1=5\\29-5 \cdot 5=4\\5-4 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=34~,~b=29\) 、余りをそれぞれ \(c=5~,~d=4\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-5c=d~~~\cdots {\small [\,2\,]}\\c-d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-1)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-b+5c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
左辺に \(5c+c=6c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 6\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}6a-6b=6c\\-b+5c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~6a-6b&=&6c\\~~-b+5c&=&-d~~\\+~\big{)}~~~~~~~~c-d&=&1\\[3pt]\hline 6a-7b&=&1\end{eqnarray}\)
\(a=34~,~b=29\) より、
\(34 \cdot 6+29 \cdot (-7)=1\)
\(34x+29y=3\) の整数解を求めたいので、両辺を \(3\) 倍すると、
\(34 \cdot 18+29 \cdot (-21)=3\)
よって、\(34x+29y=3\) の整数解の \(1\) つは \((x~,~y)=(18~,~-21)\) である
\(34x+29y=3\) との差をとると、
\(\begin{eqnarray}~~~~~34x+29y&=&3\\-~\big{)}~~~34 \cdot 18+29 \cdot (-21)&=&3\\[3pt]\hline 34(x-18)+29(y+21)&=&0\end{eqnarray}\)
\(34(x-18)=-29(y+21)~~~\cdots {\small [\,4\,]}\)
\(34\) と \(29\) は互いに素より、\(x-18\) は \(29\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-18&=&29k\\[3pt]~~~x&=&29k+18\end{eqnarray}\)
\({\small [\,4\,]}\) に \(x-18=29k\) を代入して、
\(\begin{eqnarray}~~~34 \cdot 29k&=&-29(y+21)\\[3pt]~~~-29(y+21)&=&29 \cdot 34k\\[3pt]~~~y+21&=&-34k\\[3pt]~~~y&=&-34k-21\end{eqnarray}\)
したがって、方程式 \(34x+29y=3\) の整数解は \(x=29k+18~,~y=-34k-21\) （\(k\) は整数）となる
\(34x+29y=3\) について、\(34\) と \(29\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}34-29 \cdot 1=5~~~\cdots {\small [\,1\,]}\\29-5 \cdot 5=4~~~\cdots {\small [\,2\,]}\\5-4 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{4}=\enclose{circle}{29}-\enclose{circle}{5} \cdot 5\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{5}-(\enclose{circle}{29}-\enclose{circle}{5} \cdot 5) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{5}-\enclose{circle}{29}+\enclose{circle}{5} \cdot 5&=&1\\[5pt]~~~\enclose{circle}{5} \cdot 6-\enclose{circle}{29}&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{5}=\enclose{circle}{34}-\enclose{circle}{29}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{34}-\enclose{circle}{29}) \cdot 6-\enclose{circle}{29}&=&1\\[5pt]~~~\enclose{circle}{34} \cdot 6-\enclose{circle}{29} \cdot 6-\enclose{circle}{29}&=&1\\[5pt]~~~\enclose{circle}{34} \cdot 6+\enclose{circle}{29} \cdot (-7)&=&1\end{eqnarray}\)
\(34 \cdot 6+29 \cdot (-7)=1\) となるので、両辺を \(3\) 倍すると、
\(34 \cdot 18+29 \cdot (-21)=3\)
これより、\(34x+29y=3\) の整数解の \(1\) つは \((x~,~y)=(18~,~-21)\) となるので、上と同じようにして整数解を求める
\(\begin{array}{rr}2~\\15~)~\overline{41~}\\\underline{30~}\\11~\end{array}\)
余り \(11\) より、\(15\) を \(11\) で割ると、
\(\begin{array}{rr}1~\\11~)~\overline{15~}\\\underline{11~}\\4~\end{array}\)
余り \(4\) より、\(11\) を \(4\) で割ると、
\(\begin{array}{rr}2~\\4~)~\overline{11~}\\\underline{8~}\\3~\end{array}\)
余り \(3\) より、\(4\) を \(3\) で割ると、
\(\begin{array}{rr}1~\\3~)~\overline{4~}\\\underline{3~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}41-15 \cdot 2=11\\15-11 \cdot 1=4\\11-4 \cdot 2=3\\4-3 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=41~,~b=15\) 、余りをそれぞれ \(c=11~,~d=4~,~e=3\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-2b=c~~~\cdots {\small [\,1\,]}\\b-c=d~~~\cdots {\small [\,2\,]}\\c-2d=e~~~\cdots {\small [\,3\,]}\\d-e=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,4\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-e\) があらわれるので、\({\small [\,3\,]} {\, \small \times \,} (-1)\) と \({\small [\,4\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
左辺に \(2d+d=3d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} 3\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}3b-3c=3d\\-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
左辺に \(-3c-c=-4c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} (-4)\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-4a+8b=-4c\\3b-3c=3d\\-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) 、\(d\) 、\(e\) が消去できるので、
\(\begin{eqnarray}~~~~~-4a+8b&=&-4c\\~~~~~3b-3c&=&3d\\~~-c+2d&=&-e~~\\+~\big{)}~~~~~~~~d-e&=&1\\[3pt]\hline -4a+11b&=&1\end{eqnarray}\)
\(a=41~,~b=15\) より、
\(41 \cdot (-4)+15 \cdot 11=1\)
\(41x-15y=1\) の形にすると、
\(41 \cdot (-4)-15 \cdot (-11)=1\)
\(41x-15y=5\) の整数解を求めたいので、両辺を \(5\) 倍すると、
\(41 \cdot (-20)-15 \cdot (-55)=5\)
よって、\(41x-15y=5\) の整数解の \(1\) つは \((x~,~y)=(-20~,~-55)\) である
\(41x-15y=5\) との差をとると、
\(\begin{eqnarray}~~~~~41x-15y&=&5\\-~\big{)}~~~41 \cdot (-20)-15 \cdot (-55)&=&5\\[3pt]\hline 41(x+20)-15(y+55)&=&0\end{eqnarray}\)
\(41(x+20)=15(y+55)~~~\cdots {\small [\,5\,]}\)
\(41\) と \(15\) は互いに素より、\(x+20\) は \(15\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x+20&=&15k\\[3pt]~~~x&=&15k-20\end{eqnarray}\)
\({\small [\,5\,]}\) に \(x+20=15k\) を代入して、
\(\begin{eqnarray}~~~41 \cdot 15k&=&15(y+55)\\[3pt]~~~15(y+55)&=&15 \cdot 41k\\[3pt]~~~y+55&=&41k\\[3pt]~~~y&=&41k-55\end{eqnarray}\)
したがって、方程式 \(41x-15y=5\) の整数解は \(x=15k-20~,~y=41k-55\) （\(k\) は整数）となる
\(41x-15y=5\) について、\(41\) と \(15\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}41-15 \cdot 2=11~~~\cdots {\small [\,1\,]}\\15-11 \cdot 1=4~~~\cdots {\small [\,2\,]}\\11-4 \cdot 2=3~~~\cdots {\small [\,3\,]}\\4-3 \cdot 1=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,3\,]}\) より、\(\enclose{circle}{3}=\enclose{circle}{11}-\enclose{circle}{4} \cdot 2\) を \({\small [\,4\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{4}-(\enclose{circle}{11}-\enclose{circle}{4} \cdot 2) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{4}-\enclose{circle}{11}+\enclose{circle}{4} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{4} \cdot 3-\enclose{circle}{11}&=&1\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\enclose{circle}{4}=\enclose{circle}{15}-\enclose{circle}{11} \cdot 1\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{15}-\enclose{circle}{11} \cdot 1) \cdot 3-\enclose{circle}{11}&=&1\\[5pt]~~~\enclose{circle}{15} \cdot 3-\enclose{circle}{11} \cdot 3-\enclose{circle}{11}&=&1\\[5pt]~~~\enclose{circle}{15} \cdot 3-\enclose{circle}{11} \cdot 4&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{11}=\enclose{circle}{41}-\enclose{circle}{15} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{15} \cdot 3-(\enclose{circle}{41}-\enclose{circle}{15} \cdot 2) \cdot 4&=&1\\[5pt]~~~\enclose{circle}{15} \cdot 3-\enclose{circle}{41} \cdot 4+\enclose{circle}{15} \cdot 8&=&1\\[5pt]~~~\enclose{circle}{41} \cdot (-4)+\enclose{circle}{15} \cdot 11&=&1\end{eqnarray}\)
\(41 \cdot (-4)+15 \cdot 11=1\) を \(41x-15y=1\) の形にすると、
\(41 \cdot (-4)-15 \cdot (-11)=1\)
両辺を \(5\) 倍すると、
\(41 \cdot (-20)-15 \cdot (-55)=5\)
これより、\(41x-15y=5\) の整数解の \(1\) つは \((x~,~y)=(-20~,~-55)\) となるので、上と同じようにして整数解を求める
\(\begin{array}{rr}1~\\29~)~\overline{34~}\\\underline{29~}\\5~\end{array}\)
余り \(5\) より、\(29\) を \(5\) で割ると、
\(\begin{array}{rr}5~\\5~)~\overline{29~}\\\underline{25~}\\4~\end{array}\)
余り \(4\) より、\(5\) を \(4\) で割ると、
\(\begin{array}{rr}1~\\4~)~\overline{5~}\\\underline{4~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}34-29 \cdot 1=5\\29-5 \cdot 5=4\\5-4 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=34~,~b=29\) 、余りをそれぞれ \(c=5~,~d=4\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-5c=d~~~\cdots {\small [\,2\,]}\\c-d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-1)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-b+5c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
左辺に \(5c+c=6c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 6\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}6a-6b=6c\\-b+5c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~6a-6b&=&6c\\~~-b+5c&=&-d~~\\+~\big{)}~~~~~~~~c-d&=&1\\[3pt]\hline 6a-7b&=&1\end{eqnarray}\)
\(a=34~,~b=29\) より、
\(34 \cdot 6+29 \cdot (-7)=1\)
\(34x+29y=3\) の整数解を求めたいので、両辺を \(3\) 倍すると、
\(34 \cdot 18+29 \cdot (-21)=3\)
よって、\(34x+29y=3\) の整数解の \(1\) つは \((x~,~y)=(18~,~-21)\) である
\(34x+29y=3\) との差をとると、
\(\begin{eqnarray}~~~~~34x+29y&=&3\\-~\big{)}~~~34 \cdot 18+29 \cdot (-21)&=&3\\[3pt]\hline 34(x-18)+29(y+21)&=&0\end{eqnarray}\)
\(34(x-18)=-29(y+21)~~~\cdots {\small [\,4\,]}\)
\(34\) と \(29\) は互いに素より、\(x-18\) は \(29\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-18&=&29k\\[3pt]~~~x&=&29k+18\end{eqnarray}\)
\({\small [\,4\,]}\) に \(x-18=29k\) を代入して、
\(\begin{eqnarray}~~~34 \cdot 29k&=&-29(y+21)\\[3pt]~~~-29(y+21)&=&29 \cdot 34k\\[3pt]~~~y+21&=&-34k\\[3pt]~~~y&=&-34k-21\end{eqnarray}\)
したがって、方程式 \(34x+29y=3\) の整数解は \(x=29k+18~,~y=-34k-21\) （\(k\) は整数）となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(34x+29y=3\) について、\(34\) と \(29\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}34-29 \cdot 1=5~~~\cdots {\small [\,1\,]}\\29-5 \cdot 5=4~~~\cdots {\small [\,2\,]}\\5-4 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{4}=\enclose{circle}{29}-\enclose{circle}{5} \cdot 5\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{5}-(\enclose{circle}{29}-\enclose{circle}{5} \cdot 5) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{5}-\enclose{circle}{29}+\enclose{circle}{5} \cdot 5&=&1\\[5pt]~~~\enclose{circle}{5} \cdot 6-\enclose{circle}{29}&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{5}=\enclose{circle}{34}-\enclose{circle}{29}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{34}-\enclose{circle}{29}) \cdot 6-\enclose{circle}{29}&=&1\\[5pt]~~~\enclose{circle}{34} \cdot 6-\enclose{circle}{29} \cdot 6-\enclose{circle}{29}&=&1\\[5pt]~~~\enclose{circle}{34} \cdot 6+\enclose{circle}{29} \cdot (-7)&=&1\end{eqnarray}\)
\(34 \cdot 6+29 \cdot (-7)=1\) となるので、両辺を \(3\) 倍すると、
\(34 \cdot 18+29 \cdot (-21)=3\)
これより、\(34x+29y=3\) の整数解の \(1\) つは \((x~,~y)=(18~,~-21)\) となるので、上と同じようにして整数解を求める
\({\small (2)}~41x-15y=5\) について、まず \(41x-15y=1\) を考える。\(41\) を \(15\) で割ると、
\(\begin{array}{rr}2~\\15~)~\overline{41~}\\\underline{30~}\\11~\end{array}\)
余り \(11\) より、\(15\) を \(11\) で割ると、
\(\begin{array}{rr}1~\\11~)~\overline{15~}\\\underline{11~}\\4~\end{array}\)
余り \(4\) より、\(11\) を \(4\) で割ると、
\(\begin{array}{rr}2~\\4~)~\overline{11~}\\\underline{8~}\\3~\end{array}\)
余り \(3\) より、\(4\) を \(3\) で割ると、
\(\begin{array}{rr}1~\\3~)~\overline{4~}\\\underline{3~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}41-15 \cdot 2=11\\15-11 \cdot 1=4\\11-4 \cdot 2=3\\4-3 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=41~,~b=15\) 、余りをそれぞれ \(c=11~,~d=4~,~e=3\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-2b=c~~~\cdots {\small [\,1\,]}\\b-c=d~~~\cdots {\small [\,2\,]}\\c-2d=e~~~\cdots {\small [\,3\,]}\\d-e=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,4\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-e\) があらわれるので、\({\small [\,3\,]} {\, \small \times \,} (-1)\) と \({\small [\,4\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
左辺に \(2d+d=3d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} 3\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}3b-3c=3d\\-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
左辺に \(-3c-c=-4c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} (-4)\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-4a+8b=-4c\\3b-3c=3d\\-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) 、\(d\) 、\(e\) が消去できるので、
\(\begin{eqnarray}~~~~~-4a+8b&=&-4c\\~~~~~3b-3c&=&3d\\~~-c+2d&=&-e~~\\+~\big{)}~~~~~~~~d-e&=&1\\[3pt]\hline -4a+11b&=&1\end{eqnarray}\)
\(a=41~,~b=15\) より、
\(41 \cdot (-4)+15 \cdot 11=1\)
\(41x-15y=1\) の形にすると、
\(41 \cdot (-4)-15 \cdot (-11)=1\)
\(41x-15y=5\) の整数解を求めたいので、両辺を \(5\) 倍すると、
\(41 \cdot (-20)-15 \cdot (-55)=5\)
よって、\(41x-15y=5\) の整数解の \(1\) つは \((x~,~y)=(-20~,~-55)\) である
\(41x-15y=5\) との差をとると、
\(\begin{eqnarray}~~~~~41x-15y&=&5\\-~\big{)}~~~41 \cdot (-20)-15 \cdot (-55)&=&5\\[3pt]\hline 41(x+20)-15(y+55)&=&0\end{eqnarray}\)
\(41(x+20)=15(y+55)~~~\cdots {\small [\,5\,]}\)
\(41\) と \(15\) は互いに素より、\(x+20\) は \(15\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x+20&=&15k\\[3pt]~~~x&=&15k-20\end{eqnarray}\)
\({\small [\,5\,]}\) に \(x+20=15k\) を代入して、
\(\begin{eqnarray}~~~41 \cdot 15k&=&15(y+55)\\[3pt]~~~15(y+55)&=&15 \cdot 41k\\[3pt]~~~y+55&=&41k\\[3pt]~~~y&=&41k-55\end{eqnarray}\)
したがって、方程式 \(41x-15y=5\) の整数解は \(x=15k-20~,~y=41k-55\) （\(k\) は整数）となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(41x-15y=5\) について、\(41\) と \(15\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}41-15 \cdot 2=11~~~\cdots {\small [\,1\,]}\\15-11 \cdot 1=4~~~\cdots {\small [\,2\,]}\\11-4 \cdot 2=3~~~\cdots {\small [\,3\,]}\\4-3 \cdot 1=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,3\,]}\) より、\(\enclose{circle}{3}=\enclose{circle}{11}-\enclose{circle}{4} \cdot 2\) を \({\small [\,4\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{4}-(\enclose{circle}{11}-\enclose{circle}{4} \cdot 2) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{4}-\enclose{circle}{11}+\enclose{circle}{4} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{4} \cdot 3-\enclose{circle}{11}&=&1\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\enclose{circle}{4}=\enclose{circle}{15}-\enclose{circle}{11} \cdot 1\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{15}-\enclose{circle}{11} \cdot 1) \cdot 3-\enclose{circle}{11}&=&1\\[5pt]~~~\enclose{circle}{15} \cdot 3-\enclose{circle}{11} \cdot 3-\enclose{circle}{11}&=&1\\[5pt]~~~\enclose{circle}{15} \cdot 3-\enclose{circle}{11} \cdot 4&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{11}=\enclose{circle}{41}-\enclose{circle}{15} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{15} \cdot 3-(\enclose{circle}{41}-\enclose{circle}{15} \cdot 2) \cdot 4&=&1\\[5pt]~~~\enclose{circle}{15} \cdot 3-\enclose{circle}{41} \cdot 4+\enclose{circle}{15} \cdot 8&=&1\\[5pt]~~~\enclose{circle}{41} \cdot (-4)+\enclose{circle}{15} \cdot 11&=&1\end{eqnarray}\)
\(41 \cdot (-4)+15 \cdot 11=1\) を \(41x-15y=1\) の形にすると、
\(41 \cdot (-4)-15 \cdot (-11)=1\)
両辺を \(5\) 倍すると、
\(41 \cdot (-20)-15 \cdot (-55)=5\)
これより、\(41x-15y=5\) の整数解の \(1\) つは \((x~,~y)=(-20~,~-55)\) となるので、上と同じようにして整数解を求める
問題アーカイブ02
問題アーカイブ02次の方程式の整数解をすべて求めよ。
\({\small (1)}~5x+7y=1\)
\({\small (2)}~3x-2y=4\)
\({\small (3)}~16x-23y=1\)
\({\small (4)}~35x+48y=3\)
\({\small (1)}~5x+7y=1\)
\({\small (2)}~3x-2y=4\)
\({\small (3)}~16x-23y=1\)
\({\small (4)}~35x+48y=3\)
数研出版｜数学A[104-901] p.165 問題 12
▼ より詳しい解説を開く
方程式 \(5x+7y=1\) を満たす整数解の \(1\) つは \(x=3~,~y=-2\) であるので、
\(5 \cdot 3+7 \cdot (-2)=1~~~\cdots {\small [\,1\,]}\)
\({\small [\,1\,]}\) より、
\(\begin{eqnarray}~~~~~5x+7y&=&1\\-~\big{)}~~~5 \cdot 3+7 \cdot (-2)&=&1\\[3pt]\hline 5(x-3)+7(y+2)&=&0\end{eqnarray}\)
\(5(x-3)=-7(y+2)~~~\cdots {\small [\,2\,]}\)
\(\begin{eqnarray}~~~x-3&=&7k\\[3pt]~~~x&=&7k+3\end{eqnarray}\)
\({\small [\,2\,]}\) に \(x-3=7k\) を代入して、
\(\begin{eqnarray}~~~5 \cdot 7k&=&-7(y+2)\\[3pt]~~~-7(y+2)&=&7 \cdot 5k\\[3pt]~~~y+2&=&-5k\\[3pt]~~~y&=&-5k-2\end{eqnarray}\)
したがって、方程式 \(5x+7y=1\) の整数解は \(x=7k+3~,~y=-5k-2\) （\(k\) は整数）となる
\(3 \cdot 2-2 \cdot 1=4~~~\cdots {\small [\,1\,]}\)
\({\small [\,1\,]}\) より、
\(\begin{eqnarray}~~~~~3x-2y&=&4\\-~\big{)}~~~3 \cdot 2-2 \cdot 1&=&4\\[3pt]\hline 3(x-2)-2(y-1)&=&0\end{eqnarray}\)
\(3(x-2)=2(y-1)~~~\cdots {\small [\,2\,]}\)
\(\begin{eqnarray}~~~x-2&=&2k\\[3pt]~~~x&=&2k+2\end{eqnarray}\)
\({\small [\,2\,]}\) に \(x-2=2k\) を代入して、
\(\begin{eqnarray}~~~3 \cdot 2k&=&2(y-1)\\[3pt]~~~2(y-1)&=&2 \cdot 3k\\[3pt]~~~y-1&=&3k\\[3pt]~~~y&=&3k+1\end{eqnarray}\)
したがって、方程式 \(3x-2y=4\) の整数解は \(x=2k+2~,~y=3k+1\) （\(k\) は整数）となる
\(\begin{array}{rr}1~\\16~)~\overline{23~}\\\underline{16~}\\7~\end{array}\)
余り \(7\) より、\(16\) を \(7\) で割ると、
\(\begin{array}{rr}2~\\7~)~\overline{16~}\\\underline{14~}\\2~\end{array}\)
余り \(2\) より、\(7\) を \(2\) で割ると、
\(\begin{array}{rr}3~\\2~)~\overline{7~}\\\underline{6~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}23-16 \cdot 1=7\\16-7 \cdot 2=2\\7-2 \cdot 3=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=23~,~b=16\) 、余りをそれぞれ \(c=7~,~d=2\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-2c=d~~~\cdots {\small [\,2\,]}\\c-3d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-3)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-3b+6c=-3d\\c-3d=1\end{array}\right.\end{eqnarray}\)
左辺に \(6c+c=7c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 7\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}7a-7b=7c\\-3b+6c=-3d\\c-3d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~7a-7b&=&7c\\~~-3b+6c&=&-3d~~\\+~\big{)}~~~~~~~~c-3d&=&1\\[3pt]\hline 7a-10b&=&1\end{eqnarray}\)
\(a=23~,~b=16\) より、
\(23 \cdot 7-16 \cdot 10=1\)
\(16x-23y=1\) の形にすると、
\(16 \cdot (-10)-23 \cdot (-7)=1\)
よって、\(16x-23y=1\) の整数解の \(1\) つは \((x~,~y)=(-10~,~-7)\) である
\(16x-23y=1\) との差をとると、
\(\begin{eqnarray}~~~~~16x-23y&=&1\\-~\big{)}~~~16 \cdot (-10)-23 \cdot (-7)&=&1\\[3pt]\hline 16(x+10)-23(y+7)&=&0\end{eqnarray}\)
\(16(x+10)=23(y+7)~~~\cdots {\small [\,4\,]}\)
\(16\) と \(23\) は互いに素より、\(x+10\) は \(23\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x+10&=&23k\\[3pt]~~~x&=&23k-10\end{eqnarray}\)
\({\small [\,4\,]}\) に \(x+10=23k\) を代入して、
\(\begin{eqnarray}~~~16 \cdot 23k&=&23(y+7)\\[3pt]~~~23(y+7)&=&23 \cdot 16k\\[3pt]~~~y+7&=&16k\\[3pt]~~~y&=&16k-7\end{eqnarray}\)
したがって、方程式 \(16x-23y=1\) の整数解は \(x=23k-10~,~y=16k-7\) （\(k\) は整数）となる
\(16x-23y=1\) について、\(23\) と \(16\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}23-16 \cdot 1=7~~~\cdots {\small [\,1\,]}\\16-7 \cdot 2=2~~~\cdots {\small [\,2\,]}\\7-2 \cdot 3=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{2}=\enclose{circle}{16}-\enclose{circle}{7} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{7}-(\enclose{circle}{16}-\enclose{circle}{7} \cdot 2) \cdot 3&=&1\\[5pt]~~~\enclose{circle}{7}-\enclose{circle}{16} \cdot 3+\enclose{circle}{7} \cdot 6&=&1\\[5pt]~~~\enclose{circle}{7} \cdot 7-\enclose{circle}{16} \cdot 3&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{7}=\enclose{circle}{23}-\enclose{circle}{16}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{23}-\enclose{circle}{16}) \cdot 7-\enclose{circle}{16} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{23} \cdot 7-\enclose{circle}{16} \cdot 7-\enclose{circle}{16} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{23} \cdot 7-\enclose{circle}{16} \cdot 10&=&1\end{eqnarray}\)
\(23 \cdot 7-16 \cdot 10=1\) を \(16x-23y=1\) の形にすると、
\(16 \cdot (-10)-23 \cdot (-7)=1\)
これより、\(16x-23y=1\) の整数解の \(1\) つは \((x~,~y)=(-10~,~-7)\) となるので、上と同じようにして整数解を求める
\(\begin{array}{rr}1~\\35~)~\overline{48~}\\\underline{35~}\\13~\end{array}\)
余り \(13\) より、\(35\) を \(13\) で割ると、
\(\begin{array}{rr}2~\\13~)~\overline{35~}\\\underline{26~}\\9~\end{array}\)
余り \(9\) より、\(13\) を \(9\) で割ると、
\(\begin{array}{rr}1~\\9~)~\overline{13~}\\\underline{9~}\\4~\end{array}\)
余り \(4\) より、\(9\) を \(4\) で割ると、
\(\begin{array}{rr}2~\\4~)~\overline{9~}\\\underline{8~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}48-35 \cdot 1=13\\35-13 \cdot 2=9\\13-9 \cdot 1=4\\9-4 \cdot 2=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=48~,~b=35\) 、余りをそれぞれ \(c=13~,~d=9~,~e=4\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-2c=d~~~\cdots {\small [\,2\,]}\\c-d=e~~~\cdots {\small [\,3\,]}\\d-2e=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,4\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-e\) があらわれるので、\({\small [\,3\,]} {\, \small \times \,} (-2)\) と \({\small [\,4\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-2c+2d=-2e\\d-2e=1\end{array}\right.\end{eqnarray}\)
左辺に \(2d+d=3d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} 3\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}3b-6c=3d\\-2c+2d=-2e\\d-2e=1\end{array}\right.\end{eqnarray}\)
左辺に \(-6c-2c=-8c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} (-8)\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-8a+8b=-8c\\3b-6c=3d\\-2c+2d=-2e\\d-2e=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) 、\(d\) 、\(e\) が消去できるので、
\(\begin{eqnarray}~~~~~-8a+8b&=&-8c\\~~~~~3b-6c&=&3d\\~~-2c+2d&=&-2e~~\\+~\big{)}~~~~~~~~d-2e&=&1\\[3pt]\hline -8a+11b&=&1\end{eqnarray}\)
\(a=48~,~b=35\) より、
\(48 \cdot (-8)+35 \cdot 11=1\)
\(35x+48y=1\) の形にすると、
\(35 \cdot 11+48 \cdot (-8)=1\)
\(35x+48y=3\) の整数解を求めたいので、両辺を \(3\) 倍すると、
\(35 \cdot 33+48 \cdot (-24)=3\)
よって、\(35x+48y=3\) の整数解の \(1\) つは \((x~,~y)=(33~,~-24)\) である
\(35x+48y=3\) との差をとると、
\(\begin{eqnarray}~~~~~35x+48y&=&3\\-~\big{)}~~~35 \cdot 33+48 \cdot (-24)&=&3\\[3pt]\hline 35(x-33)+48(y+24)&=&0\end{eqnarray}\)
\(35(x-33)=-48(y+24)~~~\cdots {\small [\,5\,]}\)
\(35\) と \(48\) は互いに素より、\(x-33\) は \(48\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-33&=&48k\\[3pt]~~~x&=&48k+33\end{eqnarray}\)
\({\small [\,5\,]}\) に \(x-33=48k\) を代入して、
\(\begin{eqnarray}~~~35 \cdot 48k&=&-48(y+24)\\[3pt]~~~-48(y+24)&=&48 \cdot 35k\\[3pt]~~~y+24&=&-35k\\[3pt]~~~y&=&-35k-24\end{eqnarray}\)
したがって、方程式 \(35x+48y=3\) の整数解は \(x=48k+33~,~y=-35k-24\) （\(k\) は整数）となる
\(35x+48y=3\) について、\(48\) と \(35\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}48-35 \cdot 1=13~~~\cdots {\small [\,1\,]}\\35-13 \cdot 2=9~~~\cdots {\small [\,2\,]}\\13-9 \cdot 1=4~~~\cdots {\small [\,3\,]}\\9-4 \cdot 2=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,3\,]}\) より、\(\require{enclose}\enclose{circle}{4}=\enclose{circle}{13}-\enclose{circle}{9}\) を \({\small [\,4\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{9}-(\enclose{circle}{13}-\enclose{circle}{9}) \cdot 2&=&1\\[5pt]~~~\enclose{circle}{9}-\enclose{circle}{13} \cdot 2+\enclose{circle}{9} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{9} \cdot 3-\enclose{circle}{13} \cdot 2&=&1\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\enclose{circle}{9}=\enclose{circle}{35}-\enclose{circle}{13} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{35}-\enclose{circle}{13} \cdot 2) \cdot 3-\enclose{circle}{13} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{35} \cdot 3-\enclose{circle}{13} \cdot 6-\enclose{circle}{13} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{35} \cdot 3-\enclose{circle}{13} \cdot 8&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{13}=\enclose{circle}{48}-\enclose{circle}{35}\) を代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{35} \cdot 3-(\enclose{circle}{48}-\enclose{circle}{35}) \cdot 8&=&1\\[5pt]~~~\enclose{circle}{35} \cdot 3-\enclose{circle}{48} \cdot 8+\enclose{circle}{35} \cdot 8&=&1\\[5pt]~~~\enclose{circle}{35} \cdot 11-\enclose{circle}{48} \cdot 8&=&1\end{eqnarray}\)
\(35 \cdot 11-48 \cdot 8=1\) を \(35x+48y=1\) の形にすると、
\(35 \cdot 11+48 \cdot (-8)=1\)
両辺を \(3\) 倍すると、
\(35 \cdot 33+48 \cdot (-24)=3\)
これより、\(35x+48y=3\) の整数解の \(1\) つは \((x~,~y)=(33~,~-24)\) となるので、上と同じようにして整数解を求める
\(5 \cdot 3+7 \cdot (-2)=1~~~\cdots {\small [\,1\,]}\)
\({\small [\,1\,]}\) より、
\(\begin{eqnarray}~~~~~5x+7y&=&1\\-~\big{)}~~~5 \cdot 3+7 \cdot (-2)&=&1\\[3pt]\hline 5(x-3)+7(y+2)&=&0\end{eqnarray}\)
\(5(x-3)=-7(y+2)~~~\cdots {\small [\,2\,]}\)
\(5x-5 \cdot 3=5(x-3)\)
\(7y-7 \cdot (-2)=7\left\{\,y-(-2)\,\right\}=7(y+2)\)
\(5\) と \(7\) は互いに素より、\(x-3\) は \(7\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-3&=&7k\\[3pt]~~~x&=&7k+3\end{eqnarray}\)
\({\small [\,2\,]}\) に \(x-3=7k\) を代入して、
\(\begin{eqnarray}~~~5 \cdot 7k&=&-7(y+2)\\[3pt]~~~-7(y+2)&=&7 \cdot 5k\\[3pt]~~~y+2&=&-5k\\[3pt]~~~y&=&-5k-2\end{eqnarray}\)
したがって、方程式 \(5x+7y=1\) の整数解は \(x=7k+3~,~y=-5k-2\) （\(k\) は整数）となる
方程式 \(3x-2y=4\) を満たす整数解の \(1\) つは \(x=2~,~y=1\) であるので、
\(3 \cdot 2-2 \cdot 1=4~~~\cdots {\small [\,1\,]}\)
\({\small [\,1\,]}\) より、
\(\begin{eqnarray}~~~~~3x-2y&=&4\\-~\big{)}~~~3 \cdot 2-2 \cdot 1&=&4\\[3pt]\hline 3(x-2)-2(y-1)&=&0\end{eqnarray}\)
\(3(x-2)=2(y-1)~~~\cdots {\small [\,2\,]}\)
\(3x-3 \cdot 2=3(x-2)\)
\(2y-2 \cdot 1=2(y-1)\)
\(3\) と \(2\) は互いに素より、\(x-2\) は \(2\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-2&=&2k\\[3pt]~~~x&=&2k+2\end{eqnarray}\)
\({\small [\,2\,]}\) に \(x-2=2k\) を代入して、
\(\begin{eqnarray}~~~3 \cdot 2k&=&2(y-1)\\[3pt]~~~2(y-1)&=&2 \cdot 3k\\[3pt]~~~y-1&=&3k\\[3pt]~~~y&=&3k+1\end{eqnarray}\)
したがって、方程式 \(3x-2y=4\) の整数解は \(x=2k+2~,~y=3k+1\) （\(k\) は整数）となる
\({\small (3)}~16x-23y=1\) について、\(23\) を \(16\) で割ると、
\(\begin{array}{rr}1~\\16~)~\overline{23~}\\\underline{16~}\\7~\end{array}\)
余り \(7\) より、\(16\) を \(7\) で割ると、
\(\begin{array}{rr}2~\\7~)~\overline{16~}\\\underline{14~}\\2~\end{array}\)
余り \(2\) より、\(7\) を \(2\) で割ると、
\(\begin{array}{rr}3~\\2~)~\overline{7~}\\\underline{6~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}23-16 \cdot 1=7\\16-7 \cdot 2=2\\7-2 \cdot 3=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=23~,~b=16\) 、余りをそれぞれ \(c=7~,~d=2\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-2c=d~~~\cdots {\small [\,2\,]}\\c-3d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-3)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-3b+6c=-3d\\c-3d=1\end{array}\right.\end{eqnarray}\)
左辺に \(6c+c=7c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 7\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}7a-7b=7c\\-3b+6c=-3d\\c-3d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~7a-7b&=&7c\\~~-3b+6c&=&-3d~~\\+~\big{)}~~~~~~~~c-3d&=&1\\[3pt]\hline 7a-10b&=&1\end{eqnarray}\)
\(a=23~,~b=16\) より、
\(23 \cdot 7-16 \cdot 10=1\)
\(16x-23y=1\) の形にすると、
\(16 \cdot (-10)-23 \cdot (-7)=1\)
よって、\(16x-23y=1\) の整数解の \(1\) つは \((x~,~y)=(-10~,~-7)\) である
\(16x-23y=1\) との差をとると、
\(\begin{eqnarray}~~~~~16x-23y&=&1\\-~\big{)}~~~16 \cdot (-10)-23 \cdot (-7)&=&1\\[3pt]\hline 16(x+10)-23(y+7)&=&0\end{eqnarray}\)
\(16(x+10)=23(y+7)~~~\cdots {\small [\,4\,]}\)
\(16\) と \(23\) は互いに素より、\(x+10\) は \(23\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x+10&=&23k\\[3pt]~~~x&=&23k-10\end{eqnarray}\)
\({\small [\,4\,]}\) に \(x+10=23k\) を代入して、
\(\begin{eqnarray}~~~16 \cdot 23k&=&23(y+7)\\[3pt]~~~23(y+7)&=&23 \cdot 16k\\[3pt]~~~y+7&=&16k\\[3pt]~~~y&=&16k-7\end{eqnarray}\)
したがって、方程式 \(16x-23y=1\) の整数解は \(x=23k-10~,~y=16k-7\) （\(k\) は整数）となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(16x-23y=1\) について、\(23\) と \(16\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}23-16 \cdot 1=7~~~\cdots {\small [\,1\,]}\\16-7 \cdot 2=2~~~\cdots {\small [\,2\,]}\\7-2 \cdot 3=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{2}=\enclose{circle}{16}-\enclose{circle}{7} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{7}-(\enclose{circle}{16}-\enclose{circle}{7} \cdot 2) \cdot 3&=&1\\[5pt]~~~\enclose{circle}{7}-\enclose{circle}{16} \cdot 3+\enclose{circle}{7} \cdot 6&=&1\\[5pt]~~~\enclose{circle}{7} \cdot 7-\enclose{circle}{16} \cdot 3&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{7}=\enclose{circle}{23}-\enclose{circle}{16}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{23}-\enclose{circle}{16}) \cdot 7-\enclose{circle}{16} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{23} \cdot 7-\enclose{circle}{16} \cdot 7-\enclose{circle}{16} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{23} \cdot 7-\enclose{circle}{16} \cdot 10&=&1\end{eqnarray}\)
\(23 \cdot 7-16 \cdot 10=1\) を \(16x-23y=1\) の形にすると、
\(16 \cdot (-10)-23 \cdot (-7)=1\)
これより、\(16x-23y=1\) の整数解の \(1\) つは \((x~,~y)=(-10~,~-7)\) となるので、上と同じようにして整数解を求める
\({\small (4)}~35x+48y=3\) について、まず \(35x+48y=1\) を考える。\(48\) を \(35\) で割ると、
\(\begin{array}{rr}1~\\35~)~\overline{48~}\\\underline{35~}\\13~\end{array}\)
余り \(13\) より、\(35\) を \(13\) で割ると、
\(\begin{array}{rr}2~\\13~)~\overline{35~}\\\underline{26~}\\9~\end{array}\)
余り \(9\) より、\(13\) を \(9\) で割ると、
\(\begin{array}{rr}1~\\9~)~\overline{13~}\\\underline{9~}\\4~\end{array}\)
余り \(4\) より、\(9\) を \(4\) で割ると、
\(\begin{array}{rr}2~\\4~)~\overline{9~}\\\underline{8~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}48-35 \cdot 1=13\\35-13 \cdot 2=9\\13-9 \cdot 1=4\\9-4 \cdot 2=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=48~,~b=35\) 、余りをそれぞれ \(c=13~,~d=9~,~e=4\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-2c=d~~~\cdots {\small [\,2\,]}\\c-d=e~~~\cdots {\small [\,3\,]}\\d-2e=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,4\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-e\) があらわれるので、\({\small [\,3\,]} {\, \small \times \,} (-2)\) と \({\small [\,4\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-2c+2d=-2e\\d-2e=1\end{array}\right.\end{eqnarray}\)
左辺に \(2d+d=3d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} 3\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}3b-6c=3d\\-2c+2d=-2e\\d-2e=1\end{array}\right.\end{eqnarray}\)
左辺に \(-6c-2c=-8c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} (-8)\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-8a+8b=-8c\\3b-6c=3d\\-2c+2d=-2e\\d-2e=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) 、\(d\) 、\(e\) が消去できるので、
\(\begin{eqnarray}~~~~~-8a+8b&=&-8c\\~~~~~3b-6c&=&3d\\~~-2c+2d&=&-2e~~\\+~\big{)}~~~~~~~~d-2e&=&1\\[3pt]\hline -8a+11b&=&1\end{eqnarray}\)
\(a=48~,~b=35\) より、
\(48 \cdot (-8)+35 \cdot 11=1\)
\(35x+48y=1\) の形にすると、
\(35 \cdot 11+48 \cdot (-8)=1\)
\(35x+48y=3\) の整数解を求めたいので、両辺を \(3\) 倍すると、
\(35 \cdot 33+48 \cdot (-24)=3\)
よって、\(35x+48y=3\) の整数解の \(1\) つは \((x~,~y)=(33~,~-24)\) である
\(35x+48y=3\) との差をとると、
\(\begin{eqnarray}~~~~~35x+48y&=&3\\-~\big{)}~~~35 \cdot 33+48 \cdot (-24)&=&3\\[3pt]\hline 35(x-33)+48(y+24)&=&0\end{eqnarray}\)
\(35(x-33)=-48(y+24)~~~\cdots {\small [\,5\,]}\)
\(35\) と \(48\) は互いに素より、\(x-33\) は \(48\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-33&=&48k\\[3pt]~~~x&=&48k+33\end{eqnarray}\)
\({\small [\,5\,]}\) に \(x-33=48k\) を代入して、
\(\begin{eqnarray}~~~35 \cdot 48k&=&-48(y+24)\\[3pt]~~~-48(y+24)&=&48 \cdot 35k\\[3pt]~~~y+24&=&-35k\\[3pt]~~~y&=&-35k-24\end{eqnarray}\)
したがって、方程式 \(35x+48y=3\) の整数解は \(x=48k+33~,~y=-35k-24\) （\(k\) は整数）となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(35x+48y=3\) について、\(48\) と \(35\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}48-35 \cdot 1=13~~~\cdots {\small [\,1\,]}\\35-13 \cdot 2=9~~~\cdots {\small [\,2\,]}\\13-9 \cdot 1=4~~~\cdots {\small [\,3\,]}\\9-4 \cdot 2=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,3\,]}\) より、\(\require{enclose}\enclose{circle}{4}=\enclose{circle}{13}-\enclose{circle}{9}\) を \({\small [\,4\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{9}-(\enclose{circle}{13}-\enclose{circle}{9}) \cdot 2&=&1\\[5pt]~~~\enclose{circle}{9}-\enclose{circle}{13} \cdot 2+\enclose{circle}{9} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{9} \cdot 3-\enclose{circle}{13} \cdot 2&=&1\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\enclose{circle}{9}=\enclose{circle}{35}-\enclose{circle}{13} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{35}-\enclose{circle}{13} \cdot 2) \cdot 3-\enclose{circle}{13} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{35} \cdot 3-\enclose{circle}{13} \cdot 6-\enclose{circle}{13} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{35} \cdot 3-\enclose{circle}{13} \cdot 8&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{13}=\enclose{circle}{48}-\enclose{circle}{35}\) を代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{35} \cdot 3-(\enclose{circle}{48}-\enclose{circle}{35}) \cdot 8&=&1\\[5pt]~~~\enclose{circle}{35} \cdot 3-\enclose{circle}{48} \cdot 8+\enclose{circle}{35} \cdot 8&=&1\\[5pt]~~~\enclose{circle}{35} \cdot 11-\enclose{circle}{48} \cdot 8&=&1\end{eqnarray}\)
\(35 \cdot 11-48 \cdot 8=1\) を \(35x+48y=1\) の形にすると、
\(35 \cdot 11+48 \cdot (-8)=1\)
両辺を \(3\) 倍すると、
\(35 \cdot 33+48 \cdot (-24)=3\)
これより、\(35x+48y=3\) の整数解の \(1\) つは \((x~,~y)=(33~,~-24)\) となるので、上と同じようにして整数解を求める
問題アーカイブ03
問題アーカイブ03次の方程式の整数解をすべて求めよ。
\(43x-32y=4\)
\(43x-32y=4\)
数研出版｜高等学校数学A[104-903] p.152 練習21
▼ より詳しい解説を開く
\(43x-32y=4\) について、まず \(43x-32y=1\) を考える。\(43\) を \(32\) で割ると、
\(\begin{array}{rr}1~\\32~)~\overline{43~}\\\underline{32~}\\11~\end{array}\)
余り \(11\) より、\(32\) を \(11\) で割ると、
\(\begin{array}{rr}2~\\11~)~\overline{32~}\\\underline{22~}\\10~\end{array}\)
余り \(10\) より、\(11\) を \(10\) で割ると、
\(\begin{array}{rr}1~\\10~)~\overline{11~}\\\underline{10~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}43-32 \cdot 1=11\\32-11 \cdot 2=10\\11-10 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=43~,~b=32\) 、余りをそれぞれ \(c=11~,~d=10\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-2c=d~~~\cdots {\small [\,2\,]}\\c-d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-1)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-b+2c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
左辺に \(2c+c=3c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 3\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}3a-3b=3c\\-b+2c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~3a-3b&=&3c\\~~-b+2c&=&-d~~\\+~\big{)}~~~~~~~~c-d&=&1\\[3pt]\hline 3a-4b&=&1\end{eqnarray}\)
\(a=43~,~b=32\) より、
\(43 \cdot 3-32 \cdot 4=1\)
これは \(43x-32y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(3~,~4)\) である
\(43x-32y=4\) の整数解を求めたいので、両辺を \(4\) 倍すると、
\(43 \cdot 12-32 \cdot 16=4\)
よって、\(43x-32y=4\) の整数解の \(1\) つは \((x~,~y)=(12~,~16)\) である
\(43x-32y=4\) との差をとると、
\(\begin{eqnarray}~~~~~43x-32y&=&4\\-~\big{)}~~~43 \cdot 12-32 \cdot 16&=&4\\[3pt]\hline 43(x-12)-32(y-16)&=&0\end{eqnarray}\)
\(43(x-12)=32(y-16)~~~\cdots {\small [\,4\,]}\)
\(43\) と \(32\) は互いに素より、\(x-12\) は \(32\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-12&=&32k\\[3pt]~~~x&=&32k+12\end{eqnarray}\)
\({\small [\,4\,]}\) に \(x-12=32k\) を代入して、
\(\begin{eqnarray}~~~43 \cdot 32k&=&32(y-16)\\[3pt]~~~32(y-16)&=&32 \cdot 43k\\[3pt]~~~y-16&=&43k\\[3pt]~~~y&=&43k+16\end{eqnarray}\)
したがって、方程式 \(43x-32y=4\) の整数解は \(x=32k+12~,~y=43k+16\) （\(k\) は整数）となる
\(43x-32y=4\) について、\(43\) と \(32\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}43-32 \cdot 1=11~~~\cdots {\small [\,1\,]}\\32-11 \cdot 2=10~~~\cdots {\small [\,2\,]}\\11-10 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{10}=\enclose{circle}{32}-\enclose{circle}{11} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{11}-(\enclose{circle}{32}-\enclose{circle}{11} \cdot 2) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{11}-\enclose{circle}{32}+\enclose{circle}{11} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{11} \cdot 3-\enclose{circle}{32}&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{11}=\enclose{circle}{43}-\enclose{circle}{32}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{43}-\enclose{circle}{32}) \cdot 3-\enclose{circle}{32}&=&1\\[5pt]~~~\enclose{circle}{43} \cdot 3-\enclose{circle}{32} \cdot 3-\enclose{circle}{32}&=&1\\[5pt]~~~\enclose{circle}{43} \cdot 3-\enclose{circle}{32} \cdot 4&=&1\end{eqnarray}\)
\(43 \cdot 3-32 \cdot 4=1\) は \(43x-32y=1\) の形になっているので、両辺を \(4\) 倍すると、
\(43 \cdot 12-32 \cdot 16=4\)
これより、\(43x-32y=4\) の整数解の \(1\) つは \((x~,~y)=(12~,~16)\) となるので、上と同じようにして整数解を求める
\(\begin{array}{rr}1~\\32~)~\overline{43~}\\\underline{32~}\\11~\end{array}\)
余り \(11\) より、\(32\) を \(11\) で割ると、
\(\begin{array}{rr}2~\\11~)~\overline{32~}\\\underline{22~}\\10~\end{array}\)
余り \(10\) より、\(11\) を \(10\) で割ると、
\(\begin{array}{rr}1~\\10~)~\overline{11~}\\\underline{10~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}43-32 \cdot 1=11\\32-11 \cdot 2=10\\11-10 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=43~,~b=32\) 、余りをそれぞれ \(c=11~,~d=10\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-2c=d~~~\cdots {\small [\,2\,]}\\c-d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-1)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-b+2c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
左辺に \(2c+c=3c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 3\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}3a-3b=3c\\-b+2c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~3a-3b&=&3c\\~~-b+2c&=&-d~~\\+~\big{)}~~~~~~~~c-d&=&1\\[3pt]\hline 3a-4b&=&1\end{eqnarray}\)
\(a=43~,~b=32\) より、
\(43 \cdot 3-32 \cdot 4=1\)
これは \(43x-32y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(3~,~4)\) である
\(43x-32y=4\) の整数解を求めたいので、両辺を \(4\) 倍すると、
\(43 \cdot 12-32 \cdot 16=4\)
よって、\(43x-32y=4\) の整数解の \(1\) つは \((x~,~y)=(12~,~16)\) である
\(43x-32y=4\) との差をとると、
\(\begin{eqnarray}~~~~~43x-32y&=&4\\-~\big{)}~~~43 \cdot 12-32 \cdot 16&=&4\\[3pt]\hline 43(x-12)-32(y-16)&=&0\end{eqnarray}\)
\(43(x-12)=32(y-16)~~~\cdots {\small [\,4\,]}\)
\(43\) と \(32\) は互いに素より、\(x-12\) は \(32\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-12&=&32k\\[3pt]~~~x&=&32k+12\end{eqnarray}\)
\({\small [\,4\,]}\) に \(x-12=32k\) を代入して、
\(\begin{eqnarray}~~~43 \cdot 32k&=&32(y-16)\\[3pt]~~~32(y-16)&=&32 \cdot 43k\\[3pt]~~~y-16&=&43k\\[3pt]~~~y&=&43k+16\end{eqnarray}\)
したがって、方程式 \(43x-32y=4\) の整数解は \(x=32k+12~,~y=43k+16\) （\(k\) は整数）となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(43x-32y=4\) について、\(43\) と \(32\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}43-32 \cdot 1=11~~~\cdots {\small [\,1\,]}\\32-11 \cdot 2=10~~~\cdots {\small [\,2\,]}\\11-10 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{10}=\enclose{circle}{32}-\enclose{circle}{11} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{11}-(\enclose{circle}{32}-\enclose{circle}{11} \cdot 2) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{11}-\enclose{circle}{32}+\enclose{circle}{11} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{11} \cdot 3-\enclose{circle}{32}&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{11}=\enclose{circle}{43}-\enclose{circle}{32}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{43}-\enclose{circle}{32}) \cdot 3-\enclose{circle}{32}&=&1\\[5pt]~~~\enclose{circle}{43} \cdot 3-\enclose{circle}{32} \cdot 3-\enclose{circle}{32}&=&1\\[5pt]~~~\enclose{circle}{43} \cdot 3-\enclose{circle}{32} \cdot 4&=&1\end{eqnarray}\)
\(43 \cdot 3-32 \cdot 4=1\) は \(43x-32y=1\) の形になっているので、両辺を \(4\) 倍すると、
\(43 \cdot 12-32 \cdot 16=4\)
これより、\(43x-32y=4\) の整数解の \(1\) つは \((x~,~y)=(12~,~16)\) となるので、上と同じようにして整数解を求める
問題アーカイブ04
問題アーカイブ04次の方程式の整数解をすべて求めよ。
\({\small (1)}~5x-2y=1\)
\({\small (2)}~36x+25y=2\)
\({\small (1)}~5x-2y=1\)
\({\small (2)}~36x+25y=2\)
数研出版｜高等学校数学A[104-903] p.157 問題 9
▼ より詳しい解説を開く
方程式 \(5x-2y=1\) を満たす整数解の \(1\) つは \(x=1~,~y=2\) であるので、
\(5 \cdot 1-2 \cdot 2=1~~~\cdots {\small [\,1\,]}\)
\({\small [\,1\,]}\) より、
\(\begin{eqnarray}~~~~~5x-2y&=&1\\-~\big{)}~~~5 \cdot 1-2 \cdot 2&=&1\\[3pt]\hline 5(x-1)-2(y-2)&=&0\end{eqnarray}\)
\(5(x-1)=2(y-2)~~~\cdots {\small [\,2\,]}\)
\(\begin{eqnarray}~~~x-1&=&2k\\[3pt]~~~x&=&2k+1\end{eqnarray}\)
\({\small [\,2\,]}\) に \(x-1=2k\) を代入して、
\(\begin{eqnarray}~~~5 \cdot 2k&=&2(y-2)\\[3pt]~~~2(y-2)&=&2 \cdot 5k\\[3pt]~~~y-2&=&5k\\[3pt]~~~y&=&5k+2\end{eqnarray}\)
したがって、方程式 \(5x-2y=1\) の整数解は \(x=2k+1~,~y=5k+2\) （\(k\) は整数）となる
\(\begin{array}{rr}1~\\25~)~\overline{36~}\\\underline{25~}\\11~\end{array}\)
余り \(11\) より、\(25\) を \(11\) で割ると、
\(\begin{array}{rr}2~\\11~)~\overline{25~}\\\underline{22~}\\3~\end{array}\)
余り \(3\) より、\(11\) を \(3\) で割ると、
\(\begin{array}{rr}3~\\3~)~\overline{11~}\\\underline{9~}\\2~\end{array}\)
余り \(2\) より、\(3\) を \(2\) で割ると、
\(\begin{array}{rr}1~\\2~)~\overline{3~}\\\underline{2~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}36-25 \cdot 1=11\\25-11 \cdot 2=3\\11-3 \cdot 3=2\\3-2 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=36~,~b=25\) 、余りをそれぞれ \(c=11~,~d=3~,~e=2\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-2c=d~~~\cdots {\small [\,2\,]}\\c-3d=e~~~\cdots {\small [\,3\,]}\\d-e=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,4\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-e\) があらわれるので、\({\small [\,3\,]} {\, \small \times \,} (-1)\) と \({\small [\,4\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-c+3d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
左辺に \(3d+d=4d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} 4\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}4b-8c=4d\\-c+3d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
左辺に \(-8c-c=-9c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} (-9)\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-9a+9b=-9c\\4b-8c=4d\\-c+3d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) 、\(d\) 、\(e\) が消去できるので、
\(\begin{eqnarray}~~~~~-9a+9b&=&-9c\\~~~~~4b-8c&=&4d\\~~-c+3d&=&-e~~\\+~\big{)}~~~~~~~~d-e&=&1\\[3pt]\hline -9a+13b&=&1\end{eqnarray}\)
\(a=36~,~b=25\) より、
\(36 \cdot (-9)+25 \cdot 13=1\)
これは \(36x+25y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(-9~,~13)\) である
\(36x+25y=2\) の整数解を求めたいので、両辺を \(2\) 倍すると、
\(36 \cdot (-18)+25 \cdot 26=2\)
よって、\(36x+25y=2\) の整数解の \(1\) つは \((x~,~y)=(-18~,~26)\) である
\(36x+25y=2\) との差をとると、
\(\begin{eqnarray}~~~~~36x+25y&=&2\\-~\big{)}~~~36 \cdot (-18)+25 \cdot 26&=&2\\[3pt]\hline 36(x+18)+25(y-26)&=&0\end{eqnarray}\)
\(36(x+18)=-25(y-26)~~~\cdots {\small [\,5\,]}\)
\(36\) と \(25\) は互いに素より、\(x+18\) は \(25\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x+18&=&25k\\[3pt]~~~x&=&25k-18\end{eqnarray}\)
\({\small [\,5\,]}\) に \(x+18=25k\) を代入して、
\(\begin{eqnarray}~~~36 \cdot 25k&=&-25(y-26)\\[3pt]~~~-25(y-26)&=&25 \cdot 36k\\[3pt]~~~y-26&=&-36k\\[3pt]~~~y&=&-36k+26\end{eqnarray}\)
したがって、方程式 \(36x+25y=2\) の整数解は \(x=25k-18~,~y=-36k+26\) （\(k\) は整数）となる
\(36x+25y=2\) について、\(36\) と \(25\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}36-25 \cdot 1=11~~~\cdots {\small [\,1\,]}\\25-11 \cdot 2=3~~~\cdots {\small [\,2\,]}\\11-3 \cdot 3=2~~~\cdots {\small [\,3\,]}\\3-2 \cdot 1=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,3\,]}\) より、\(\require{enclose}\enclose{circle}{2}=\enclose{circle}{11}-\enclose{circle}{3} \cdot 3\) を \({\small [\,4\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{3}-(\enclose{circle}{11}-\enclose{circle}{3} \cdot 3) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{3}-\enclose{circle}{11}+\enclose{circle}{3} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{3} \cdot 4-\enclose{circle}{11}&=&1\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\enclose{circle}{3}=\enclose{circle}{25}-\enclose{circle}{11} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{25}-\enclose{circle}{11} \cdot 2) \cdot 4-\enclose{circle}{11}&=&1\\[5pt]~~~\enclose{circle}{25} \cdot 4-\enclose{circle}{11} \cdot 8-\enclose{circle}{11}&=&1\\[5pt]~~~\enclose{circle}{25} \cdot 4-\enclose{circle}{11} \cdot 9&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{11}=\enclose{circle}{36}-\enclose{circle}{25}\) を代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{25} \cdot 4-(\enclose{circle}{36}-\enclose{circle}{25}) \cdot 9&=&1\\[5pt]~~~\enclose{circle}{25} \cdot 4-\enclose{circle}{36} \cdot 9+\enclose{circle}{25} \cdot 9&=&1\\[5pt]~~~\enclose{circle}{36} \cdot (-9)+\enclose{circle}{25} \cdot 13&=&1\end{eqnarray}\)
\(36 \cdot (-9)+25 \cdot 13=1\) は \(36x+25y=1\) の形になっているので、両辺を \(2\) 倍すると、
\(36 \cdot (-18)+25 \cdot 26=2\)
これより、\(36x+25y=2\) の整数解の \(1\) つは \((x~,~y)=(-18~,~26)\) となるので、上と同じようにして整数解を求める
\(5 \cdot 1-2 \cdot 2=1~~~\cdots {\small [\,1\,]}\)
\({\small [\,1\,]}\) より、
\(\begin{eqnarray}~~~~~5x-2y&=&1\\-~\big{)}~~~5 \cdot 1-2 \cdot 2&=&1\\[3pt]\hline 5(x-1)-2(y-2)&=&0\end{eqnarray}\)
\(5(x-1)=2(y-2)~~~\cdots {\small [\,2\,]}\)
\(5x-5 \cdot 1=5(x-1)\)
\(2y-2 \cdot 2=2(y-2)\)
\(5\) と \(2\) は互いに素より、\(x-1\) は \(2\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-1&=&2k\\[3pt]~~~x&=&2k+1\end{eqnarray}\)
\({\small [\,2\,]}\) に \(x-1=2k\) を代入して、
\(\begin{eqnarray}~~~5 \cdot 2k&=&2(y-2)\\[3pt]~~~2(y-2)&=&2 \cdot 5k\\[3pt]~~~y-2&=&5k\\[3pt]~~~y&=&5k+2\end{eqnarray}\)
したがって、方程式 \(5x-2y=1\) の整数解は \(x=2k+1~,~y=5k+2\) （\(k\) は整数）となる
\({\small (2)}~36x+25y=2\) について、まず \(36x+25y=1\) を考える。\(36\) を \(25\) で割ると、
\(\begin{array}{rr}1~\\25~)~\overline{36~}\\\underline{25~}\\11~\end{array}\)
余り \(11\) より、\(25\) を \(11\) で割ると、
\(\begin{array}{rr}2~\\11~)~\overline{25~}\\\underline{22~}\\3~\end{array}\)
余り \(3\) より、\(11\) を \(3\) で割ると、
\(\begin{array}{rr}3~\\3~)~\overline{11~}\\\underline{9~}\\2~\end{array}\)
余り \(2\) より、\(3\) を \(2\) で割ると、
\(\begin{array}{rr}1~\\2~)~\overline{3~}\\\underline{2~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}36-25 \cdot 1=11\\25-11 \cdot 2=3\\11-3 \cdot 3=2\\3-2 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=36~,~b=25\) 、余りをそれぞれ \(c=11~,~d=3~,~e=2\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-2c=d~~~\cdots {\small [\,2\,]}\\c-3d=e~~~\cdots {\small [\,3\,]}\\d-e=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,4\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-e\) があらわれるので、\({\small [\,3\,]} {\, \small \times \,} (-1)\) と \({\small [\,4\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-c+3d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
左辺に \(3d+d=4d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} 4\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}4b-8c=4d\\-c+3d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
左辺に \(-8c-c=-9c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} (-9)\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-9a+9b=-9c\\4b-8c=4d\\-c+3d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) 、\(d\) 、\(e\) が消去できるので、
\(\begin{eqnarray}~~~~~-9a+9b&=&-9c\\~~~~~4b-8c&=&4d\\~~-c+3d&=&-e~~\\+~\big{)}~~~~~~~~d-e&=&1\\[3pt]\hline -9a+13b&=&1\end{eqnarray}\)
\(a=36~,~b=25\) より、
\(36 \cdot (-9)+25 \cdot 13=1\)
これは \(36x+25y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(-9~,~13)\) である
\(36x+25y=2\) の整数解を求めたいので、両辺を \(2\) 倍すると、
\(36 \cdot (-18)+25 \cdot 26=2\)
よって、\(36x+25y=2\) の整数解の \(1\) つは \((x~,~y)=(-18~,~26)\) である
\(36x+25y=2\) との差をとると、
\(\begin{eqnarray}~~~~~36x+25y&=&2\\-~\big{)}~~~36 \cdot (-18)+25 \cdot 26&=&2\\[3pt]\hline 36(x+18)+25(y-26)&=&0\end{eqnarray}\)
\(36(x+18)=-25(y-26)~~~\cdots {\small [\,5\,]}\)
\(36\) と \(25\) は互いに素より、\(x+18\) は \(25\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x+18&=&25k\\[3pt]~~~x&=&25k-18\end{eqnarray}\)
\({\small [\,5\,]}\) に \(x+18=25k\) を代入して、
\(\begin{eqnarray}~~~36 \cdot 25k&=&-25(y-26)\\[3pt]~~~-25(y-26)&=&25 \cdot 36k\\[3pt]~~~y-26&=&-36k\\[3pt]~~~y&=&-36k+26\end{eqnarray}\)
したがって、方程式 \(36x+25y=2\) の整数解は \(x=25k-18~,~y=-36k+26\) （\(k\) は整数）となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(36x+25y=2\) について、\(36\) と \(25\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}36-25 \cdot 1=11~~~\cdots {\small [\,1\,]}\\25-11 \cdot 2=3~~~\cdots {\small [\,2\,]}\\11-3 \cdot 3=2~~~\cdots {\small [\,3\,]}\\3-2 \cdot 1=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,3\,]}\) より、\(\require{enclose}\enclose{circle}{2}=\enclose{circle}{11}-\enclose{circle}{3} \cdot 3\) を \({\small [\,4\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{3}-(\enclose{circle}{11}-\enclose{circle}{3} \cdot 3) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{3}-\enclose{circle}{11}+\enclose{circle}{3} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{3} \cdot 4-\enclose{circle}{11}&=&1\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\enclose{circle}{3}=\enclose{circle}{25}-\enclose{circle}{11} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{25}-\enclose{circle}{11} \cdot 2) \cdot 4-\enclose{circle}{11}&=&1\\[5pt]~~~\enclose{circle}{25} \cdot 4-\enclose{circle}{11} \cdot 8-\enclose{circle}{11}&=&1\\[5pt]~~~\enclose{circle}{25} \cdot 4-\enclose{circle}{11} \cdot 9&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{11}=\enclose{circle}{36}-\enclose{circle}{25}\) を代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{25} \cdot 4-(\enclose{circle}{36}-\enclose{circle}{25}) \cdot 9&=&1\\[5pt]~~~\enclose{circle}{25} \cdot 4-\enclose{circle}{36} \cdot 9+\enclose{circle}{25} \cdot 9&=&1\\[5pt]~~~\enclose{circle}{36} \cdot (-9)+\enclose{circle}{25} \cdot 13&=&1\end{eqnarray}\)
\(36 \cdot (-9)+25 \cdot 13=1\) は \(36x+25y=1\) の形になっているので、両辺を \(2\) 倍すると、
\(36 \cdot (-18)+25 \cdot 26=2\)
これより、\(36x+25y=2\) の整数解の \(1\) つは \((x~,~y)=(-18~,~26)\) となるので、上と同じようにして整数解を求める
問題アーカイブ05
問題アーカイブ05次の方程式の整数解をすべて求めよ。
\({\small (1)}~33x-14y=1\)
\({\small (2)}~30x+11y=2\)
\({\small (1)}~33x-14y=1\)
\({\small (2)}~30x+11y=2\)
数研出版｜高等学校数学A[104-903] p.177 章末問題A 7
数研出版｜新編数学A[104-904] p.166 章末問題A 6
▼ より詳しい解説を開く
\({\small (1)}~33x-14y=1\) について、\(33\) を \(14\) で割ると、
\(\begin{array}{rr}2~\\14~)~\overline{33~}\\\underline{28~}\\5~\end{array}\)
余り \(5\) より、\(14\) を \(5\) で割ると、
\(\begin{array}{rr}2~\\5~)~\overline{14~}\\\underline{10~}\\4~\end{array}\)
余り \(4\) より、\(5\) を \(4\) で割ると、
\(\begin{array}{rr}1~\\4~)~\overline{5~}\\\underline{4~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}33-14 \cdot 2=5\\14-5 \cdot 2=4\\5-4 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=33~,~b=14\) 、余りをそれぞれ \(c=5~,~d=4\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-2b=c~~~\cdots {\small [\,1\,]}\\b-2c=d~~~\cdots {\small [\,2\,]}\\c-d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-1)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-b+2c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
左辺に \(2c+c=3c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 3\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}3a-6b=3c\\-b+2c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~3a-6b&=&3c\\~~-b+2c&=&-d~~\\+~\big{)}~~~~~~~~c-d&=&1\\[3pt]\hline 3a-7b&=&1\end{eqnarray}\)
\(a=33~,~b=14\) より、
\(33 \cdot 3-14 \cdot 7=1\)
これは \(33x-14y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(3~,~7)\) である
\(33x-14y=1\) との差をとると、
\(\begin{eqnarray}~~~~~33x-14y&=&1\\-~\big{)}~~~33 \cdot 3-14 \cdot 7&=&1\\[3pt]\hline 33(x-3)-14(y-7)&=&0\end{eqnarray}\)
\(33(x-3)=14(y-7)~~~\cdots {\small [\,4\,]}\)
\(33\) と \(14\) は互いに素より、\(x-3\) は \(14\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-3&=&14k\\[3pt]~~~x&=&14k+3\end{eqnarray}\)
\({\small [\,4\,]}\) に \(x-3=14k\) を代入して、
\(\begin{eqnarray}~~~33 \cdot 14k&=&14(y-7)\\[3pt]~~~14(y-7)&=&14 \cdot 33k\\[3pt]~~~y-7&=&33k\\[3pt]~~~y&=&33k+7\end{eqnarray}\)
したがって、方程式 \(33x-14y=1\) の整数解は \(x=14k+3~,~y=33k+7\) （\(k\) は整数）となる
\(33x-14y=1\) について、\(33\) と \(14\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}33-14 \cdot 2=5~~~\cdots {\small [\,1\,]}\\14-5 \cdot 2=4~~~\cdots {\small [\,2\,]}\\5-4 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{4}=\enclose{circle}{14}-\enclose{circle}{5} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{5}-(\enclose{circle}{14}-\enclose{circle}{5} \cdot 2) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{5}-\enclose{circle}{14}+\enclose{circle}{5} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{5} \cdot 3-\enclose{circle}{14}&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{5}=\enclose{circle}{33}-\enclose{circle}{14} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{33}-\enclose{circle}{14} \cdot 2) \cdot 3-\enclose{circle}{14}&=&1\\[5pt]~~~\enclose{circle}{33} \cdot 3-\enclose{circle}{14} \cdot 6-\enclose{circle}{14}&=&1\\[5pt]~~~\enclose{circle}{33} \cdot 3-\enclose{circle}{14} \cdot 7&=&1\end{eqnarray}\)
\(33 \cdot 3-14 \cdot 7=1\) は \(33x-14y=1\) の形になっているので、
これより、\(33x-14y=1\) の整数解の \(1\) つは \((x~,~y)=(3~,~7)\) となるので、上と同じようにして整数解を求める
\(\begin{array}{rr}2~\\11~)~\overline{30~}\\\underline{22~}\\8~\end{array}\)
余り \(8\) より、\(11\) を \(8\) で割ると、
\(\begin{array}{rr}1~\\8~)~\overline{11~}\\\underline{8~}\\3~\end{array}\)
余り \(3\) より、\(8\) を \(3\) で割ると、
\(\begin{array}{rr}2~\\3~)~\overline{8~}\\\underline{6~}\\2~\end{array}\)
余り \(2\) より、\(3\) を \(2\) で割ると、
\(\begin{array}{rr}1~\\2~)~\overline{3~}\\\underline{2~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}30-11 \cdot 2=8\\11-8 \cdot 1=3\\8-3 \cdot 2=2\\3-2 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=30~,~b=11\) 、余りをそれぞれ \(c=8~,~d=3~,~e=2\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-2b=c~~~\cdots {\small [\,1\,]}\\b-c=d~~~\cdots {\small [\,2\,]}\\c-2d=e~~~\cdots {\small [\,3\,]}\\d-e=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,4\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-e\) があらわれるので、\({\small [\,3\,]} {\, \small \times \,} (-1)\) と \({\small [\,4\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
左辺に \(2d+d=3d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} 3\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}3b-3c=3d\\-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
左辺に \(-3c-c=-4c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} (-4)\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-4a+8b=-4c\\3b-3c=3d\\-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) 、\(d\) 、\(e\) が消去できるので、
\(\begin{eqnarray}~~~~~-4a+8b&=&-4c\\~~~~~3b-3c&=&3d\\~~-c+2d&=&-e~~\\+~\big{)}~~~~~~~~d-e&=&1\\[3pt]\hline -4a+11b&=&1\end{eqnarray}\)
\(a=30~,~b=11\) より、
\(30 \cdot (-4)+11 \cdot 11=1\)
これは \(30x+11y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(-4~,~11)\) である
\(30x+11y=2\) の整数解を求めたいので、両辺を \(2\) 倍すると、
\(30 \cdot (-8)+11 \cdot 22=2\)
よって、\(30x+11y=2\) の整数解の \(1\) つは \((x~,~y)=(-8~,~22)\) である
\(30x+11y=2\) との差をとると、
\(\begin{eqnarray}~~~~~30x+11y&=&2\\-~\big{)}~~~30 \cdot (-8)+11 \cdot 22&=&2\\[3pt]\hline 30(x+8)+11(y-22)&=&0\end{eqnarray}\)
\(30(x+8)=-11(y-22)~~~\cdots {\small [\,5\,]}\)
\(30\) と \(11\) は互いに素より、\(x+8\) は \(11\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x+8&=&11k\\[3pt]~~~x&=&11k-8\end{eqnarray}\)
\({\small [\,5\,]}\) に \(x+8=11k\) を代入して、
\(\begin{eqnarray}~~~30 \cdot 11k&=&-11(y-22)\\[3pt]~~~-11(y-22)&=&11 \cdot 30k\\[3pt]~~~y-22&=&-30k\\[3pt]~~~y&=&-30k+22\end{eqnarray}\)
したがって、方程式 \(30x+11y=2\) の整数解は \(x=11k-8~,~y=-30k+22\) （\(k\) は整数）となる
\(30x+11y=2\) について、\(30\) と \(11\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}30-11 \cdot 2=8~~~\cdots {\small [\,1\,]}\\11-8 \cdot 1=3~~~\cdots {\small [\,2\,]}\\8-3 \cdot 2=2~~~\cdots {\small [\,3\,]}\\3-2 \cdot 1=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,3\,]}\) より、\(\enclose{circle}{2}=\enclose{circle}{8}-\enclose{circle}{3} \cdot 2\) を \({\small [\,4\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{3}-(\enclose{circle}{8}-\enclose{circle}{3} \cdot 2) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{3}-\enclose{circle}{8}+\enclose{circle}{3} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{3} \cdot 3-\enclose{circle}{8}&=&1\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\enclose{circle}{3}=\enclose{circle}{11}-\enclose{circle}{8}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{11}-\enclose{circle}{8}) \cdot 3-\enclose{circle}{8}&=&1\\[5pt]~~~\enclose{circle}{11} \cdot 3-\enclose{circle}{8} \cdot 3-\enclose{circle}{8}&=&1\\[5pt]~~~\enclose{circle}{11} \cdot 3-\enclose{circle}{8} \cdot 4&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{8}=\enclose{circle}{30}-\enclose{circle}{11} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{11} \cdot 3-(\enclose{circle}{30}-\enclose{circle}{11} \cdot 2) \cdot 4&=&1\\[5pt]~~~\enclose{circle}{11} \cdot 3-\enclose{circle}{30} \cdot 4+\enclose{circle}{11} \cdot 8&=&1\\[5pt]~~~\enclose{circle}{30} \cdot (-4)+\enclose{circle}{11} \cdot 11&=&1\end{eqnarray}\)
\(30 \cdot (-4)+11 \cdot 11=1\) は \(30x+11y=1\) の形になっているので、両辺を \(2\) 倍すると、
\(30 \cdot (-8)+11 \cdot 22=2\)
これより、\(30x+11y=2\) の整数解の \(1\) つは \((x~,~y)=(-8~,~22)\) となるので、上と同じようにして整数解を求める
\(\begin{array}{rr}2~\\14~)~\overline{33~}\\\underline{28~}\\5~\end{array}\)
余り \(5\) より、\(14\) を \(5\) で割ると、
\(\begin{array}{rr}2~\\5~)~\overline{14~}\\\underline{10~}\\4~\end{array}\)
余り \(4\) より、\(5\) を \(4\) で割ると、
\(\begin{array}{rr}1~\\4~)~\overline{5~}\\\underline{4~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}33-14 \cdot 2=5\\14-5 \cdot 2=4\\5-4 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=33~,~b=14\) 、余りをそれぞれ \(c=5~,~d=4\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-2b=c~~~\cdots {\small [\,1\,]}\\b-2c=d~~~\cdots {\small [\,2\,]}\\c-d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-1)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-b+2c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
左辺に \(2c+c=3c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 3\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}3a-6b=3c\\-b+2c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~3a-6b&=&3c\\~~-b+2c&=&-d~~\\+~\big{)}~~~~~~~~c-d&=&1\\[3pt]\hline 3a-7b&=&1\end{eqnarray}\)
\(a=33~,~b=14\) より、
\(33 \cdot 3-14 \cdot 7=1\)
これは \(33x-14y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(3~,~7)\) である
\(33x-14y=1\) との差をとると、
\(\begin{eqnarray}~~~~~33x-14y&=&1\\-~\big{)}~~~33 \cdot 3-14 \cdot 7&=&1\\[3pt]\hline 33(x-3)-14(y-7)&=&0\end{eqnarray}\)
\(33(x-3)=14(y-7)~~~\cdots {\small [\,4\,]}\)
\(33\) と \(14\) は互いに素より、\(x-3\) は \(14\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-3&=&14k\\[3pt]~~~x&=&14k+3\end{eqnarray}\)
\({\small [\,4\,]}\) に \(x-3=14k\) を代入して、
\(\begin{eqnarray}~~~33 \cdot 14k&=&14(y-7)\\[3pt]~~~14(y-7)&=&14 \cdot 33k\\[3pt]~~~y-7&=&33k\\[3pt]~~~y&=&33k+7\end{eqnarray}\)
したがって、方程式 \(33x-14y=1\) の整数解は \(x=14k+3~,~y=33k+7\) （\(k\) は整数）となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(33x-14y=1\) について、\(33\) と \(14\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}33-14 \cdot 2=5~~~\cdots {\small [\,1\,]}\\14-5 \cdot 2=4~~~\cdots {\small [\,2\,]}\\5-4 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{4}=\enclose{circle}{14}-\enclose{circle}{5} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{5}-(\enclose{circle}{14}-\enclose{circle}{5} \cdot 2) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{5}-\enclose{circle}{14}+\enclose{circle}{5} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{5} \cdot 3-\enclose{circle}{14}&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{5}=\enclose{circle}{33}-\enclose{circle}{14} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{33}-\enclose{circle}{14} \cdot 2) \cdot 3-\enclose{circle}{14}&=&1\\[5pt]~~~\enclose{circle}{33} \cdot 3-\enclose{circle}{14} \cdot 6-\enclose{circle}{14}&=&1\\[5pt]~~~\enclose{circle}{33} \cdot 3-\enclose{circle}{14} \cdot 7&=&1\end{eqnarray}\)
\(33 \cdot 3-14 \cdot 7=1\) は \(33x-14y=1\) の形になっているので、
これより、\(33x-14y=1\) の整数解の \(1\) つは \((x~,~y)=(3~,~7)\) となるので、上と同じようにして整数解を求める
\({\small (2)}~30x+11y=2\) について、まず \(30x+11y=1\) を考える。\(30\) を \(11\) で割ると、
\(\begin{array}{rr}2~\\11~)~\overline{30~}\\\underline{22~}\\8~\end{array}\)
余り \(8\) より、\(11\) を \(8\) で割ると、
\(\begin{array}{rr}1~\\8~)~\overline{11~}\\\underline{8~}\\3~\end{array}\)
余り \(3\) より、\(8\) を \(3\) で割ると、
\(\begin{array}{rr}2~\\3~)~\overline{8~}\\\underline{6~}\\2~\end{array}\)
余り \(2\) より、\(3\) を \(2\) で割ると、
\(\begin{array}{rr}1~\\2~)~\overline{3~}\\\underline{2~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}30-11 \cdot 2=8\\11-8 \cdot 1=3\\8-3 \cdot 2=2\\3-2 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=30~,~b=11\) 、余りをそれぞれ \(c=8~,~d=3~,~e=2\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-2b=c~~~\cdots {\small [\,1\,]}\\b-c=d~~~\cdots {\small [\,2\,]}\\c-2d=e~~~\cdots {\small [\,3\,]}\\d-e=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,4\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-e\) があらわれるので、\({\small [\,3\,]} {\, \small \times \,} (-1)\) と \({\small [\,4\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
左辺に \(2d+d=3d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} 3\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}3b-3c=3d\\-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
左辺に \(-3c-c=-4c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} (-4)\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-4a+8b=-4c\\3b-3c=3d\\-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) 、\(d\) 、\(e\) が消去できるので、
\(\begin{eqnarray}~~~~~-4a+8b&=&-4c\\~~~~~3b-3c&=&3d\\~~-c+2d&=&-e~~\\+~\big{)}~~~~~~~~d-e&=&1\\[3pt]\hline -4a+11b&=&1\end{eqnarray}\)
\(a=30~,~b=11\) より、
\(30 \cdot (-4)+11 \cdot 11=1\)
これは \(30x+11y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(-4~,~11)\) である
\(30x+11y=2\) の整数解を求めたいので、両辺を \(2\) 倍すると、
\(30 \cdot (-8)+11 \cdot 22=2\)
よって、\(30x+11y=2\) の整数解の \(1\) つは \((x~,~y)=(-8~,~22)\) である
\(30x+11y=2\) との差をとると、
\(\begin{eqnarray}~~~~~30x+11y&=&2\\-~\big{)}~~~30 \cdot (-8)+11 \cdot 22&=&2\\[3pt]\hline 30(x+8)+11(y-22)&=&0\end{eqnarray}\)
\(30(x+8)=-11(y-22)~~~\cdots {\small [\,5\,]}\)
\(30\) と \(11\) は互いに素より、\(x+8\) は \(11\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x+8&=&11k\\[3pt]~~~x&=&11k-8\end{eqnarray}\)
\({\small [\,5\,]}\) に \(x+8=11k\) を代入して、
\(\begin{eqnarray}~~~30 \cdot 11k&=&-11(y-22)\\[3pt]~~~-11(y-22)&=&11 \cdot 30k\\[3pt]~~~y-22&=&-30k\\[3pt]~~~y&=&-30k+22\end{eqnarray}\)
したがって、方程式 \(30x+11y=2\) の整数解は \(x=11k-8~,~y=-30k+22\) （\(k\) は整数）となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(30x+11y=2\) について、\(30\) と \(11\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}30-11 \cdot 2=8~~~\cdots {\small [\,1\,]}\\11-8 \cdot 1=3~~~\cdots {\small [\,2\,]}\\8-3 \cdot 2=2~~~\cdots {\small [\,3\,]}\\3-2 \cdot 1=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,3\,]}\) より、\(\enclose{circle}{2}=\enclose{circle}{8}-\enclose{circle}{3} \cdot 2\) を \({\small [\,4\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{3}-(\enclose{circle}{8}-\enclose{circle}{3} \cdot 2) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{3}-\enclose{circle}{8}+\enclose{circle}{3} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{3} \cdot 3-\enclose{circle}{8}&=&1\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\enclose{circle}{3}=\enclose{circle}{11}-\enclose{circle}{8}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{11}-\enclose{circle}{8}) \cdot 3-\enclose{circle}{8}&=&1\\[5pt]~~~\enclose{circle}{11} \cdot 3-\enclose{circle}{8} \cdot 3-\enclose{circle}{8}&=&1\\[5pt]~~~\enclose{circle}{11} \cdot 3-\enclose{circle}{8} \cdot 4&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{8}=\enclose{circle}{30}-\enclose{circle}{11} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{11} \cdot 3-(\enclose{circle}{30}-\enclose{circle}{11} \cdot 2) \cdot 4&=&1\\[5pt]~~~\enclose{circle}{11} \cdot 3-\enclose{circle}{30} \cdot 4+\enclose{circle}{11} \cdot 8&=&1\\[5pt]~~~\enclose{circle}{30} \cdot (-4)+\enclose{circle}{11} \cdot 11&=&1\end{eqnarray}\)
\(30 \cdot (-4)+11 \cdot 11=1\) は \(30x+11y=1\) の形になっているので、両辺を \(2\) 倍すると、
\(30 \cdot (-8)+11 \cdot 22=2\)
これより、\(30x+11y=2\) の整数解の \(1\) つは \((x~,~y)=(-8~,~22)\) となるので、上と同じようにして整数解を求める
問題アーカイブ06
問題アーカイブ06整数 \(x~,~y\) は \(0{\small ~≦~}x{\small ~≦~}30~,~0{\small ~≦~}y{\small ~≦~}30\) の範囲にあるとする。このとき、方程式 \(24x-19y=1\) の整数解をすべて求めよ。
数研出版｜高等学校数学A[104-903] p.178 章末問題B 16
▼ より詳しい解説を開く
\(24x-19y=1\) について、\(24\) を \(19\) で割ると、
\(\begin{array}{rr}1~\\19~)~\overline{24~}\\\underline{19~}\\5~\end{array}\)
余り \(5\) より、\(19\) を \(5\) で割ると、
\(\begin{array}{rr}3~\\5~)~\overline{19~}\\\underline{15~}\\4~\end{array}\)
余り \(4\) より、\(5\) を \(4\) で割ると、
\(\begin{array}{rr}1~\\4~)~\overline{5~}\\\underline{4~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}24-19 \cdot 1=5\\19-5 \cdot 3=4\\5-4 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=24~,~b=19\) 、余りをそれぞれ \(c=5~,~d=4\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-3c=d~~~\cdots {\small [\,2\,]}\\c-d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-1)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-b+3c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
左辺に \(3c+c=4c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 4\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}4a-4b=4c\\-b+3c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~4a-4b&=&4c\\~~-b+3c&=&-d~~\\+~\big{)}~~~~~~~~c-d&=&1\\[3pt]\hline 4a-5b&=&1\end{eqnarray}\)
\(a=24~,~b=19\) より、
\(24 \cdot 4-19 \cdot 5=1\)
これは \(24x-19y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(4~,~5)\) である
\(24x-19y=1\) との差をとると、
\(\begin{eqnarray}~~~~~24x-19y&=&1\\-~\big{)}~~~24 \cdot 4-19 \cdot 5&=&1\\[3pt]\hline 24(x-4)-19(y-5)&=&0\end{eqnarray}\)
\(24(x-4)=19(y-5)~~~\cdots {\small [\,4\,]}\)
\(24\) と \(19\) は互いに素より、\(x-4\) は \(19\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-4&=&19k\\[3pt]~~~x&=&19k+4\end{eqnarray}\)
\({\small [\,4\,]}\) に \(x-4=19k\) を代入して、
\(\begin{eqnarray}~~~24 \cdot 19k&=&19(y-5)\\[3pt]~~~19(y-5)&=&19 \cdot 24k\\[3pt]~~~y-5&=&24k\\[3pt]~~~y&=&24k+5\end{eqnarray}\)
よって、方程式 \(24x-19y=1\) の整数解は \(x=19k+4~,~y=24k+5\) （\(k\) は整数）となる
次に、\(0{\small ~≦~}x{\small ~≦~}30~,~0{\small ~≦~}y{\small ~≦~}30\) の範囲にある解を求める
\(0{\small ~≦~}x{\small ~≦~}30\) より、
\(\begin{eqnarray}~~~0&{\small ~≦~}&19k+4{\small ~≦~}30\\[3pt]~~~-4&{\small ~≦~}&19k{\small ~≦~}26\\[5pt]~~~-\displaystyle \frac{\,4\,}{\,19\,}&{\small ~≦~}&k{\small ~≦~}\displaystyle \frac{\,26\,}{\,19\,}\end{eqnarray}\)
\(k\) は整数より、
\(k=0~,~1\)
\(x=4~,~y=5\)
\(k=1\) のとき、
\(x=23~,~y=29\)
したがって、求める整数解は \((x~,~y)=(4~,~5)~,~(23~,~29)\) となる
\(24x-19y=1\) について、\(24\) と \(19\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}24-19 \cdot 1=5~~~\cdots {\small [\,1\,]}\\19-5 \cdot 3=4~~~\cdots {\small [\,2\,]}\\5-4 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{4}=\enclose{circle}{19}-\enclose{circle}{5} \cdot 3\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{5}-(\enclose{circle}{19}-\enclose{circle}{5} \cdot 3) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{5}-\enclose{circle}{19}+\enclose{circle}{5} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{5} \cdot 4-\enclose{circle}{19}&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{5}=\enclose{circle}{24}-\enclose{circle}{19}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{24}-\enclose{circle}{19}) \cdot 4-\enclose{circle}{19}&=&1\\[5pt]~~~\enclose{circle}{24} \cdot 4-\enclose{circle}{19} \cdot 4-\enclose{circle}{19}&=&1\\[5pt]~~~\enclose{circle}{24} \cdot 4-\enclose{circle}{19} \cdot 5&=&1\end{eqnarray}\)
\(24 \cdot 4-19 \cdot 5=1\) は \(24x-19y=1\) の形になっているので、
これより、\(24x-19y=1\) の整数解の \(1\) つは \((x~,~y)=(4~,~5)\) となるので、上と同じようにして整数解を求める
\(\begin{array}{rr}1~\\19~)~\overline{24~}\\\underline{19~}\\5~\end{array}\)
余り \(5\) より、\(19\) を \(5\) で割ると、
\(\begin{array}{rr}3~\\5~)~\overline{19~}\\\underline{15~}\\4~\end{array}\)
余り \(4\) より、\(5\) を \(4\) で割ると、
\(\begin{array}{rr}1~\\4~)~\overline{5~}\\\underline{4~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}24-19 \cdot 1=5\\19-5 \cdot 3=4\\5-4 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=24~,~b=19\) 、余りをそれぞれ \(c=5~,~d=4\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-3c=d~~~\cdots {\small [\,2\,]}\\c-d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-1)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-b+3c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
左辺に \(3c+c=4c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 4\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}4a-4b=4c\\-b+3c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~4a-4b&=&4c\\~~-b+3c&=&-d~~\\+~\big{)}~~~~~~~~c-d&=&1\\[3pt]\hline 4a-5b&=&1\end{eqnarray}\)
\(a=24~,~b=19\) より、
\(24 \cdot 4-19 \cdot 5=1\)
これは \(24x-19y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(4~,~5)\) である
\(24x-19y=1\) との差をとると、
\(\begin{eqnarray}~~~~~24x-19y&=&1\\-~\big{)}~~~24 \cdot 4-19 \cdot 5&=&1\\[3pt]\hline 24(x-4)-19(y-5)&=&0\end{eqnarray}\)
\(24(x-4)=19(y-5)~~~\cdots {\small [\,4\,]}\)
\(24\) と \(19\) は互いに素より、\(x-4\) は \(19\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-4&=&19k\\[3pt]~~~x&=&19k+4\end{eqnarray}\)
\({\small [\,4\,]}\) に \(x-4=19k\) を代入して、
\(\begin{eqnarray}~~~24 \cdot 19k&=&19(y-5)\\[3pt]~~~19(y-5)&=&19 \cdot 24k\\[3pt]~~~y-5&=&24k\\[3pt]~~~y&=&24k+5\end{eqnarray}\)
よって、方程式 \(24x-19y=1\) の整数解は \(x=19k+4~,~y=24k+5\) （\(k\) は整数）となる
次に、\(0{\small ~≦~}x{\small ~≦~}30~,~0{\small ~≦~}y{\small ~≦~}30\) の範囲にある解を求める
\(0{\small ~≦~}x{\small ~≦~}30\) より、
\(\begin{eqnarray}~~~0&{\small ~≦~}&19k+4{\small ~≦~}30\\[3pt]~~~-4&{\small ~≦~}&19k{\small ~≦~}26\\[5pt]~~~-\displaystyle \frac{\,4\,}{\,19\,}&{\small ~≦~}&k{\small ~≦~}\displaystyle \frac{\,26\,}{\,19\,}\end{eqnarray}\)
\(k\) は整数より、
\(k=0~,~1\)
\(0{\small ~≦~}y{\small ~≦~}30\) からも、\(0{\small ~≦~}24k+5{\small ~≦~}30\) より \(-\displaystyle \frac{\,5\,}{\,24\,}{\small ~≦~}k{\small ~≦~}\displaystyle \frac{\,25\,}{\,24\,}\) となり、同じく \(k=0~,~1\) が得られる。
\(k=0\) のとき、
\(x=4~,~y=5\)
\(k=1\) のとき、
\(x=23~,~y=29\)
したがって、求める整数解は \((x~,~y)=(4~,~5)~,~(23~,~29)\) となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(24x-19y=1\) について、\(24\) と \(19\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}24-19 \cdot 1=5~~~\cdots {\small [\,1\,]}\\19-5 \cdot 3=4~~~\cdots {\small [\,2\,]}\\5-4 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{4}=\enclose{circle}{19}-\enclose{circle}{5} \cdot 3\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{5}-(\enclose{circle}{19}-\enclose{circle}{5} \cdot 3) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{5}-\enclose{circle}{19}+\enclose{circle}{5} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{5} \cdot 4-\enclose{circle}{19}&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{5}=\enclose{circle}{24}-\enclose{circle}{19}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{24}-\enclose{circle}{19}) \cdot 4-\enclose{circle}{19}&=&1\\[5pt]~~~\enclose{circle}{24} \cdot 4-\enclose{circle}{19} \cdot 4-\enclose{circle}{19}&=&1\\[5pt]~~~\enclose{circle}{24} \cdot 4-\enclose{circle}{19} \cdot 5&=&1\end{eqnarray}\)
\(24 \cdot 4-19 \cdot 5=1\) は \(24x-19y=1\) の形になっているので、
これより、\(24x-19y=1\) の整数解の \(1\) つは \((x~,~y)=(4~,~5)\) となるので、上と同じようにして整数解を求める
問題アーカイブ07
問題アーカイブ07次の方程式の整数解をすべて求めよ。
\(43x+32y=4\)
\(43x+32y=4\)
数研出版｜新編数学A[104-904] p.142 練習24
▼ より詳しい解説を開く
\(43x+32y=4\) について、まず \(43x+32y=1\) を考える。\(43\) を \(32\) で割ると、
\(\begin{array}{rr}1~\\32~)~\overline{43~}\\\underline{32~}\\11~\end{array}\)
余り \(11\) より、\(32\) を \(11\) で割ると、
\(\begin{array}{rr}2~\\11~)~\overline{32~}\\\underline{22~}\\10~\end{array}\)
余り \(10\) より、\(11\) を \(10\) で割ると、
\(\begin{array}{rr}1~\\10~)~\overline{11~}\\\underline{10~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}43-32 \cdot 1=11\\32-11 \cdot 2=10\\11-10 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=43~,~b=32\) 、余りをそれぞれ \(c=11~,~d=10\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-2c=d~~~\cdots {\small [\,2\,]}\\c-d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-1)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-b+2c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
左辺に \(2c+c=3c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 3\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}3a-3b=3c\\-b+2c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~3a-3b&=&3c\\~~-b+2c&=&-d~~\\+~\big{)}~~~~~~~~c-d&=&1\\[3pt]\hline 3a-4b&=&1\end{eqnarray}\)
\(a=43~,~b=32\) より、
\(43 \cdot 3-32 \cdot 4=1\)
\(43x+32y=1\) の形にすると、
\(43 \cdot 3+32 \cdot (-4)=1\)
よって、\(43x+32y=1\) の整数解の \(1\) つは \((x~,~y)=(3~,~-4)\) である
\(43x+32y=4\) の整数解を求めたいので、両辺を \(4\) 倍すると、
\(43 \cdot 12+32 \cdot (-16)=4\)
よって、\(43x+32y=4\) の整数解の \(1\) つは \((x~,~y)=(12~,~-16)\) である
\(43x+32y=4\) との差をとると、
\(\begin{eqnarray}~~~~~43x+32y&=&4\\-~\big{)}~~~43 \cdot 12+32 \cdot (-16)&=&4\\[3pt]\hline 43(x-12)+32(y+16)&=&0\end{eqnarray}\)
\(43(x-12)=-32(y+16)~~~\cdots {\small [\,4\,]}\)
\(43\) と \(32\) は互いに素より、\(x-12\) は \(32\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-12&=&32k\\[3pt]~~~x&=&32k+12\end{eqnarray}\)
\({\small [\,4\,]}\) に \(x-12=32k\) を代入して、
\(\begin{eqnarray}~~~43 \cdot 32k&=&-32(y+16)\\[3pt]~~~-32(y+16)&=&32 \cdot 43k\\[3pt]~~~y+16&=&-43k\\[3pt]~~~y&=&-43k-16\end{eqnarray}\)
したがって、方程式 \(43x+32y=4\) の整数解は \(x=32k+12~,~y=-43k-16\) （\(k\) は整数）となる
\(43x+32y=4\) について、\(43\) と \(32\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}43-32 \cdot 1=11~~~\cdots {\small [\,1\,]}\\32-11 \cdot 2=10~~~\cdots {\small [\,2\,]}\\11-10 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{10}=\enclose{circle}{32}-\enclose{circle}{11} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{11}-(\enclose{circle}{32}-\enclose{circle}{11} \cdot 2) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{11}-\enclose{circle}{32}+\enclose{circle}{11} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{11} \cdot 3-\enclose{circle}{32}&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{11}=\enclose{circle}{43}-\enclose{circle}{32}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{43}-\enclose{circle}{32}) \cdot 3-\enclose{circle}{32}&=&1\\[5pt]~~~\enclose{circle}{43} \cdot 3-\enclose{circle}{32} \cdot 3-\enclose{circle}{32}&=&1\\[5pt]~~~\enclose{circle}{43} \cdot 3-\enclose{circle}{32} \cdot 4&=&1\end{eqnarray}\)
\(43 \cdot 3-32 \cdot 4=1\) を \(43x+32y=1\) の形にすると、
\(43 \cdot 3+32 \cdot (-4)=1\)
両辺を \(4\) 倍すると、
\(43 \cdot 12+32 \cdot (-16)=4\)
これより、\(43x+32y=4\) の整数解の \(1\) つは \((x~,~y)=(12~,~-16)\) となるので、上と同じようにして整数解を求める
\(\begin{array}{rr}1~\\32~)~\overline{43~}\\\underline{32~}\\11~\end{array}\)
余り \(11\) より、\(32\) を \(11\) で割ると、
\(\begin{array}{rr}2~\\11~)~\overline{32~}\\\underline{22~}\\10~\end{array}\)
余り \(10\) より、\(11\) を \(10\) で割ると、
\(\begin{array}{rr}1~\\10~)~\overline{11~}\\\underline{10~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}43-32 \cdot 1=11\\32-11 \cdot 2=10\\11-10 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=43~,~b=32\) 、余りをそれぞれ \(c=11~,~d=10\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-2c=d~~~\cdots {\small [\,2\,]}\\c-d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-1)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-b+2c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
左辺に \(2c+c=3c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 3\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}3a-3b=3c\\-b+2c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~3a-3b&=&3c\\~~-b+2c&=&-d~~\\+~\big{)}~~~~~~~~c-d&=&1\\[3pt]\hline 3a-4b&=&1\end{eqnarray}\)
\(a=43~,~b=32\) より、
\(43 \cdot 3-32 \cdot 4=1\)
\(43x+32y=1\) の形にすると、
\(43 \cdot 3+32 \cdot (-4)=1\)
よって、\(43x+32y=1\) の整数解の \(1\) つは \((x~,~y)=(3~,~-4)\) である
\(43x+32y=4\) の整数解を求めたいので、両辺を \(4\) 倍すると、
\(43 \cdot 12+32 \cdot (-16)=4\)
よって、\(43x+32y=4\) の整数解の \(1\) つは \((x~,~y)=(12~,~-16)\) である
\(43x+32y=4\) との差をとると、
\(\begin{eqnarray}~~~~~43x+32y&=&4\\-~\big{)}~~~43 \cdot 12+32 \cdot (-16)&=&4\\[3pt]\hline 43(x-12)+32(y+16)&=&0\end{eqnarray}\)
\(43(x-12)=-32(y+16)~~~\cdots {\small [\,4\,]}\)
\(43\) と \(32\) は互いに素より、\(x-12\) は \(32\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-12&=&32k\\[3pt]~~~x&=&32k+12\end{eqnarray}\)
\({\small [\,4\,]}\) に \(x-12=32k\) を代入して、
\(\begin{eqnarray}~~~43 \cdot 32k&=&-32(y+16)\\[3pt]~~~-32(y+16)&=&32 \cdot 43k\\[3pt]~~~y+16&=&-43k\\[3pt]~~~y&=&-43k-16\end{eqnarray}\)
したがって、方程式 \(43x+32y=4\) の整数解は \(x=32k+12~,~y=-43k-16\) （\(k\) は整数）となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(43x+32y=4\) について、\(43\) と \(32\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}43-32 \cdot 1=11~~~\cdots {\small [\,1\,]}\\32-11 \cdot 2=10~~~\cdots {\small [\,2\,]}\\11-10 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{10}=\enclose{circle}{32}-\enclose{circle}{11} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{11}-(\enclose{circle}{32}-\enclose{circle}{11} \cdot 2) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{11}-\enclose{circle}{32}+\enclose{circle}{11} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{11} \cdot 3-\enclose{circle}{32}&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{11}=\enclose{circle}{43}-\enclose{circle}{32}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{43}-\enclose{circle}{32}) \cdot 3-\enclose{circle}{32}&=&1\\[5pt]~~~\enclose{circle}{43} \cdot 3-\enclose{circle}{32} \cdot 3-\enclose{circle}{32}&=&1\\[5pt]~~~\enclose{circle}{43} \cdot 3-\enclose{circle}{32} \cdot 4&=&1\end{eqnarray}\)
\(43 \cdot 3-32 \cdot 4=1\) を \(43x+32y=1\) の形にすると、
\(43 \cdot 3+32 \cdot (-4)=1\)
両辺を \(4\) 倍すると、
\(43 \cdot 12+32 \cdot (-16)=4\)
これより、\(43x+32y=4\) の整数解の \(1\) つは \((x~,~y)=(12~,~-16)\) となるので、上と同じようにして整数解を求める
問題アーカイブ08
問題アーカイブ08次の方程式の整数解をすべて求めよ。
\(33x-19y=2\)
\(33x-19y=2\)
数研出版｜新編数学A[104-904] p.147 補充問題 4
▼ より詳しい解説を開く
\(33x-19y=2\) について、まず \(33x-19y=1\) を考える。\(33\) を \(19\) で割ると、
\(\begin{array}{rr}1~\\19~)~\overline{33~}\\\underline{19~}\\14~\end{array}\)
余り \(14\) より、\(19\) を \(14\) で割ると、
\(\begin{array}{rr}1~\\14~)~\overline{19~}\\\underline{14~}\\5~\end{array}\)
余り \(5\) より、\(14\) を \(5\) で割ると、
\(\begin{array}{rr}2~\\5~)~\overline{14~}\\\underline{10~}\\4~\end{array}\)
余り \(4\) より、\(5\) を \(4\) で割ると、
\(\begin{array}{rr}1~\\4~)~\overline{5~}\\\underline{4~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}33-19 \cdot 1=14\\19-14 \cdot 1=5\\14-5 \cdot 2=4\\5-4 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=33~,~b=19\) 、余りをそれぞれ \(c=14~,~d=5~,~e=4\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-c=d~~~\cdots {\small [\,2\,]}\\c-2d=e~~~\cdots {\small [\,3\,]}\\d-e=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,4\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-e\) があらわれるので、\({\small [\,3\,]} {\, \small \times \,} (-1)\) と \({\small [\,4\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
左辺に \(2d+d=3d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} 3\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}3b-3c=3d\\-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
左辺に \(-3c-c=-4c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} (-4)\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-4a+4b=-4c\\3b-3c=3d\\-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) 、\(d\) 、\(e\) が消去できるので、
\(\begin{eqnarray}~~~~~-4a+4b&=&-4c\\~~~~~3b-3c&=&3d\\~~-c+2d&=&-e~~\\+~\big{)}~~~~~~~~d-e&=&1\\[3pt]\hline -4a+7b&=&1\end{eqnarray}\)
\(a=33~,~b=19\) より、
\(33 \cdot (-4)+19 \cdot 7=1\)
\(33x-19y=1\) の形にすると、
\(33 \cdot (-4)-19 \cdot (-7)=1\)
よって、\(33x-19y=1\) の整数解の \(1\) つは \((x~,~y)=(-4~,~-7)\) である
\(33x-19y=2\) の整数解を求めたいので、両辺を \(2\) 倍すると、
\(33 \cdot (-8)-19 \cdot (-14)=2\)
よって、\(33x-19y=2\) の整数解の \(1\) つは \((x~,~y)=(-8~,~-14)\) である
\(33x-19y=2\) との差をとると、
\(\begin{eqnarray}~~~~~33x-19y&=&2\\-~\big{)}~~~33 \cdot (-8)-19 \cdot (-14)&=&2\\[3pt]\hline 33(x+8)-19(y+14)&=&0\end{eqnarray}\)
\(33(x+8)=19(y+14)~~~\cdots {\small [\,5\,]}\)
\(33\) と \(19\) は互いに素より、\(x+8\) は \(19\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x+8&=&19k\\[3pt]~~~x&=&19k-8\end{eqnarray}\)
\({\small [\,5\,]}\) に \(x+8=19k\) を代入して、
\(\begin{eqnarray}~~~33 \cdot 19k&=&19(y+14)\\[3pt]~~~19(y+14)&=&19 \cdot 33k\\[3pt]~~~y+14&=&33k\\[3pt]~~~y&=&33k-14\end{eqnarray}\)
したがって、方程式 \(33x-19y=2\) の整数解は \(x=19k-8~,~y=33k-14\) （\(k\) は整数）となる
\(33x-19y=2\) について、\(33\) と \(19\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}33-19 \cdot 1=14~~~\cdots {\small [\,1\,]}\\19-14 \cdot 1=5~~~\cdots {\small [\,2\,]}\\14-5 \cdot 2=4~~~\cdots {\small [\,3\,]}\\5-4 \cdot 1=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,3\,]}\) より、\(\require{enclose}\enclose{circle}{4}=\enclose{circle}{14}-\enclose{circle}{5} \cdot 2\) を \({\small [\,4\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{5}-(\enclose{circle}{14}-\enclose{circle}{5} \cdot 2) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{5}-\enclose{circle}{14}+\enclose{circle}{5} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{5} \cdot 3-\enclose{circle}{14}&=&1\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\enclose{circle}{5}=\enclose{circle}{19}-\enclose{circle}{14}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{19}-\enclose{circle}{14}) \cdot 3-\enclose{circle}{14}&=&1\\[5pt]~~~\enclose{circle}{19} \cdot 3-\enclose{circle}{14} \cdot 3-\enclose{circle}{14}&=&1\\[5pt]~~~\enclose{circle}{19} \cdot 3-\enclose{circle}{14} \cdot 4&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{14}=\enclose{circle}{33}-\enclose{circle}{19}\) を代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{19} \cdot 3-(\enclose{circle}{33}-\enclose{circle}{19}) \cdot 4&=&1\\[5pt]~~~\enclose{circle}{19} \cdot 3-\enclose{circle}{33} \cdot 4+\enclose{circle}{19} \cdot 4&=&1\\[5pt]~~~\enclose{circle}{33} \cdot (-4)+\enclose{circle}{19} \cdot 7&=&1\end{eqnarray}\)
\(33 \cdot (-4)+19 \cdot 7=1\) を \(33x-19y=1\) の形にすると、
\(33 \cdot (-4)-19 \cdot (-7)=1\)
両辺を \(2\) 倍すると、
\(33 \cdot (-8)-19 \cdot (-14)=2\)
これより、\(33x-19y=2\) の整数解の \(1\) つは \((x~,~y)=(-8~,~-14)\) となるので、上と同じようにして整数解を求める
\(\begin{array}{rr}1~\\19~)~\overline{33~}\\\underline{19~}\\14~\end{array}\)
余り \(14\) より、\(19\) を \(14\) で割ると、
\(\begin{array}{rr}1~\\14~)~\overline{19~}\\\underline{14~}\\5~\end{array}\)
余り \(5\) より、\(14\) を \(5\) で割ると、
\(\begin{array}{rr}2~\\5~)~\overline{14~}\\\underline{10~}\\4~\end{array}\)
余り \(4\) より、\(5\) を \(4\) で割ると、
\(\begin{array}{rr}1~\\4~)~\overline{5~}\\\underline{4~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}33-19 \cdot 1=14\\19-14 \cdot 1=5\\14-5 \cdot 2=4\\5-4 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=33~,~b=19\) 、余りをそれぞれ \(c=14~,~d=5~,~e=4\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-c=d~~~\cdots {\small [\,2\,]}\\c-2d=e~~~\cdots {\small [\,3\,]}\\d-e=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,4\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-e\) があらわれるので、\({\small [\,3\,]} {\, \small \times \,} (-1)\) と \({\small [\,4\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
左辺に \(2d+d=3d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} 3\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}3b-3c=3d\\-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
左辺に \(-3c-c=-4c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} (-4)\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-4a+4b=-4c\\3b-3c=3d\\-c+2d=-e\\d-e=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) 、\(d\) 、\(e\) が消去できるので、
\(\begin{eqnarray}~~~~~-4a+4b&=&-4c\\~~~~~3b-3c&=&3d\\~~-c+2d&=&-e~~\\+~\big{)}~~~~~~~~d-e&=&1\\[3pt]\hline -4a+7b&=&1\end{eqnarray}\)
\(a=33~,~b=19\) より、
\(33 \cdot (-4)+19 \cdot 7=1\)
\(33x-19y=1\) の形にすると、
\(33 \cdot (-4)-19 \cdot (-7)=1\)
よって、\(33x-19y=1\) の整数解の \(1\) つは \((x~,~y)=(-4~,~-7)\) である
\(33x-19y=2\) の整数解を求めたいので、両辺を \(2\) 倍すると、
\(33 \cdot (-8)-19 \cdot (-14)=2\)
よって、\(33x-19y=2\) の整数解の \(1\) つは \((x~,~y)=(-8~,~-14)\) である
\(33x-19y=2\) との差をとると、
\(\begin{eqnarray}~~~~~33x-19y&=&2\\-~\big{)}~~~33 \cdot (-8)-19 \cdot (-14)&=&2\\[3pt]\hline 33(x+8)-19(y+14)&=&0\end{eqnarray}\)
\(33(x+8)=19(y+14)~~~\cdots {\small [\,5\,]}\)
\(33\) と \(19\) は互いに素より、\(x+8\) は \(19\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x+8&=&19k\\[3pt]~~~x&=&19k-8\end{eqnarray}\)
\({\small [\,5\,]}\) に \(x+8=19k\) を代入して、
\(\begin{eqnarray}~~~33 \cdot 19k&=&19(y+14)\\[3pt]~~~19(y+14)&=&19 \cdot 33k\\[3pt]~~~y+14&=&33k\\[3pt]~~~y&=&33k-14\end{eqnarray}\)
したがって、方程式 \(33x-19y=2\) の整数解は \(x=19k-8~,~y=33k-14\) （\(k\) は整数）となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(33x-19y=2\) について、\(33\) と \(19\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}33-19 \cdot 1=14~~~\cdots {\small [\,1\,]}\\19-14 \cdot 1=5~~~\cdots {\small [\,2\,]}\\14-5 \cdot 2=4~~~\cdots {\small [\,3\,]}\\5-4 \cdot 1=1~~~\cdots {\small [\,4\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,3\,]}\) より、\(\require{enclose}\enclose{circle}{4}=\enclose{circle}{14}-\enclose{circle}{5} \cdot 2\) を \({\small [\,4\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{5}-(\enclose{circle}{14}-\enclose{circle}{5} \cdot 2) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{5}-\enclose{circle}{14}+\enclose{circle}{5} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{5} \cdot 3-\enclose{circle}{14}&=&1\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\enclose{circle}{5}=\enclose{circle}{19}-\enclose{circle}{14}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{19}-\enclose{circle}{14}) \cdot 3-\enclose{circle}{14}&=&1\\[5pt]~~~\enclose{circle}{19} \cdot 3-\enclose{circle}{14} \cdot 3-\enclose{circle}{14}&=&1\\[5pt]~~~\enclose{circle}{19} \cdot 3-\enclose{circle}{14} \cdot 4&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{14}=\enclose{circle}{33}-\enclose{circle}{19}\) を代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{19} \cdot 3-(\enclose{circle}{33}-\enclose{circle}{19}) \cdot 4&=&1\\[5pt]~~~\enclose{circle}{19} \cdot 3-\enclose{circle}{33} \cdot 4+\enclose{circle}{19} \cdot 4&=&1\\[5pt]~~~\enclose{circle}{33} \cdot (-4)+\enclose{circle}{19} \cdot 7&=&1\end{eqnarray}\)
\(33 \cdot (-4)+19 \cdot 7=1\) を \(33x-19y=1\) の形にすると、
\(33 \cdot (-4)-19 \cdot (-7)=1\)
両辺を \(2\) 倍すると、
\(33 \cdot (-8)-19 \cdot (-14)=2\)
これより、\(33x-19y=2\) の整数解の \(1\) つは \((x~,~y)=(-8~,~-14)\) となるので、上と同じようにして整数解を求める
問題アーカイブ09
問題アーカイブ09次の \(1\) 次不定方程式のすべての整数解を求めよ。
\({\small (1)}~13x-5y=2\)
\({\small (2)}~93x+40y=1\)
\({\small (1)}~13x-5y=2\)
\({\small (2)}~93x+40y=1\)
東京書籍｜Advanced数学A[002-901] p.142 問題 6
▼ より詳しい解説を開く
\({\small (1)}~13x-5y=2\) について、まず \(13x-5y=1\) を考える。\(13\) を \(5\) で割ると、
\(\begin{array}{rr}2~\\5~)~\overline{13~}\\\underline{10~}\\3~\end{array}\)
余り \(3\) より、\(5\) を \(3\) で割ると、
\(\begin{array}{rr}1~\\3~)~\overline{5~}\\\underline{3~}\\2~\end{array}\)
余り \(2\) より、\(3\) を \(2\) で割ると、
\(\begin{array}{rr}1~\\2~)~\overline{3~}\\\underline{2~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}13-5 \cdot 2=3\\5-3 \cdot 1=2\\3-2 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=13~,~b=5\) 、余りをそれぞれ \(c=3~,~d=2\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-2b=c~~~\cdots {\small [\,1\,]}\\b-c=d~~~\cdots {\small [\,2\,]}\\c-d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-1)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-b+c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
左辺に \(c+c=2c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 2\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}2a-4b=2c\\-b+c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~2a-4b&=&2c\\~~-b+c&=&-d~~\\+~\big{)}~~~~~~~~c-d&=&1\\[3pt]\hline 2a-5b&=&1\end{eqnarray}\)
\(a=13~,~b=5\) より、
\(13 \cdot 2-5 \cdot 5=1\)
これは \(13x-5y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(2~,~5)\) である
\(13x-5y=2\) の整数解を求めたいので、両辺を \(2\) 倍すると、
\(13 \cdot 4-5 \cdot 10=2\)
よって、\(13x-5y=2\) の整数解の \(1\) つは \((x~,~y)=(4~,~10)\) である
\(13x-5y=2\) との差をとると、
\(\begin{eqnarray}~~~~~13x-5y&=&2\\-~\big{)}~~~13 \cdot 4-5 \cdot 10&=&2\\[3pt]\hline 13(x-4)-5(y-10)&=&0\end{eqnarray}\)
\(13(x-4)=5(y-10)~~~\cdots {\small [\,4\,]}\)
\(13\) と \(5\) は互いに素より、\(x-4\) は \(5\) の倍数となるので、整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-4&=&5k\\[3pt]~~~x&=&5k+4\end{eqnarray}\)
\({\small [\,4\,]}\) に \(x-4=5k\) を代入して、
\(\begin{eqnarray}~~~13 \cdot 5k&=&5(y-10)\\[3pt]~~~5(y-10)&=&5 \cdot 13k\\[3pt]~~~y-10&=&13k\\[3pt]~~~y&=&13k+10\end{eqnarray}\)
したがって、方程式 \(13x-5y=2\) の整数解は \(x=5k+4~,~y=13k+10\) （\(k\) は整数）となる
\(13x-5y=2\) について、\(13\) と \(5\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}13-5 \cdot 2=3~~~\cdots {\small [\,1\,]}\\5-3 \cdot 1=2~~~\cdots {\small [\,2\,]}\\3-2 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{2}=\enclose{circle}{5}-\enclose{circle}{3}\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{3}-(\enclose{circle}{5}-\enclose{circle}{3})&=&1\\[5pt]~~~\enclose{circle}{3}-\enclose{circle}{5}+\enclose{circle}{3}&=&1\\[5pt]~~~\enclose{circle}{3} \cdot 2-\enclose{circle}{5}&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{3}=\enclose{circle}{13}-\enclose{circle}{5} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{13}-\enclose{circle}{5} \cdot 2) \cdot 2-\enclose{circle}{5}&=&1\\[5pt]~~~\enclose{circle}{13} \cdot 2-\enclose{circle}{5} \cdot 4-\enclose{circle}{5}&=&1\\[5pt]~~~\enclose{circle}{13} \cdot 2-\enclose{circle}{5} \cdot 5&=&1\end{eqnarray}\)
\(13 \cdot 2-5 \cdot 5=1\) は \(13x-5y=1\) の形になっているので、両辺を \(2\) 倍すると、
\(13 \cdot 4-5 \cdot 10=2\)
これより、\(13x-5y=2\) の整数解の \(1\) つは \((x~,~y)=(4~,~10)\) となるので、上と同じようにして整数解を求める
\(\begin{array}{rr}2~\\40~)~\overline{93~}\\\underline{80~}\\13~\end{array}\)
余り \(13\) より、\(40\) を \(13\) で割ると、
\(\begin{array}{rr}3~\\13~)~\overline{40~}\\\underline{39~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}93-40 \cdot 2=13\\40-13 \cdot 3=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=93~,~b=40\) 、余りを \(c=13\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-2b=c~~~\cdots {\small [\,1\,]}\\b-3c=1~~~\cdots {\small [\,2\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,2\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-3c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} (-3)\) と \({\small [\,2\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-3a+6b=-3c\\b-3c=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) が消去できるので、
\(\begin{eqnarray}~~~~~-3a+6b&=&-3c\\+~\big{)}~~~~~~~~~~b-3c&=&1\\[3pt]\hline -3a+7b&=&1\end{eqnarray}\)
\(a=93~,~b=40\) より、
\(93 \cdot (-3)+40 \cdot 7=1\)
これは \(93x+40y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(-3~,~7)\) である
\(93x+40y=1\) との差をとると、
\(\begin{eqnarray}~~~~~93x+40y&=&1\\-~\big{)}~~~93 \cdot (-3)+40 \cdot 7&=&1\\[3pt]\hline 93(x+3)+40(y-7)&=&0\end{eqnarray}\)
\(93(x+3)=-40(y-7)~~~\cdots {\small [\,5\,]}\)
\(93\) と \(40\) は互いに素より、\(x+3\) は \(40\) の倍数となるので、整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x+3&=&40k\\[3pt]~~~x&=&40k-3\end{eqnarray}\)
\({\small [\,5\,]}\) に \(x+3=40k\) を代入して、
\(\begin{eqnarray}~~~93 \cdot 40k&=&-40(y-7)\\[3pt]~~~-40(y-7)&=&40 \cdot 93k\\[3pt]~~~y-7&=&-93k\\[3pt]~~~y&=&-93k+7\end{eqnarray}\)
したがって、方程式 \(93x+40y=1\) の整数解は \(x=40k-3~,~y=-93k+7\) （\(k\) は整数）となる
\(93x+40y=1\) について、\(93\) と \(40\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}93-40 \cdot 2=13~~~\cdots {\small [\,1\,]}\\40-13 \cdot 3=1~~~\cdots {\small [\,2\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\require{enclose}\enclose{circle}{13}=\enclose{circle}{93}-\enclose{circle}{40} \cdot 2\) を \({\small [\,2\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{40}-(\enclose{circle}{93}-\enclose{circle}{40} \cdot 2) \cdot 3&=&1\\[5pt]~~~\enclose{circle}{40}-\enclose{circle}{93} \cdot 3+\enclose{circle}{40} \cdot 6&=&1\\[5pt]~~~\enclose{circle}{93} \cdot (-3)+\enclose{circle}{40} \cdot 7&=&1\end{eqnarray}\)
\(93 \cdot (-3)+40 \cdot 7=1\) は \(93x+40y=1\) の形になっているので、
これより、\(93x+40y=1\) の整数解の \(1\) つは \((x~,~y)=(-3~,~7)\) となるので、上と同じようにして整数解を求める
\(\begin{array}{rr}2~\\5~)~\overline{13~}\\\underline{10~}\\3~\end{array}\)
余り \(3\) より、\(5\) を \(3\) で割ると、
\(\begin{array}{rr}1~\\3~)~\overline{5~}\\\underline{3~}\\2~\end{array}\)
余り \(2\) より、\(3\) を \(2\) で割ると、
\(\begin{array}{rr}1~\\2~)~\overline{3~}\\\underline{2~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}13-5 \cdot 2=3\\5-3 \cdot 1=2\\3-2 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=13~,~b=5\) 、余りをそれぞれ \(c=3~,~d=2\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-2b=c~~~\cdots {\small [\,1\,]}\\b-c=d~~~\cdots {\small [\,2\,]}\\c-d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-1)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-b+c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
左辺に \(c+c=2c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 2\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}2a-4b=2c\\-b+c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~2a-4b&=&2c\\~~-b+c&=&-d~~\\+~\big{)}~~~~~~~~c-d&=&1\\[3pt]\hline 2a-5b&=&1\end{eqnarray}\)
\(a=13~,~b=5\) より、
\(13 \cdot 2-5 \cdot 5=1\)
これは \(13x-5y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(2~,~5)\) である
\(13x-5y=2\) の整数解を求めたいので、両辺を \(2\) 倍すると、
\(13 \cdot 4-5 \cdot 10=2\)
よって、\(13x-5y=2\) の整数解の \(1\) つは \((x~,~y)=(4~,~10)\) である
\(13x-5y=2\) との差をとると、
\(\begin{eqnarray}~~~~~13x-5y&=&2\\-~\big{)}~~~13 \cdot 4-5 \cdot 10&=&2\\[3pt]\hline 13(x-4)-5(y-10)&=&0\end{eqnarray}\)
\(13(x-4)=5(y-10)~~~\cdots {\small [\,4\,]}\)
\(13\) と \(5\) は互いに素より、\(x-4\) は \(5\) の倍数となるので、整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-4&=&5k\\[3pt]~~~x&=&5k+4\end{eqnarray}\)
\({\small [\,4\,]}\) に \(x-4=5k\) を代入して、
\(\begin{eqnarray}~~~13 \cdot 5k&=&5(y-10)\\[3pt]~~~5(y-10)&=&5 \cdot 13k\\[3pt]~~~y-10&=&13k\\[3pt]~~~y&=&13k+10\end{eqnarray}\)
したがって、方程式 \(13x-5y=2\) の整数解は \(x=5k+4~,~y=13k+10\) （\(k\) は整数）となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(13x-5y=2\) について、\(13\) と \(5\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}13-5 \cdot 2=3~~~\cdots {\small [\,1\,]}\\5-3 \cdot 1=2~~~\cdots {\small [\,2\,]}\\3-2 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{2}=\enclose{circle}{5}-\enclose{circle}{3}\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{3}-(\enclose{circle}{5}-\enclose{circle}{3})&=&1\\[5pt]~~~\enclose{circle}{3}-\enclose{circle}{5}+\enclose{circle}{3}&=&1\\[5pt]~~~\enclose{circle}{3} \cdot 2-\enclose{circle}{5}&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{3}=\enclose{circle}{13}-\enclose{circle}{5} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{13}-\enclose{circle}{5} \cdot 2) \cdot 2-\enclose{circle}{5}&=&1\\[5pt]~~~\enclose{circle}{13} \cdot 2-\enclose{circle}{5} \cdot 4-\enclose{circle}{5}&=&1\\[5pt]~~~\enclose{circle}{13} \cdot 2-\enclose{circle}{5} \cdot 5&=&1\end{eqnarray}\)
\(13 \cdot 2-5 \cdot 5=1\) は \(13x-5y=1\) の形になっているので、両辺を \(2\) 倍すると、
\(13 \cdot 4-5 \cdot 10=2\)
これより、\(13x-5y=2\) の整数解の \(1\) つは \((x~,~y)=(4~,~10)\) となるので、上と同じようにして整数解を求める
\({\small (2)}~93x+40y=1\) について、\(93\) を \(40\) で割ると、
\(\begin{array}{rr}2~\\40~)~\overline{93~}\\\underline{80~}\\13~\end{array}\)
余り \(13\) より、\(40\) を \(13\) で割ると、
\(\begin{array}{rr}3~\\13~)~\overline{40~}\\\underline{39~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}93-40 \cdot 2=13\\40-13 \cdot 3=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=93~,~b=40\) 、余りを \(c=13\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-2b=c~~~\cdots {\small [\,1\,]}\\b-3c=1~~~\cdots {\small [\,2\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,2\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-3c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} (-3)\) と \({\small [\,2\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-3a+6b=-3c\\b-3c=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) が消去できるので、
\(\begin{eqnarray}~~~~~-3a+6b&=&-3c\\+~\big{)}~~~~~~~~~~b-3c&=&1\\[3pt]\hline -3a+7b&=&1\end{eqnarray}\)
\(a=93~,~b=40\) より、
\(93 \cdot (-3)+40 \cdot 7=1\)
これは \(93x+40y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(-3~,~7)\) である
\(93x+40y=1\) との差をとると、
\(\begin{eqnarray}~~~~~93x+40y&=&1\\-~\big{)}~~~93 \cdot (-3)+40 \cdot 7&=&1\\[3pt]\hline 93(x+3)+40(y-7)&=&0\end{eqnarray}\)
\(93(x+3)=-40(y-7)~~~\cdots {\small [\,5\,]}\)
\(93\) と \(40\) は互いに素より、\(x+3\) は \(40\) の倍数となるので、整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x+3&=&40k\\[3pt]~~~x&=&40k-3\end{eqnarray}\)
\({\small [\,5\,]}\) に \(x+3=40k\) を代入して、
\(\begin{eqnarray}~~~93 \cdot 40k&=&-40(y-7)\\[3pt]~~~-40(y-7)&=&40 \cdot 93k\\[3pt]~~~y-7&=&-93k\\[3pt]~~~y&=&-93k+7\end{eqnarray}\)
したがって、方程式 \(93x+40y=1\) の整数解は \(x=40k-3~,~y=-93k+7\) （\(k\) は整数）となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(93x+40y=1\) について、\(93\) と \(40\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}93-40 \cdot 2=13~~~\cdots {\small [\,1\,]}\\40-13 \cdot 3=1~~~\cdots {\small [\,2\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\require{enclose}\enclose{circle}{13}=\enclose{circle}{93}-\enclose{circle}{40} \cdot 2\) を \({\small [\,2\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{40}-(\enclose{circle}{93}-\enclose{circle}{40} \cdot 2) \cdot 3&=&1\\[5pt]~~~\enclose{circle}{40}-\enclose{circle}{93} \cdot 3+\enclose{circle}{40} \cdot 6&=&1\\[5pt]~~~\enclose{circle}{93} \cdot (-3)+\enclose{circle}{40} \cdot 7&=&1\end{eqnarray}\)
\(93 \cdot (-3)+40 \cdot 7=1\) は \(93x+40y=1\) の形になっているので、
これより、\(93x+40y=1\) の整数解の \(1\) つは \((x~,~y)=(-3~,~7)\) となるので、上と同じようにして整数解を求める
問題アーカイブ10
問題アーカイブ10次の \(1\) 次不定方程式のすべての整数解を求めよ。
\({\small (1)}~113x+41y=1\)
\({\small (2)}~113x+41y=3\)
\({\small (1)}~113x+41y=1\)
\({\small (2)}~113x+41y=3\)
東京書籍｜Advanced数学A[002-901] p.143 練習問題 8
東京書籍｜Standard数学A[002-902] p.159 Level Up 10
▼ より詳しい解説を開く
\({\small (1)}~113x+41y=1\) について、\(113\) を \(41\) で割ると、
\(\begin{array}{rr}2~\\41~)~\overline{113~}\\\underline{82~}\\31~\end{array}\)
余り \(31\) より、\(41\) を \(31\) で割ると、
\(\begin{array}{rr}1~\\31~)~\overline{41~}\\\underline{31~}\\10~\end{array}\)
余り \(10\) より、\(31\) を \(10\) で割ると、
\(\begin{array}{rr}3~\\10~)~\overline{31~}\\\underline{30~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}113-41 \cdot 2=31\\41-31 \cdot 1=10\\31-10 \cdot 3=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=113~,~b=41\) 、余りをそれぞれ \(c=31~,~d=10\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-2b=c~~~\cdots {\small [\,1\,]}\\b-c=d~~~\cdots {\small [\,2\,]}\\c-3d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-3d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-3)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-3b+3c=-3d\\c-3d=1\end{array}\right.\end{eqnarray}\)
左辺に \(3c+c=4c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 4\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}4a-8b=4c\\-3b+3c=-3d\\c-3d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~4a-8b&=&4c\\~~-3b+3c&=&-3d~~\\+~\big{)}~~~~~~~~c-3d&=&1\\[3pt]\hline 4a-11b&=&1\end{eqnarray}\)
\(a=113~,~b=41\) より、
\(113 \cdot 4+41 \cdot (-11)=1\)
これは \(113x+41y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(4~,~-11)\) である
\(113x+41y=1\) との差をとると、
\(\begin{eqnarray}~~~~~113x+41y&=&1\\-~\big{)}~~~113 \cdot 4+41 \cdot (-11)&=&1\\[3pt]\hline 113(x-4)+41(y+11)&=&0\end{eqnarray}\)
\(113(x-4)=-41(y+11)~~~\cdots {\small [\,4\,]}\)
\(113\) と \(41\) は互いに素より、\(x-4\) は \(41\) の倍数となるので、整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-4&=&41k\\[3pt]~~~x&=&41k+4\end{eqnarray}\)
\({\small [\,4\,]}\) に \(x-4=41k\) を代入して、
\(\begin{eqnarray}~~~113 \cdot 41k&=&-41(y+11)\\[3pt]~~~-41(y+11)&=&41 \cdot 113k\\[3pt]~~~y+11&=&-113k\\[3pt]~~~y&=&-113k-11\end{eqnarray}\)
したがって、方程式 \(113x+41y=1\) の整数解は \(x=41k+4~,~y=-113k-11\) （\(k\) は整数）となる
\(113x+41y=1\) について、\(113\) と \(41\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}113-41 \cdot 2=31~~~\cdots {\small [\,1\,]}\\41-31 \cdot 1=10~~~\cdots {\small [\,2\,]}\\31-10 \cdot 3=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{10}=\enclose{circle}{41}-\enclose{circle}{31}\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{31}-(\enclose{circle}{41}-\enclose{circle}{31}) \cdot 3&=&1\\[5pt]~~~\enclose{circle}{31}-\enclose{circle}{41} \cdot 3+\enclose{circle}{31} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{31} \cdot 4-\enclose{circle}{41} \cdot 3&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{31}=\enclose{circle}{113}-\enclose{circle}{41} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{113}-\enclose{circle}{41} \cdot 2) \cdot 4-\enclose{circle}{41} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{113} \cdot 4-\enclose{circle}{41} \cdot 8-\enclose{circle}{41} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{113} \cdot 4+\enclose{circle}{41} \cdot (-11)&=&1\end{eqnarray}\)
\(113 \cdot 4+41 \cdot (-11)=1\) は \(113x+41y=1\) の形になっているので、
これより、\(113x+41y=1\) の整数解の \(1\) つは \((x~,~y)=(4~,~-11)\) となるので、上と同じようにして整数解を求める
\(\begin{array}{rr}2~\\41~)~\overline{113~}\\\underline{82~}\\31~\end{array}\)
余り \(31\) より、\(41\) を \(31\) で割ると、
\(\begin{array}{rr}1~\\31~)~\overline{41~}\\\underline{31~}\\10~\end{array}\)
余り \(10\) より、\(31\) を \(10\) で割ると、
\(\begin{array}{rr}3~\\10~)~\overline{31~}\\\underline{30~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}113-41 \cdot 2=31\\41-31 \cdot 1=10\\31-10 \cdot 3=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=113~,~b=41\) 、余りをそれぞれ \(c=31~,~d=10\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-2b=c~~~\cdots {\small [\,1\,]}\\b-c=d~~~\cdots {\small [\,2\,]}\\c-3d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-3d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-3)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-3b+3c=-3d\\c-3d=1\end{array}\right.\end{eqnarray}\)
左辺に \(3c+c=4c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 4\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}4a-8b=4c\\-3b+3c=-3d\\c-3d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~4a-8b&=&4c\\~~-3b+3c&=&-3d~~\\+~\big{)}~~~~~~~~c-3d&=&1\\[3pt]\hline 4a-11b&=&1\end{eqnarray}\)
\(a=113~,~b=41\) より、
\(113 \cdot 4+41 \cdot (-11)=1\)
これは \(113x+41y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(4~,~-11)\) である
\(113x+41y=3\) の整数解を求めたいので、両辺を \(3\) 倍すると、
\(113 \cdot 12+41 \cdot (-33)=3\)
よって、\(113x+41y=3\) の整数解の \(1\) つは \((x~,~y)=(12~,~-33)\) である
\(113x+41y=3\) との差をとると、
\(\begin{eqnarray}~~~~~113x+41y&=&3\\-~\big{)}~~~113 \cdot 12+41 \cdot (-33)&=&3\\[3pt]\hline 113(x-12)+41(y+33)&=&0\end{eqnarray}\)
\(113(x-12)=-41(y+33)~~~\cdots {\small [\,5\,]}\)
\(113\) と \(41\) は互いに素より、\(x-12\) は \(41\) の倍数となるので、整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-12&=&41k\\[3pt]~~~x&=&41k+12\end{eqnarray}\)
\({\small [\,5\,]}\) に \(x-12=41k\) を代入して、
\(\begin{eqnarray}~~~113 \cdot 41k&=&-41(y+33)\\[3pt]~~~-41(y+33)&=&41 \cdot 113k\\[3pt]~~~y+33&=&-113k\\[3pt]~~~y&=&-113k-33\end{eqnarray}\)
したがって、方程式 \(113x+41y=3\) の整数解は \(x=41k+12~,~y=-113k-33\) （\(k\) は整数）となる
\(113x+41y=3\) について、\(113\) と \(41\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}113-41 \cdot 2=31~~~\cdots {\small [\,1\,]}\\41-31 \cdot 1=10~~~\cdots {\small [\,2\,]}\\31-10 \cdot 3=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{10}=\enclose{circle}{41}-\enclose{circle}{31}\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{31}-(\enclose{circle}{41}-\enclose{circle}{31}) \cdot 3&=&1\\[5pt]~~~\enclose{circle}{31}-\enclose{circle}{41} \cdot 3+\enclose{circle}{31} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{31} \cdot 4-\enclose{circle}{41} \cdot 3&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{31}=\enclose{circle}{113}-\enclose{circle}{41} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{113}-\enclose{circle}{41} \cdot 2) \cdot 4-\enclose{circle}{41} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{113} \cdot 4-\enclose{circle}{41} \cdot 8-\enclose{circle}{41} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{113} \cdot 4+\enclose{circle}{41} \cdot (-11)&=&1\end{eqnarray}\)
\(113 \cdot 4+41 \cdot (-11)=1\) は \(113x+41y=1\) の形になっているので、両辺を \(3\) 倍すると、
\(113 \cdot 12+41 \cdot (-33)=3\)
これより、\(113x+41y=3\) の整数解の \(1\) つは \((x~,~y)=(12~,~-33)\) となるので、上と同じようにして整数解を求める
\(\begin{array}{rr}2~\\41~)~\overline{113~}\\\underline{82~}\\31~\end{array}\)
余り \(31\) より、\(41\) を \(31\) で割ると、
\(\begin{array}{rr}1~\\31~)~\overline{41~}\\\underline{31~}\\10~\end{array}\)
余り \(10\) より、\(31\) を \(10\) で割ると、
\(\begin{array}{rr}3~\\10~)~\overline{31~}\\\underline{30~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}113-41 \cdot 2=31\\41-31 \cdot 1=10\\31-10 \cdot 3=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=113~,~b=41\) 、余りをそれぞれ \(c=31~,~d=10\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-2b=c~~~\cdots {\small [\,1\,]}\\b-c=d~~~\cdots {\small [\,2\,]}\\c-3d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-3d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-3)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-3b+3c=-3d\\c-3d=1\end{array}\right.\end{eqnarray}\)
左辺に \(3c+c=4c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 4\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}4a-8b=4c\\-3b+3c=-3d\\c-3d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~4a-8b&=&4c\\~~-3b+3c&=&-3d~~\\+~\big{)}~~~~~~~~c-3d&=&1\\[3pt]\hline 4a-11b&=&1\end{eqnarray}\)
\(a=113~,~b=41\) より、
\(113 \cdot 4+41 \cdot (-11)=1\)
これは \(113x+41y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(4~,~-11)\) である
\(113x+41y=1\) との差をとると、
\(\begin{eqnarray}~~~~~113x+41y&=&1\\-~\big{)}~~~113 \cdot 4+41 \cdot (-11)&=&1\\[3pt]\hline 113(x-4)+41(y+11)&=&0\end{eqnarray}\)
\(113(x-4)=-41(y+11)~~~\cdots {\small [\,4\,]}\)
\(113\) と \(41\) は互いに素より、\(x-4\) は \(41\) の倍数となるので、整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-4&=&41k\\[3pt]~~~x&=&41k+4\end{eqnarray}\)
\({\small [\,4\,]}\) に \(x-4=41k\) を代入して、
\(\begin{eqnarray}~~~113 \cdot 41k&=&-41(y+11)\\[3pt]~~~-41(y+11)&=&41 \cdot 113k\\[3pt]~~~y+11&=&-113k\\[3pt]~~~y&=&-113k-11\end{eqnarray}\)
したがって、方程式 \(113x+41y=1\) の整数解は \(x=41k+4~,~y=-113k-11\) （\(k\) は整数）となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(113x+41y=1\) について、\(113\) と \(41\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}113-41 \cdot 2=31~~~\cdots {\small [\,1\,]}\\41-31 \cdot 1=10~~~\cdots {\small [\,2\,]}\\31-10 \cdot 3=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{10}=\enclose{circle}{41}-\enclose{circle}{31}\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{31}-(\enclose{circle}{41}-\enclose{circle}{31}) \cdot 3&=&1\\[5pt]~~~\enclose{circle}{31}-\enclose{circle}{41} \cdot 3+\enclose{circle}{31} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{31} \cdot 4-\enclose{circle}{41} \cdot 3&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{31}=\enclose{circle}{113}-\enclose{circle}{41} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{113}-\enclose{circle}{41} \cdot 2) \cdot 4-\enclose{circle}{41} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{113} \cdot 4-\enclose{circle}{41} \cdot 8-\enclose{circle}{41} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{113} \cdot 4+\enclose{circle}{41} \cdot (-11)&=&1\end{eqnarray}\)
\(113 \cdot 4+41 \cdot (-11)=1\) は \(113x+41y=1\) の形になっているので、
これより、\(113x+41y=1\) の整数解の \(1\) つは \((x~,~y)=(4~,~-11)\) となるので、上と同じようにして整数解を求める
\({\small (2)}~113x+41y=3\) について、まず \(113x+41y=1\) を考える。\(113\) を \(41\) で割ると、
\(\begin{array}{rr}2~\\41~)~\overline{113~}\\\underline{82~}\\31~\end{array}\)
余り \(31\) より、\(41\) を \(31\) で割ると、
\(\begin{array}{rr}1~\\31~)~\overline{41~}\\\underline{31~}\\10~\end{array}\)
余り \(10\) より、\(31\) を \(10\) で割ると、
\(\begin{array}{rr}3~\\10~)~\overline{31~}\\\underline{30~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}113-41 \cdot 2=31\\41-31 \cdot 1=10\\31-10 \cdot 3=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=113~,~b=41\) 、余りをそれぞれ \(c=31~,~d=10\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-2b=c~~~\cdots {\small [\,1\,]}\\b-c=d~~~\cdots {\small [\,2\,]}\\c-3d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-3d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-3)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-3b+3c=-3d\\c-3d=1\end{array}\right.\end{eqnarray}\)
左辺に \(3c+c=4c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 4\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}4a-8b=4c\\-3b+3c=-3d\\c-3d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~4a-8b&=&4c\\~~-3b+3c&=&-3d~~\\+~\big{)}~~~~~~~~c-3d&=&1\\[3pt]\hline 4a-11b&=&1\end{eqnarray}\)
\(a=113~,~b=41\) より、
\(113 \cdot 4+41 \cdot (-11)=1\)
これは \(113x+41y=1\) の形になっているので、整数解の \(1\) つは \((x~,~y)=(4~,~-11)\) である
\(113x+41y=3\) の整数解を求めたいので、両辺を \(3\) 倍すると、
\(113 \cdot 12+41 \cdot (-33)=3\)
よって、\(113x+41y=3\) の整数解の \(1\) つは \((x~,~y)=(12~,~-33)\) である
\(113x+41y=3\) との差をとると、
\(\begin{eqnarray}~~~~~113x+41y&=&3\\-~\big{)}~~~113 \cdot 12+41 \cdot (-33)&=&3\\[3pt]\hline 113(x-12)+41(y+33)&=&0\end{eqnarray}\)
\(113(x-12)=-41(y+33)~~~\cdots {\small [\,5\,]}\)
\(113\) と \(41\) は互いに素より、\(x-12\) は \(41\) の倍数となるので、整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-12&=&41k\\[3pt]~~~x&=&41k+12\end{eqnarray}\)
\({\small [\,5\,]}\) に \(x-12=41k\) を代入して、
\(\begin{eqnarray}~~~113 \cdot 41k&=&-41(y+33)\\[3pt]~~~-41(y+33)&=&41 \cdot 113k\\[3pt]~~~y+33&=&-113k\\[3pt]~~~y&=&-113k-33\end{eqnarray}\)
したがって、方程式 \(113x+41y=3\) の整数解は \(x=41k+12~,~y=-113k-33\) （\(k\) は整数）となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(113x+41y=3\) について、\(113\) と \(41\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}113-41 \cdot 2=31~~~\cdots {\small [\,1\,]}\\41-31 \cdot 1=10~~~\cdots {\small [\,2\,]}\\31-10 \cdot 3=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{10}=\enclose{circle}{41}-\enclose{circle}{31}\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{31}-(\enclose{circle}{41}-\enclose{circle}{31}) \cdot 3&=&1\\[5pt]~~~\enclose{circle}{31}-\enclose{circle}{41} \cdot 3+\enclose{circle}{31} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{31} \cdot 4-\enclose{circle}{41} \cdot 3&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{31}=\enclose{circle}{113}-\enclose{circle}{41} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{113}-\enclose{circle}{41} \cdot 2) \cdot 4-\enclose{circle}{41} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{113} \cdot 4-\enclose{circle}{41} \cdot 8-\enclose{circle}{41} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{113} \cdot 4+\enclose{circle}{41} \cdot (-11)&=&1\end{eqnarray}\)
\(113 \cdot 4+41 \cdot (-11)=1\) は \(113x+41y=1\) の形になっているので、両辺を \(3\) 倍すると、
\(113 \cdot 12+41 \cdot (-33)=3\)
これより、\(113x+41y=3\) の整数解の \(1\) つは \((x~,~y)=(12~,~-33)\) となるので、上と同じようにして整数解を求める
