- 数学A｜整数の性質「ユークリッドの互除法と等式を満たす整数」の基本例題解説ページです。
- 目次をクリックすると各セクションへ移動します。
問題｜ユークリッドの互除法と等式を満たす整数
整数の性質 30等式 \(23x+16y=1~,~\)\(40x+17y=2\) を満たす整数 \(x~,~y\) の組の \(1\) つの求め方は？
高校数学A｜整数の性質
練習問題アーカイブページはこちら→
ユークリッドの互除法と等式を満たす整数
解法のPoint
ユークリッドの互除法と等式を満たす整数
Point：ユークリッドの互除法と等式を満たす整数ユークリッドの互除法と等式を満たす整数は、
① ユークリッドの互除法の式を、移項した式をつくる。
\(23\) と \(16\) の互除法より、
\(\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~,~b\) 、互除法の余りを \(c~,~d\) として、\(c~,~d\) を消去して \(a\) と \(b\) の式にする。
\(\begin{eqnarray}~~~~~7a-7b&=&7c\\~~-3b+6c&=&-3d~~\\+~\big{)}~~~~~~~~c-3d&=&1\\[3pt]\hline 7a-10b&=&1\end{eqnarray}\)
③ \(a\) と \(b\) をもとに戻し、\(ax+by=1\) を満たす整数の組 \((x~,~y)\) の \(1\) つを求める。
※ 教科書では、ユークリッドの互除法の式を順に代入していく方法が一般的ですが、ここでは文字式で置き換えて加減法で \(a~,~b\) だけの式にする方法を採用しています。
① ユークリッドの互除法の式を、移項した式をつくる。
\(23\) と \(16\) の互除法より、
\(\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~,~b\) 、互除法の余りを \(c~,~d\) として、\(c~,~d\) を消去して \(a\) と \(b\) の式にする。
\(\begin{eqnarray}~~~~~7a-7b&=&7c\\~~-3b+6c&=&-3d~~\\+~\big{)}~~~~~~~~c-3d&=&1\\[3pt]\hline 7a-10b&=&1\end{eqnarray}\)
③ \(a\) と \(b\) をもとに戻し、\(ax+by=1\) を満たす整数の組 \((x~,~y)\) の \(1\) つを求める。
※ 教科書では、ユークリッドの互除法の式を順に代入していく方法が一般的ですが、ここでは文字式で置き換えて加減法で \(a~,~b\) だけの式にする方法を採用しています。
©︎ 2026 教科書より詳しい高校数学 yorikuwa.com
詳しい解説｜ユークリッドの互除法と等式を満たす整数
整数の性質 30等式 \(23x+16y=1~,~\)\(40x+17y=2\) を満たす整数 \(x~,~y\) の組の \(1\) つの求め方は？
高校数学A｜整数の性質
\(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)\) となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(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)\) となる
\(40x+17y=2\) について、\(40\) を \(17\) で割ると、
\(\begin{array}{rr}2~\\17~)~\overline{40~}\\\underline{34~}\\6~\end{array}\)
余り \(6\) より、\(17\) を \(6\) で割ると、
\(\begin{array}{rr}2~\\6~)~\overline{17~}\\\underline{12~}\\5~\end{array}\)
余り \(5\) より、\(6\) を \(5\) で割ると、
\(\begin{array}{rr}1~\\5~)~\overline{6~}\\\underline{5~}\\1~\end{array}\)
これより、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}40-17 \cdot 2=6\\17-6 \cdot 2=5\\6-5 \cdot 1=1\end{array}\right.\end{eqnarray}\)
ここで、\(a=40~,~b=17\) 、余りをそれぞれ \(c=6~,~d=5\) とすると、
\(\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}\)
左辺に \(c+2c=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=40~,~b=17\) より、
\(40 \cdot 3+17 \cdot (-7)=1\)
ここで、\(40x+17y=2\) を満たす整数 \(x~,~y\) を求めたいので、両辺を \(2\) 倍すると、
\(\begin{eqnarray}~~~40 \cdot 3 \cdot 2+17 \cdot (-7) \cdot 2&=&1 \cdot 2\\[3pt]~~~40 \cdot 6+17 \cdot (-14)&=&2\end{eqnarray}\)
したがって、\(40x+17y=2\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(6~,~-14)\) となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(40x+17y=2\) について、\(40\) と \(17\) の互除法より、
\(\begin{eqnarray}~~~ \left\{~\begin{array}{l}40-17 \cdot 2=6~~~\cdots {\small [\,1\,]}\\17-6 \cdot 2=5~~~\cdots {\small [\,2\,]}\\6-5 \cdot 1=1~~~\cdots {\small [\,3\,]}\end{array}\right.\end{eqnarray}\)
\({\small [\,2\,]}\) より、\(\enclose{circle}{5}=\enclose{circle}{17}-\enclose{circle}{6} \cdot 2\) を \({\small [\,3\,]}\) に代入すると、
\(\begin{eqnarray}~~~\enclose{circle}{6}-(\enclose{circle}{17}-\enclose{circle}{6} \cdot 2) \cdot 1&=&1\\[5pt]~~~\enclose{circle}{6}-\enclose{circle}{17}+\enclose{circle}{6} \cdot 2&=&1\\[5pt]~~~\enclose{circle}{6} \cdot 3-\enclose{circle}{17}&=&1\end{eqnarray}\)
\({\small [\,1\,]}\) より、\(\enclose{circle}{6}=\enclose{circle}{40}-\enclose{circle}{17} \cdot 2\) を代入すると、
\(\begin{eqnarray}~~~(\enclose{circle}{40}-\enclose{circle}{17} \cdot 2) \cdot 3-\enclose{circle}{17}&=&1\\[5pt]~~~\enclose{circle}{40} \cdot 3-\enclose{circle}{17} \cdot 6-\enclose{circle}{17}&=&1\\[5pt]~~~\enclose{circle}{40} \cdot 3+\enclose{circle}{17} \cdot (-7)&=&1\end{eqnarray}\)
\(40 \cdot 3+17 \cdot (-7)=1\) となるので、両辺を \(2\) 倍すると、
\(40 \cdot 6+17 \cdot (-14)=2\)
したがって、\(40x+17y=2\) を満たす整数 \(x~,~y\) の組の \(1\) つは \((x~,~y)=(6~,~-14)\) となる
