このページは、「ユークリッドの互除法と等式を満たす整数」の練習問題アーカイブページとなります。
この問題の解き方の詳細は↓
ユークリッドの互除法と等式を満たす整数 で確認できます。
問題アーカイブ01
問題アーカイブ01次の等式を満たす整数 \(x~,~y\) の組を \(1\) つ求めよ。
\({\small (1)}~24x+17y=1\)
\({\small (2)}~67x+20y=2\)
\({\small (3)}~73x-51y=3\)
\({\small (1)}~24x+17y=1\)
\({\small (2)}~67x+20y=2\)
\({\small (3)}~73x-51y=3\)
数研出版｜数学A[104-901] p.155 練習18
▼ より詳しい解説を開く
\({\small (1)}~24x+17y=1\) について、\(24\) を \(17\) で割ると、
\(\begin{array}{rr}1~\\17~)~\overline{24~}\\\underline{17~}\\7~\end{array}\)
余り \(7\) より、\(17\) を \(7\) で割ると、
\(\begin{array}{rr}2~\\7~)~\overline{17~}\\\underline{14~}\\3~\end{array}\)
余り \(3\) より、\(7\) を \(3\) で割ると、
\(\begin{array}{rr}2~\\3~)~\overline{7~}\\\underline{6~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}24-17 \cdot 1=7\\17-7 \cdot 2=3\\7-3 \cdot 2=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=24~,~b=17\) 、余りをそれぞれ \(c=7~,~d=3\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-2c=d~~~\cdots {\small [\,2\,]}\\c-2d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-2d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-2)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-2b+4c=-2d\\c-2d=1\end{array}\right.\end{eqnarray}\)
左辺に \(4c+c=5c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 5\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}5a-5b=5c\\-2b+4c=-2d\\c-2d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~5a-5b&=&5c\\~~-2b+4c&=&-2d~~\\+~\big{)}~~~~~~~~c-2d&=&1\\[3pt]\hline 5a-7b&=&1\end{eqnarray}\)
\(a=24~,~b=17\) より、
\(24 \cdot 5+17 \cdot (-7)=1\)
したがって、\(24x+17y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(5~,~-7)\) となる
\({\small (1)}~24x+17y=1\) について、\(24\) と \(17\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}24-17 \cdot 1=7~~~\cdots {\small [\,1\,]}\\17-7 \cdot 2=3~~~\cdots {\small [\,2\,]}\\7-3 \cdot 2=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{3}=\enclose{circle}{17}-\enclose{circle}{7} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{7}-(\enclose{circle}{17}-\enclose{circle}{7} \cdot 2) \cdot 2&=&1\\[5pt]~~~\enclose{circle}{7}-\enclose{circle}{17} \cdot 2+\enclose{circle}{7} \cdot 4&=&1\\[5pt]~~~\enclose{circle}{7} \cdot 5-\enclose{circle}{17} \cdot 2&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{7}=\enclose{circle}{24}-\enclose{circle}{17}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{24}-\enclose{circle}{17}) \cdot 5-\enclose{circle}{17} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{24} \cdot 5-\enclose{circle}{17} \cdot 5-\enclose{circle}{17} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{24} \cdot 5+\enclose{circle}{17} \cdot (-7)&=&1\end{eqnarray}\)
\(24 \cdot 5+17 \cdot (-7)=1\) となるので、\(24x+17y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(5~,~-7)\) となる
\(\begin{array}{rr}3~\\20~)~\overline{67~}\\\underline{60~}\\7~\end{array}\)
余り \(7\) より、\(20\) を \(7\) で割ると、
\(\begin{array}{rr}2~\\7~)~\overline{20~}\\\underline{14~}\\6~\end{array}\)
余り \(6\) より、\(7\) を \(6\) で割ると、
\(\begin{array}{rr}1~\\6~)~\overline{7~}\\\underline{6~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}67-20 \cdot 3=7\\20-7 \cdot 2=6\\7-6 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=67~,~b=20\) 、余りをそれぞれ \(c=7~,~d=6\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-3b=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-9b=3c\\-b+2c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~3a-9b&=&3c\\-b+2c&=&-d~~\\+~\big{)}~~~~~~~c-d&=&1\\[3pt]\hline 3a-10b&=&1\end{eqnarray}\)
\(a=67~,~b=20\) より、
\(67 \cdot 3+20 \cdot (-10)=1\)
ここで、\(67x+20y=2\) を満たす整数 \(x~,~y\) を求めたいので、両辺を \(2\) 倍すると、
\(\begin{eqnarray}~~~67 \cdot 3 \cdot 2+20 \cdot (-10) \cdot 2&=&1 \cdot 2\\[3pt]~~~67 \cdot 6+20 \cdot (-20)&=&2\end{eqnarray}\)
したがって、\(67x+20y=2\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(6~,~-20)\) となる
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}67-20 \cdot 3=7~~~\cdots {\small [\,1\,]}\\20-7 \cdot 2=6~~~\cdots {\small [\,2\,]}\\7-6 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\enclose{circle}{6}=\enclose{circle}{20}-\enclose{circle}{7} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{7}-(\enclose{circle}{20}-\enclose{circle}{7} \cdot 2) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{7}-\enclose{circle}{20}+\enclose{circle}{7} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{7} \cdot 3-\enclose{circle}{20}&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{7}=\enclose{circle}{67}-\enclose{circle}{20} \cdot 3\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{67}-\enclose{circle}{20} \cdot 3) \cdot 3-\enclose{circle}{20}&=&1\\[5pt]~~~\enclose{circle}{67} \cdot 3-\enclose{circle}{20} \cdot 9-\enclose{circle}{20}&=&1\\[5pt]~~~\enclose{circle}{67} \cdot 3+\enclose{circle}{20} \cdot (-10)&=&1\end{eqnarray}\)
\(67 \cdot 3+20 \cdot (-10)=1\) となるので、両辺を \(2\) 倍すると、
\(67 \cdot 6+20 \cdot (-20)=2\)
したがって、\(67x+20y=2\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(6~,~-20)\) となる
\(\begin{array}{rr}1~\\51~)~\overline{73~}\\\underline{51~}\\22~\end{array}\)
余り \(22\) より、\(51\) を \(22\) で割ると、
\(\begin{array}{rr}2~\\22~)~\overline{51~}\\\underline{44~}\\7~\end{array}\)
余り \(7\) より、\(22\) を \(7\) で割ると、
\(\begin{array}{rr}3~\\7~)~\overline{22~}\\\underline{21~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}73-51 \cdot 1=22\\51-22 \cdot 2=7\\22-7 \cdot 3=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=73~,~b=51\) 、余りをそれぞれ \(c=22~,~d=7\) とすると、
\(\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\) の式をつくっていく
左辺に \(-3d\) があらわれるので、\({\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=73~,~b=51\) より、
\(73 \cdot 7+51 \cdot (-10)=1\)
ここで、\(73x-51y=3\) を満たす整数 \(x~,~y\) を求めたいので、\(51 \cdot (-10)=-51 \cdot 10\) と変形し、両辺を \(3\) 倍すると、
\(\begin{eqnarray}~~~73 \cdot 7-51 \cdot 10&=&1\\[3pt]~~~73 \cdot 7 \cdot 3-51 \cdot 10 \cdot 3&=&1 \cdot 3\\[3pt]~~~73 \cdot 21-51 \cdot 30&=&3\end{eqnarray}\)
したがって、\(73x-51y=3\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(21~,~30)\) となる
\({\small (3)}~73x-51y=3\) について、\(73\) と \(51\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}73-51 \cdot 1=22~~~\cdots {\small [\,1\,]}\\51-22 \cdot 2=7~~~\cdots {\small [\,2\,]}\\22-7 \cdot 3=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\enclose{circle}{7}=\enclose{circle}{51}-\enclose{circle}{22} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{22}-(\enclose{circle}{51}-\enclose{circle}{22} \cdot 2) \cdot 3&=&1\\[5pt]~~~\enclose{circle}{22}-\enclose{circle}{51} \cdot 3+\enclose{circle}{22} \cdot 6&=&1\\[5pt]~~~\enclose{circle}{22} \cdot 7-\enclose{circle}{51} \cdot 3&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{22}=\enclose{circle}{73}-\enclose{circle}{51}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{73}-\enclose{circle}{51}) \cdot 7-\enclose{circle}{51} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{73} \cdot 7-\enclose{circle}{51} \cdot 7-\enclose{circle}{51} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{73} \cdot 7-\enclose{circle}{51} \cdot 10&=&1\end{eqnarray}\)
\(73 \cdot 7-51 \cdot 10=1\) となるので、両辺を \(3\) 倍すると、
\(73 \cdot 21-51 \cdot 30=3\)
したがって、\(73x-51y=3\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(21~,~30)\) となる
\(\begin{array}{rr}1~\\17~)~\overline{24~}\\\underline{17~}\\7~\end{array}\)
余り \(7\) より、\(17\) を \(7\) で割ると、
\(\begin{array}{rr}2~\\7~)~\overline{17~}\\\underline{14~}\\3~\end{array}\)
余り \(3\) より、\(7\) を \(3\) で割ると、
\(\begin{array}{rr}2~\\3~)~\overline{7~}\\\underline{6~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}24-17 \cdot 1=7\\17-7 \cdot 2=3\\7-3 \cdot 2=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=24~,~b=17\) 、余りをそれぞれ \(c=7~,~d=3\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=c~~~\cdots {\small [\,1\,]}\\b-2c=d~~~\cdots {\small [\,2\,]}\\c-2d=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\sim{\small [\,3\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-2d\) があらわれるので、\({\small [\,2\,]} {\, \small \times \,} (-2)\) と \({\small [\,3\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-2b+4c=-2d\\c-2d=1\end{array}\right.\end{eqnarray}\)
左辺に \(4c+c=5c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} 5\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}5a-5b=5c\\-2b+4c=-2d\\c-2d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~5a-5b&=&5c\\~~-2b+4c&=&-2d~~\\+~\big{)}~~~~~~~~c-2d&=&1\\[3pt]\hline 5a-7b&=&1\end{eqnarray}\)
\(a=24~,~b=17\) より、
\(24 \cdot 5+17 \cdot (-7)=1\)
したがって、\(24x+17y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(5~,~-7)\) となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\({\small (1)}~24x+17y=1\) について、\(24\) と \(17\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}24-17 \cdot 1=7~~~\cdots {\small [\,1\,]}\\17-7 \cdot 2=3~~~\cdots {\small [\,2\,]}\\7-3 \cdot 2=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{3}=\enclose{circle}{17}-\enclose{circle}{7} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{7}-(\enclose{circle}{17}-\enclose{circle}{7} \cdot 2) \cdot 2&=&1\\[5pt]~~~\enclose{circle}{7}-\enclose{circle}{17} \cdot 2+\enclose{circle}{7} \cdot 4&=&1\\[5pt]~~~\enclose{circle}{7} \cdot 5-\enclose{circle}{17} \cdot 2&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{7}=\enclose{circle}{24}-\enclose{circle}{17}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{24}-\enclose{circle}{17}) \cdot 5-\enclose{circle}{17} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{24} \cdot 5-\enclose{circle}{17} \cdot 5-\enclose{circle}{17} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{24} \cdot 5+\enclose{circle}{17} \cdot (-7)&=&1\end{eqnarray}\)
\(24 \cdot 5+17 \cdot (-7)=1\) となるので、\(24x+17y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(5~,~-7)\) となる
\({\small (2)}~67x+20y=2\) について、\(67\) を \(20\) で割ると、
\(\begin{array}{rr}3~\\20~)~\overline{67~}\\\underline{60~}\\7~\end{array}\)
余り \(7\) より、\(20\) を \(7\) で割ると、
\(\begin{array}{rr}2~\\7~)~\overline{20~}\\\underline{14~}\\6~\end{array}\)
余り \(6\) より、\(7\) を \(6\) で割ると、
\(\begin{array}{rr}1~\\6~)~\overline{7~}\\\underline{6~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}67-20 \cdot 3=7\\20-7 \cdot 2=6\\7-6 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=67~,~b=20\) 、余りをそれぞれ \(c=7~,~d=6\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-3b=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-9b=3c\\-b+2c=-d\\c-d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~3a-9b&=&3c\\-b+2c&=&-d~~\\+~\big{)}~~~~~~~c-d&=&1\\[3pt]\hline 3a-10b&=&1\end{eqnarray}\)
\(a=67~,~b=20\) より、
\(67 \cdot 3+20 \cdot (-10)=1\)
ここで、\(67x+20y=2\) を満たす整数 \(x~,~y\) を求めたいので、両辺を \(2\) 倍すると、
\(\begin{eqnarray}~~~67 \cdot 3 \cdot 2+20 \cdot (-10) \cdot 2&=&1 \cdot 2\\[3pt]~~~67 \cdot 6+20 \cdot (-20)&=&2\end{eqnarray}\)
したがって、\(67x+20y=2\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(6~,~-20)\) となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\({\small (2)}~67x+20y=2\) について、\(67\) と \(20\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}67-20 \cdot 3=7~~~\cdots {\small [\,1\,]}\\20-7 \cdot 2=6~~~\cdots {\small [\,2\,]}\\7-6 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\enclose{circle}{6}=\enclose{circle}{20}-\enclose{circle}{7} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{7}-(\enclose{circle}{20}-\enclose{circle}{7} \cdot 2) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{7}-\enclose{circle}{20}+\enclose{circle}{7} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{7} \cdot 3-\enclose{circle}{20}&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{7}=\enclose{circle}{67}-\enclose{circle}{20} \cdot 3\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{67}-\enclose{circle}{20} \cdot 3) \cdot 3-\enclose{circle}{20}&=&1\\[5pt]~~~\enclose{circle}{67} \cdot 3-\enclose{circle}{20} \cdot 9-\enclose{circle}{20}&=&1\\[5pt]~~~\enclose{circle}{67} \cdot 3+\enclose{circle}{20} \cdot (-10)&=&1\end{eqnarray}\)
\(67 \cdot 3+20 \cdot (-10)=1\) となるので、両辺を \(2\) 倍すると、
\(67 \cdot 6+20 \cdot (-20)=2\)
したがって、\(67x+20y=2\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(6~,~-20)\) となる
\({\small (3)}~73x-51y=3\) について、\(73\) を \(51\) で割ると、
\(\begin{array}{rr}1~\\51~)~\overline{73~}\\\underline{51~}\\22~\end{array}\)
余り \(22\) より、\(51\) を \(22\) で割ると、
\(\begin{array}{rr}2~\\22~)~\overline{51~}\\\underline{44~}\\7~\end{array}\)
余り \(7\) より、\(22\) を \(7\) で割ると、
\(\begin{array}{rr}3~\\7~)~\overline{22~}\\\underline{21~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}73-51 \cdot 1=22\\51-22 \cdot 2=7\\22-7 \cdot 3=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=73~,~b=51\) 、余りをそれぞれ \(c=22~,~d=7\) とすると、
\(\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\) の式をつくっていく
左辺に \(-3d\) があらわれるので、\({\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=73~,~b=51\) より、
\(73 \cdot 7+51 \cdot (-10)=1\)
ここで、\(73x-51y=3\) を満たす整数 \(x~,~y\) を求めたいので、\(51 \cdot (-10)=-51 \cdot 10\) と変形し、両辺を \(3\) 倍すると、
\(\begin{eqnarray}~~~73 \cdot 7-51 \cdot 10&=&1\\[3pt]~~~73 \cdot 7 \cdot 3-51 \cdot 10 \cdot 3&=&1 \cdot 3\\[3pt]~~~73 \cdot 21-51 \cdot 30&=&3\end{eqnarray}\)
したがって、\(73x-51y=3\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(21~,~30)\) となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\({\small (3)}~73x-51y=3\) について、\(73\) と \(51\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}73-51 \cdot 1=22~~~\cdots {\small [\,1\,]}\\51-22 \cdot 2=7~~~\cdots {\small [\,2\,]}\\22-7 \cdot 3=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\enclose{circle}{7}=\enclose{circle}{51}-\enclose{circle}{22} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{22}-(\enclose{circle}{51}-\enclose{circle}{22} \cdot 2) \cdot 3&=&1\\[5pt]~~~\enclose{circle}{22}-\enclose{circle}{51} \cdot 3+\enclose{circle}{22} \cdot 6&=&1\\[5pt]~~~\enclose{circle}{22} \cdot 7-\enclose{circle}{51} \cdot 3&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{22}=\enclose{circle}{73}-\enclose{circle}{51}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{73}-\enclose{circle}{51}) \cdot 7-\enclose{circle}{51} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{73} \cdot 7-\enclose{circle}{51} \cdot 7-\enclose{circle}{51} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{73} \cdot 7-\enclose{circle}{51} \cdot 10&=&1\end{eqnarray}\)
\(73 \cdot 7-51 \cdot 10=1\) となるので、両辺を \(3\) 倍すると、
\(73 \cdot 21-51 \cdot 30=3\)
したがって、\(73x-51y=3\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(21~,~30)\) となる
問題アーカイブ02
問題アーカイブ02次の等式を満たす整数 \(x~,~y\) の組を \(1\) つ求めよ。
\({\small (1)}~26x+11y=1\)
\({\small (2)}~30x+17y=5\)
\({\small (1)}~26x+11y=1\)
\({\small (2)}~30x+17y=5\)
数研出版｜高等学校数学A[104-903] p.149 練習19
▼ より詳しい解説を開く
\({\small (1)}~26x+11y=1\) について、\(26\) を \(11\) で割ると、
\(\begin{array}{rr}2~\\11~)~\overline{26~}\\\underline{22~}\\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}26-11 \cdot 2=4\\11-4 \cdot 2=3\\4-3 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=26~,~b=11\) 、余りをそれぞれ \(c=4~,~d=3\) とすると、
\(\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=26~,~b=11\) より、
\(26 \cdot 3+11 \cdot (-7)=1\)
したがって、\(26x+11y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(3~,~-7)\) となる
\({\small (1)}~26x+11y=1\) について、\(26\) と \(11\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}26-11 \cdot 2=4~~~\cdots {\small [\,1\,]}\\11-4 \cdot 2=3~~~\cdots {\small [\,2\,]}\\4-3 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{3}=\enclose{circle}{11}-\enclose{circle}{4} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\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 [\,1\,]}\) より、\(\enclose{circle}{4}=\enclose{circle}{26}-\enclose{circle}{11} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{26}-\enclose{circle}{11} \cdot 2) \cdot 3-\enclose{circle}{11}&=&1\\[5pt]~~~\enclose{circle}{26} \cdot 3-\enclose{circle}{11} \cdot 6-\enclose{circle}{11}&=&1\\[5pt]~~~\enclose{circle}{26} \cdot 3+\enclose{circle}{11} \cdot (-7)&=&1\end{eqnarray}\)
\(26 \cdot 3+11 \cdot (-7)=1\) となるので、\(26x+11y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(3~,~-7)\) となる
\(\begin{array}{rr}1~\\17~)~\overline{30~}\\\underline{17~}\\13~\end{array}\)
余り \(13\) より、\(17\) を \(13\) で割ると、
\(\begin{array}{rr}1~\\13~)~\overline{17~}\\\underline{13~}\\4~\end{array}\)
余り \(4\) より、\(13\) を \(4\) で割ると、
\(\begin{array}{rr}3~\\4~)~\overline{13~}\\\underline{12~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}30-17 \cdot 1=13\\17-13 \cdot 1=4\\13-4 \cdot 3=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=30~,~b=17\) 、余りをそれぞれ \(c=13~,~d=4\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=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-4b=4c\\-3b+3c=-3d\\c-3d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~4a-4b&=&4c\\~~-3b+3c&=&-3d~~\\+~\big{)}~~~~~~~~c-3d&=&1\\[3pt]\hline 4a-7b&=&1\end{eqnarray}\)
\(a=30~,~b=17\) より、
\(30 \cdot 4+17 \cdot (-7)=1\)
ここで、\(30x+17y=5\) を満たす整数 \(x~,~y\) を求めたいので、両辺を \(5\) 倍すると、
\(\begin{eqnarray}~~~30 \cdot 4 \cdot 5+17 \cdot (-7) \cdot 5&=&1 \cdot 5\\[3pt]~~~30 \cdot 20+17 \cdot (-35)&=&5\end{eqnarray}\)
したがって、\(30x+17y=5\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(20~,~-35)\) となる
\({\small (2)}~30x+17y=5\) について、\(30\) と \(17\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}30-17 \cdot 1=13~~~\cdots {\small [\,1\,]}\\17-13 \cdot 1=4~~~\cdots {\small [\,2\,]}\\13-4 \cdot 3=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\enclose{circle}{4}=\enclose{circle}{17}-\enclose{circle}{13} \cdot 1\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{13}-(\enclose{circle}{17}-\enclose{circle}{13} \cdot 1) \cdot 3&=&1\\[5pt]~~~\enclose{circle}{13}-\enclose{circle}{17} \cdot 3+\enclose{circle}{13} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{13} \cdot 4-\enclose{circle}{17} \cdot 3&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{13}=\enclose{circle}{30}-\enclose{circle}{17}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{30}-\enclose{circle}{17}) \cdot 4-\enclose{circle}{17} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{30} \cdot 4-\enclose{circle}{17} \cdot 4-\enclose{circle}{17} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{30} \cdot 4+\enclose{circle}{17} \cdot (-7)&=&1\end{eqnarray}\)
\(30 \cdot 4+17 \cdot (-7)=1\) となるので、両辺を \(5\) 倍すると、
\(30 \cdot 20+17 \cdot (-35)=5\)
したがって、\(30x+17y=5\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(20~,~-35)\) となる
\(\begin{array}{rr}2~\\11~)~\overline{26~}\\\underline{22~}\\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}26-11 \cdot 2=4\\11-4 \cdot 2=3\\4-3 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=26~,~b=11\) 、余りをそれぞれ \(c=4~,~d=3\) とすると、
\(\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=26~,~b=11\) より、
\(26 \cdot 3+11 \cdot (-7)=1\)
したがって、\(26x+11y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(3~,~-7)\) となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\({\small (1)}~26x+11y=1\) について、\(26\) と \(11\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}26-11 \cdot 2=4~~~\cdots {\small [\,1\,]}\\11-4 \cdot 2=3~~~\cdots {\small [\,2\,]}\\4-3 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{3}=\enclose{circle}{11}-\enclose{circle}{4} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\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 [\,1\,]}\) より、\(\enclose{circle}{4}=\enclose{circle}{26}-\enclose{circle}{11} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{26}-\enclose{circle}{11} \cdot 2) \cdot 3-\enclose{circle}{11}&=&1\\[5pt]~~~\enclose{circle}{26} \cdot 3-\enclose{circle}{11} \cdot 6-\enclose{circle}{11}&=&1\\[5pt]~~~\enclose{circle}{26} \cdot 3+\enclose{circle}{11} \cdot (-7)&=&1\end{eqnarray}\)
\(26 \cdot 3+11 \cdot (-7)=1\) となるので、\(26x+11y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(3~,~-7)\) となる
\({\small (2)}~30x+17y=5\) について、\(30\) を \(17\) で割ると、
\(\begin{array}{rr}1~\\17~)~\overline{30~}\\\underline{17~}\\13~\end{array}\)
余り \(13\) より、\(17\) を \(13\) で割ると、
\(\begin{array}{rr}1~\\13~)~\overline{17~}\\\underline{13~}\\4~\end{array}\)
余り \(4\) より、\(13\) を \(4\) で割ると、
\(\begin{array}{rr}3~\\4~)~\overline{13~}\\\underline{12~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}30-17 \cdot 1=13\\17-13 \cdot 1=4\\13-4 \cdot 3=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=30~,~b=17\) 、余りをそれぞれ \(c=13~,~d=4\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=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-4b=4c\\-3b+3c=-3d\\c-3d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~4a-4b&=&4c\\~~-3b+3c&=&-3d~~\\+~\big{)}~~~~~~~~c-3d&=&1\\[3pt]\hline 4a-7b&=&1\end{eqnarray}\)
\(a=30~,~b=17\) より、
\(30 \cdot 4+17 \cdot (-7)=1\)
ここで、\(30x+17y=5\) を満たす整数 \(x~,~y\) を求めたいので、両辺を \(5\) 倍すると、
\(\begin{eqnarray}~~~30 \cdot 4 \cdot 5+17 \cdot (-7) \cdot 5&=&1 \cdot 5\\[3pt]~~~30 \cdot 20+17 \cdot (-35)&=&5\end{eqnarray}\)
したがって、\(30x+17y=5\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(20~,~-35)\) となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\({\small (2)}~30x+17y=5\) について、\(30\) と \(17\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}30-17 \cdot 1=13~~~\cdots {\small [\,1\,]}\\17-13 \cdot 1=4~~~\cdots {\small [\,2\,]}\\13-4 \cdot 3=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\enclose{circle}{4}=\enclose{circle}{17}-\enclose{circle}{13} \cdot 1\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{13}-(\enclose{circle}{17}-\enclose{circle}{13} \cdot 1) \cdot 3&=&1\\[5pt]~~~\enclose{circle}{13}-\enclose{circle}{17} \cdot 3+\enclose{circle}{13} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{13} \cdot 4-\enclose{circle}{17} \cdot 3&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{13}=\enclose{circle}{30}-\enclose{circle}{17}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{30}-\enclose{circle}{17}) \cdot 4-\enclose{circle}{17} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{30} \cdot 4-\enclose{circle}{17} \cdot 4-\enclose{circle}{17} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{30} \cdot 4+\enclose{circle}{17} \cdot (-7)&=&1\end{eqnarray}\)
\(30 \cdot 4+17 \cdot (-7)=1\) となるので、両辺を \(5\) 倍すると、
\(30 \cdot 20+17 \cdot (-35)=5\)
したがって、\(30x+17y=5\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(20~,~-35)\) となる
問題アーカイブ03
問題アーカイブ03次の等式を満たす整数 \(x~,~y\) の組を \(1\) つ求めよ。
\({\small (1)}~23x+16y=1\)
\({\small (2)}~34x-29y=4\)
\({\small (1)}~23x+16y=1\)
\({\small (2)}~34x-29y=4\)
数研出版｜高等学校数学A[104-903] p.157 問題 8
▼ より詳しい解説を開く
\({\small (1)}~23x+16y=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\) の式をつくっていく
左辺に \(-3d\) があらわれるので、\({\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\)
したがって、\(23x+16y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(7~,~-10)\) となる
\({\small (1)}~23x+16y=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\) となるので、\(23x+16y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(7~,~-10)\) となる
\(\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=4\) を満たす整数 \(x~,~y\) を求めたいので、\(29 \cdot (-7)=-29 \cdot 7\) と変形し、両辺を \(4\) 倍すると、
\(\begin{eqnarray}~~~34 \cdot 6-29 \cdot 7&=&1\\[3pt]~~~34 \cdot 6 \cdot 4-29 \cdot 7 \cdot 4&=&1 \cdot 4\\[3pt]~~~34 \cdot 24-29 \cdot 28&=&4\end{eqnarray}\)
したがって、\(34x-29y=4\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(24~,~28)\) となる
\({\small (2)}~34x-29y=4\) について、\(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\,]}\) より、\(\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\) となるので、両辺を \(4\) 倍すると、
\(34 \cdot 24-29 \cdot 28=4\)
したがって、\(34x-29y=4\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(24~,~28)\) となる
\(\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\) の式をつくっていく
左辺に \(-3d\) があらわれるので、\({\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\)
したがって、\(23x+16y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(7~,~-10)\) となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\({\small (1)}~23x+16y=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\) となるので、\(23x+16y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(7~,~-10)\) となる
\({\small (2)}~34x-29y=4\) について、\(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=4\) を満たす整数 \(x~,~y\) を求めたいので、\(29 \cdot (-7)=-29 \cdot 7\) と変形し、両辺を \(4\) 倍すると、
\(\begin{eqnarray}~~~34 \cdot 6-29 \cdot 7&=&1\\[3pt]~~~34 \cdot 6 \cdot 4-29 \cdot 7 \cdot 4&=&1 \cdot 4\\[3pt]~~~34 \cdot 24-29 \cdot 28&=&4\end{eqnarray}\)
したがって、\(34x-29y=4\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(24~,~28)\) となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\({\small (2)}~34x-29y=4\) について、\(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\,]}\) より、\(\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\) となるので、両辺を \(4\) 倍すると、
\(34 \cdot 24-29 \cdot 28=4\)
したがって、\(34x-29y=4\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(24~,~28)\) となる
問題アーカイブ04
問題アーカイブ04次の等式を満たす整数 \(x~,~y\) の組を \(1\) つ求めよ。
\({\small (1)}~26x+11y=1\)
\({\small (2)}~26x+11y=5\)
\({\small (1)}~26x+11y=1\)
\({\small (2)}~26x+11y=5\)
数研出版｜新編数学A[104-904] p.139 練習22
▼ より詳しい解説を開く
\({\small (1)}~26x+11y=1\) について、\(26\) を \(11\) で割ると、
\(\begin{array}{rr}2~\\11~)~\overline{26~}\\\underline{22~}\\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}26-11 \cdot 2=4\\11-4 \cdot 2=3\\4-3 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=26~,~b=11\) 、余りをそれぞれ \(c=4~,~d=3\) とすると、
\(\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=26~,~b=11\) より、
\(26 \cdot 3+11 \cdot (-7)=1\)
したがって、\(26x+11y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(3~,~-7)\) となる
\({\small (1)}~26x+11y=1\) について、\(26\) と \(11\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}26-11 \cdot 2=4~~~\cdots {\small [\,1\,]}\\11-4 \cdot 2=3~~~\cdots {\small [\,2\,]}\\4-3 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{3}=\enclose{circle}{11}-\enclose{circle}{4} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\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 [\,1\,]}\) より、\(\enclose{circle}{4}=\enclose{circle}{26}-\enclose{circle}{11} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{26}-\enclose{circle}{11} \cdot 2) \cdot 3-\enclose{circle}{11}&=&1\\[5pt]~~~\enclose{circle}{26} \cdot 3-\enclose{circle}{11} \cdot 6-\enclose{circle}{11}&=&1\\[5pt]~~~\enclose{circle}{26} \cdot 3+\enclose{circle}{11} \cdot (-7)&=&1\end{eqnarray}\)
\(26 \cdot 3+11 \cdot (-7)=1\) となるので、\(26x+11y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(3~,~-7)\) となる
\(26 \cdot 3+11 \cdot (-7)=1\)
ここで、\(26x+11y=5\) を満たす整数 \(x~,~y\) を求めたいので、両辺を \(5\) 倍すると、
\(\begin{eqnarray}~~~26 \cdot 3 \cdot 5+11 \cdot (-7) \cdot 5&=&1 \cdot 5\\[3pt]~~~26 \cdot 15+11 \cdot (-35)&=&5\end{eqnarray}\)
したがって、\(26x+11y=5\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(15~,~-35)\) となる
\({\small (2)}~26x+11y=5\) について、\({\small (1)}\) より、
\(26 \cdot 3+11 \cdot (-7)=1\)
両辺を \(5\) 倍すると、
\(26 \cdot 15+11 \cdot (-35)=5\)
したがって、\(26x+11y=5\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(15~,~-35)\) となる
\(\begin{array}{rr}2~\\11~)~\overline{26~}\\\underline{22~}\\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}26-11 \cdot 2=4\\11-4 \cdot 2=3\\4-3 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=26~,~b=11\) 、余りをそれぞれ \(c=4~,~d=3\) とすると、
\(\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=26~,~b=11\) より、
\(26 \cdot 3+11 \cdot (-7)=1\)
したがって、\(26x+11y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(3~,~-7)\) となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\({\small (1)}~26x+11y=1\) について、\(26\) と \(11\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}26-11 \cdot 2=4~~~\cdots {\small [\,1\,]}\\11-4 \cdot 2=3~~~\cdots {\small [\,2\,]}\\4-3 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{3}=\enclose{circle}{11}-\enclose{circle}{4} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\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 [\,1\,]}\) より、\(\enclose{circle}{4}=\enclose{circle}{26}-\enclose{circle}{11} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{26}-\enclose{circle}{11} \cdot 2) \cdot 3-\enclose{circle}{11}&=&1\\[5pt]~~~\enclose{circle}{26} \cdot 3-\enclose{circle}{11} \cdot 6-\enclose{circle}{11}&=&1\\[5pt]~~~\enclose{circle}{26} \cdot 3+\enclose{circle}{11} \cdot (-7)&=&1\end{eqnarray}\)
\(26 \cdot 3+11 \cdot (-7)=1\) となるので、\(26x+11y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(3~,~-7)\) となる
\({\small (2)}~26x+11y=5\) について、\({\small (1)}\) より、
\(26 \cdot 3+11 \cdot (-7)=1\)
ここで、\(26x+11y=5\) を満たす整数 \(x~,~y\) を求めたいので、両辺を \(5\) 倍すると、
\(\begin{eqnarray}~~~26 \cdot 3 \cdot 5+11 \cdot (-7) \cdot 5&=&1 \cdot 5\\[3pt]~~~26 \cdot 15+11 \cdot (-35)&=&5\end{eqnarray}\)
したがって、\(26x+11y=5\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(15~,~-35)\) となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\({\small (2)}~26x+11y=5\) について、\({\small (1)}\) より、
\(26 \cdot 3+11 \cdot (-7)=1\)
両辺を \(5\) 倍すると、
\(26 \cdot 15+11 \cdot (-35)=5\)
したがって、\(26x+11y=5\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(15~,~-35)\) となる
問題アーカイブ05
問題アーカイブ05次の等式を満たす整数 \(x~,~y\) の組を \(1\) つ求めよ。
\(30x+17y=5\)
\(30x+17y=5\)
数研出版｜新編数学A[104-904] p.147 補充問題 3
▼ より詳しい解説を開く
\(30x+17y=5\) について、\(30\) を \(17\) で割ると、
\(\begin{array}{rr}1~\\17~)~\overline{30~}\\\underline{17~}\\13~\end{array}\)
余り \(13\) より、\(17\) を \(13\) で割ると、
\(\begin{array}{rr}1~\\13~)~\overline{17~}\\\underline{13~}\\4~\end{array}\)
余り \(4\) より、\(13\) を \(4\) で割ると、
\(\begin{array}{rr}3~\\4~)~\overline{13~}\\\underline{12~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}30-17 \cdot 1=13\\17-13 \cdot 1=4\\13-4 \cdot 3=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=30~,~b=17\) 、余りをそれぞれ \(c=13~,~d=4\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=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-4b=4c\\-3b+3c=-3d\\c-3d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~4a-4b&=&4c\\~~-3b+3c&=&-3d~~\\+~\big{)}~~~~~~~~c-3d&=&1\\[3pt]\hline 4a-7b&=&1\end{eqnarray}\)
\(a=30~,~b=17\) より、
\(30 \cdot 4+17 \cdot (-7)=1\)
ここで、\(30x+17y=5\) を満たす整数 \(x~,~y\) を求めたいので、両辺を \(5\) 倍すると、
\(\begin{eqnarray}~~~30 \cdot 4 \cdot 5+17 \cdot (-7) \cdot 5&=&1 \cdot 5\\[3pt]~~~30 \cdot 20+17 \cdot (-35)&=&5\end{eqnarray}\)
したがって、\(30x+17y=5\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(20~,~-35)\) となる
\(30x+17y=5\) について、\(30\) と \(17\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}30-17 \cdot 1=13~~~\cdots {\small [\,1\,]}\\17-13 \cdot 1=4~~~\cdots {\small [\,2\,]}\\13-4 \cdot 3=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{4}=\enclose{circle}{17}-\enclose{circle}{13} \cdot 1\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{13}-(\enclose{circle}{17}-\enclose{circle}{13} \cdot 1) \cdot 3&=&1\\[5pt]~~~\enclose{circle}{13}-\enclose{circle}{17} \cdot 3+\enclose{circle}{13} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{13} \cdot 4-\enclose{circle}{17} \cdot 3&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{13}=\enclose{circle}{30}-\enclose{circle}{17}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{30}-\enclose{circle}{17}) \cdot 4-\enclose{circle}{17} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{30} \cdot 4-\enclose{circle}{17} \cdot 4-\enclose{circle}{17} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{30} \cdot 4+\enclose{circle}{17} \cdot (-7)&=&1\end{eqnarray}\)
\(30 \cdot 4+17 \cdot (-7)=1\) となるので、両辺を \(5\) 倍すると、
\(30 \cdot 20+17 \cdot (-35)=5\)
したがって、\(30x+17y=5\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(20~,~-35)\) となる
\(\begin{array}{rr}1~\\17~)~\overline{30~}\\\underline{17~}\\13~\end{array}\)
余り \(13\) より、\(17\) を \(13\) で割ると、
\(\begin{array}{rr}1~\\13~)~\overline{17~}\\\underline{13~}\\4~\end{array}\)
余り \(4\) より、\(13\) を \(4\) で割ると、
\(\begin{array}{rr}3~\\4~)~\overline{13~}\\\underline{12~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}30-17 \cdot 1=13\\17-13 \cdot 1=4\\13-4 \cdot 3=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=30~,~b=17\) 、余りをそれぞれ \(c=13~,~d=4\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-b=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-4b=4c\\-3b+3c=-3d\\c-3d=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) と \(d\) が消去できるので、
\(\begin{eqnarray}~~~~~4a-4b&=&4c\\~~-3b+3c&=&-3d~~\\+~\big{)}~~~~~~~~c-3d&=&1\\[3pt]\hline 4a-7b&=&1\end{eqnarray}\)
\(a=30~,~b=17\) より、
\(30 \cdot 4+17 \cdot (-7)=1\)
ここで、\(30x+17y=5\) を満たす整数 \(x~,~y\) を求めたいので、両辺を \(5\) 倍すると、
\(\begin{eqnarray}~~~30 \cdot 4 \cdot 5+17 \cdot (-7) \cdot 5&=&1 \cdot 5\\[3pt]~~~30 \cdot 20+17 \cdot (-35)&=&5\end{eqnarray}\)
したがって、\(30x+17y=5\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(20~,~-35)\) となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(30x+17y=5\) について、\(30\) と \(17\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}30-17 \cdot 1=13~~~\cdots {\small [\,1\,]}\\17-13 \cdot 1=4~~~\cdots {\small [\,2\,]}\\13-4 \cdot 3=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\require{enclose}\enclose{circle}{4}=\enclose{circle}{17}-\enclose{circle}{13} \cdot 1\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{13}-(\enclose{circle}{17}-\enclose{circle}{13} \cdot 1) \cdot 3&=&1\\[5pt]~~~\enclose{circle}{13}-\enclose{circle}{17} \cdot 3+\enclose{circle}{13} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{13} \cdot 4-\enclose{circle}{17} \cdot 3&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{13}=\enclose{circle}{30}-\enclose{circle}{17}\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{30}-\enclose{circle}{17}) \cdot 4-\enclose{circle}{17} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{30} \cdot 4-\enclose{circle}{17} \cdot 4-\enclose{circle}{17} \cdot 3&=&1\\[5pt]~~~\enclose{circle}{30} \cdot 4+\enclose{circle}{17} \cdot (-7)&=&1\end{eqnarray}\)
\(30 \cdot 4+17 \cdot (-7)=1\) となるので、両辺を \(5\) 倍すると、
\(30 \cdot 20+17 \cdot (-35)=5\)
したがって、\(30x+17y=5\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(20~,~-35)\) となる
問題アーカイブ06
問題アーカイブ06\(1\) 次不定方程式 \(223x+105y=1\) の \(1\) 組の整数解を求めよ。
東京書籍｜Advanced数学A[002-901] p.137 問24
東京書籍｜Standard
▼ より詳しい解説を開く
数学A[002-902] p.133 Training 9
\(223x+105y=1\) について、\(223\) を \(105\) で割ると、
\(\begin{array}{rr}2~\\105~)~\overline{223~}\\\underline{210~}\\13~\end{array}\)
余り \(13\) より、\(105\) を \(13\) で割ると、
\(\begin{array}{rr}8~\\13~)~\overline{105~}\\\underline{104~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}223-105 \cdot 2=13\\105-13 \cdot 8=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=223~,~b=105\) 、余りを \(c=13\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-2b=c~~~\cdots {\small [\,1\,]}\\b-8c=1~~~\cdots {\small [\,2\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}~,~{\small [\,2\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-8c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} (-8)\) と \({\small [\,2\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-8a+16b=-8c\\b-8c=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) が消去できるので、
\(\begin{eqnarray}~~~~~-8a+16b&=&-8c\\+~\big{)}~~~~~~~~~~~b-8c&=&1\\[3pt]\hline -8a+17b&=&1\end{eqnarray}\)
\(a=223~,~b=105\) より、
\(223 \cdot (-8)+105 \cdot 17=1\)
したがって、\(223x+105y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(-8~,~17)\) となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(223x+105y=1\) について、\(223\) と \(105\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}223-105 \cdot 2=13~~~\cdots {\small [\,1\,]}\\105-13 \cdot 8=1~~~\cdots {\small [\,2\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\require{enclose}\enclose{circle}{13}=\enclose{circle}{223}-\enclose{circle}{105} \cdot 2\) を \({\small [\,2\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{105}-(\enclose{circle}{223}-\enclose{circle}{105} \cdot 2) \cdot 8&=&1\\[5pt]~~~\enclose{circle}{105}-\enclose{circle}{223} \cdot 8+\enclose{circle}{105} \cdot 16&=&1\\[5pt]~~~\enclose{circle}{223} \cdot (-8)+\enclose{circle}{105} \cdot 17&=&1\end{eqnarray}\)
\(223 \cdot (-8)+105 \cdot 17=1\) となるので、\(223x+105y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(-8~,~17)\) となる
問題アーカイブ07
問題アーカイブ07\(1\) 次不定方程式 \(163x+78y=1\) の \(1\) 組の整数解を求めよ。
東京書籍｜Standard数学A[002-902] p.132 問20
▼ より詳しい解説を開く
\(163x+78y=1\) について、\(163\) を \(78\) で割ると、
\(\begin{array}{rr}2~\\78~)~\overline{163~}\\\underline{156~}\\7~\end{array}\)
余り \(7\) より、\(78\) を \(7\) で割ると、
\(\begin{array}{rr}11~\\7~)~\overline{78~}\\\underline{77~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}163-78 \cdot 2=7\\78-7 \cdot 11=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=163~,~b=78\) 、余りを \(c=7\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-2b=c~~~\cdots {\small [\,1\,]}\\b-11c=1~~~\cdots {\small [\,2\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}~,~{\small [\,2\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-11c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} (-11)\) と \({\small [\,2\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-11a+22b=-11c\\b-11c=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) が消去できるので、
\(\begin{eqnarray}~~~~~-11a+22b&=&-11c\\+~\big{)}~~~~~~~~~~~~~b-11c&=&1\\[3pt]\hline -11a+23b&=&1\end{eqnarray}\)
\(a=163~,~b=78\) より、
\(163 \cdot (-11)+78 \cdot 23=1\)
したがって、\(163x+78y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(-11~,~23)\) となる
\(163x+78y=1\) について、\(163\) と \(78\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}163-78 \cdot 2=7~~~\cdots {\small [\,1\,]}\\78-7 \cdot 11=1~~~\cdots {\small [\,2\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\require{enclose}\enclose{circle}{7}=\enclose{circle}{163}-\enclose{circle}{78} \cdot 2\) を \({\small [\,2\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{78}-(\enclose{circle}{163}-\enclose{circle}{78} \cdot 2) \cdot 11&=&1\\[5pt]~~~\enclose{circle}{78}-\enclose{circle}{163} \cdot 11+\enclose{circle}{78} \cdot 22&=&1\\[5pt]~~~\enclose{circle}{163} \cdot (-11)+\enclose{circle}{78} \cdot 23&=&1\end{eqnarray}\)
\(163 \cdot (-11)+78 \cdot 23=1\) となるので、\(163x+78y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(-11~,~23)\) となる
\(\begin{array}{rr}2~\\78~)~\overline{163~}\\\underline{156~}\\7~\end{array}\)
余り \(7\) より、\(78\) を \(7\) で割ると、
\(\begin{array}{rr}11~\\7~)~\overline{78~}\\\underline{77~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}163-78 \cdot 2=7\\78-7 \cdot 11=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=163~,~b=78\) 、余りを \(c=7\) とすると、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}a-2b=c~~~\cdots {\small [\,1\,]}\\b-11c=1~~~\cdots {\small [\,2\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}~,~{\small [\,2\,]}\) より、\(a\) と \(b\) の式をつくっていく
左辺に \(-11c\) があらわれるので、\({\small [\,1\,]} {\, \small \times \,} (-11)\) と \({\small [\,2\,]}\) より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}-11a+22b=-11c\\b-11c=1\end{array}\right.\end{eqnarray}\)
両辺を加えると、\(c\) が消去できるので、
\(\begin{eqnarray}~~~~~-11a+22b&=&-11c\\+~\big{)}~~~~~~~~~~~~~b-11c&=&1\\[3pt]\hline -11a+23b&=&1\end{eqnarray}\)
\(a=163~,~b=78\) より、
\(163 \cdot (-11)+78 \cdot 23=1\)
したがって、\(163x+78y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(-11~,~23)\) となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(163x+78y=1\) について、\(163\) と \(78\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}163-78 \cdot 2=7~~~\cdots {\small [\,1\,]}\\78-7 \cdot 11=1~~~\cdots {\small [\,2\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\require{enclose}\enclose{circle}{7}=\enclose{circle}{163}-\enclose{circle}{78} \cdot 2\) を \({\small [\,2\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{78}-(\enclose{circle}{163}-\enclose{circle}{78} \cdot 2) \cdot 11&=&1\\[5pt]~~~\enclose{circle}{78}-\enclose{circle}{163} \cdot 11+\enclose{circle}{78} \cdot 22&=&1\\[5pt]~~~\enclose{circle}{163} \cdot (-11)+\enclose{circle}{78} \cdot 23&=&1\end{eqnarray}\)
\(163 \cdot (-11)+78 \cdot 23=1\) となるので、\(163x+78y=1\) を満たす \(x~,~y\) の組の \(1\) つは \((x~,~y)=(-11~,~23)\) となる
