- 数学A｜整数の性質「ユークリッドの互除法と1次不定方程式」の基本例題解説ページです。
- 目次をクリックすると各セクションへ移動します。
問題｜ユークリッドの互除法と1次不定方程式
整数の性質 32方程式 \(23x+16y=1~,~\)\(23x+16y=3\) の整数解をすべて求める方法は？
高校数学A｜整数の性質
練習問題アーカイブページはこちら→
ユークリッドの互除法と1次不定方程式
解法のPoint
ユークリッドの互除法と1次不定方程式
Point：ユークリッドの互除法と1次不定方程式ユークリッドの互除法と1次不定方程式は、
① ユークリッドの互除法の式を移項した式をつくる。
\(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}\)
これより、
整数解の \(1\) 組が \((x~,~y)=(7~,~-10)\)
③ もとの方程式と②の整数解の式の差をとり、整数解を求める。
\(a~,~b\) が互いに素なことを用いて、
整数解 \((x~,~y)\) を求める。
① ユークリッドの互除法の式を移項した式をつくる。
\(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}\)
これより、
整数解の \(1\) 組が \((x~,~y)=(7~,~-10)\)
③ もとの方程式と②の整数解の式の差をとり、整数解を求める。
\(a~,~b\) が互いに素なことを用いて、
整数解 \((x~,~y)\) を求める。
©︎ 2026 教科書より詳しい高校数学 yorikuwa.com
詳しい解説｜ユークリッドの互除法と1次不定方程式
整数の性質 32方程式 \(23x+16y=1~,~\)\(23x+16y=3\) の整数解をすべて求める方法は？
高校数学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\) の整数解の \(1\) つは \((x~,~y)=(7~,~-10)\) である
\(23x+16y=1\) との差をとると、
\(\begin{eqnarray}~~~~~23x+16y&=&1\\-~\big{)}~~~23 \cdot 7+16 \cdot (-10)&=&1\\[3pt]\hline 23(x-7)+16(y+10)&=&0\end{eqnarray}\)
\(23(x-7)=-16(y+10)~~~\cdots {\small [\,4\,]}\)
\(23\) と \(16\) は互いに素より、\(x-7\) は \(16\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-7&=&16k\\[3pt]~~~x&=&16k+7\end{eqnarray}\)
\({\small [\,4\,]}\) に \(x-7=16k\) を代入して、
\(\begin{eqnarray}~~~23 \cdot 16k&=&-16(y+10)\\[3pt]~~~-16(y+10)&=&16 \cdot 23k\\[3pt]~~~y+10&=&-23k\\[3pt]~~~y&=&-23k-10\end{eqnarray}\)
したがって、方程式 \(23x+16y=1\) の整数解は \(x=16k+7~,~y=-23k-10\) （\(k\) は整数）となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(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}\)
これより、\(23x+16y=1\) の整数解の \(1\) つは \((x~,~y)=(7~,~-10)\) となるので、上と同じようにして整数解を求める
\(23x+16y=3\) について、整数解の \(1\) つを求める。
\(23 \cdot 7+16 \cdot (-10)=1\) より、両辺を \(3\) 倍すると、
\(23 \cdot 21+16 \cdot (-30)=3\)
よって、\(23x+16y=3\) の整数解の \(1\) つは \((x~,~y)=(21~,~-30)\) である
\(23x+16y=3\) との差をとると、
\(\begin{eqnarray}~~~~~23x+16y&=&3\\-~\big{)}~~~23 \cdot 21+16 \cdot (-30)&=&3\\[3pt]\hline 23(x-21)+16(y+30)&=&0\end{eqnarray}\)
\(23(x-21)=-16(y+30)~~~\cdots {\small [\,5\,]}\)
\(23\) と \(16\) は互いに素より、\(x-21\) は \(16\) の倍数となるので、
整数 \(k\) を用いて、
\(\begin{eqnarray}~~~x-21&=&16k\\[3pt]~~~x&=&16k+21\end{eqnarray}\)
\({\small [\,5\,]}\) に \(x-21=16k\) を代入して、
\(\begin{eqnarray}~~~23 \cdot 16k&=&-16(y+30)\\[3pt]~~~-16(y+30)&=&16 \cdot 23k\\[3pt]~~~y+30&=&-23k\\[3pt]~~~y&=&-23k-30\end{eqnarray}\)
したがって、方程式 \(23x+16y=3\) の整数解は \(x=16k+21~,~y=-23k-30\) （\(k\) は整数）となる
【別解】ユークリッドの互除法の式を順に代入していく方法
\(23x+16y=3\) について、\(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\,]}\) より、\(\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\) となるので、両辺を \(3\) 倍すると、
\(23 \cdot 21+16 \cdot (-30)=3\)
これより、\(23x+16y=3\) の整数解の \(1\) つは \((x~,~y)=(21~,~-30)\) となるので、上と同じようにして整数解を求める
