ここでは不定方程式の整数解に関する問題について説明します。
不定方程式の係数が大きくなると，整数解の1つを見つけることが難しくなります。
そんな場合には，ユークリッドの互除法を利用することで機械的に整数解を見つけることができます。
互除法を知らない人は，次の記事を読んで下さい。
Contents
不定方程式の問題【立教大】
2020年 立教大方程式 $37x+15y=1$ の整数解 $x,~y$ について，$x$ を15で割った余りは $\myhako$ であり，$y$ を37で割った余りは $\myhako$ である。
【考え方と解答】
まずは整数解の1つを求めよう。見つけるのに苦労する場合は，ユークリッドの互除法を利用しよう。今回は互除法を利用する方法で解くことにする。37と15の最大公約数は1ということが分かるが，37と15の最大公約数を互除法で求める計算をしていく。
まずは整数解の1つを求めよう。見つけるのに苦労する場合は，ユークリッドの互除法を利用しよう。今回は互除法を利用する方法で解くことにする。37と15の最大公約数は1ということが分かるが，37と15の最大公約数を互除法で求める計算をしていく。
\begin{align*}
&37=15\times2+7~\cdots\cdots① \\[4pt]
&15=7\times2+1~\cdots\cdots②
\end{align*}
①と②を利用して「$37\times\bigcirc+15\times\bigtriangleup=1$」の形の等式を作る。②より&37=15\times2+7~\cdots\cdots① \\[4pt]
&15=7\times2+1~\cdots\cdots②
\end{align*}
\begin{align*}
1=15-7\times2~\cdots\cdots②’
\end{align*}
①より1=15-7\times2~\cdots\cdots②’
\end{align*}
\begin{align*}
7=37-15\times2
\end{align*}
となるから，これを$②’$に代入すると7=37-15\times2
\end{align*}
\begin{align*}
1&=15-(37-15\times2)\times2 \\[4pt]
&=15\times5-37\times2
\end{align*}
よって，$37\times(-2)+15\times5=1$ となるから，与えられた方程式の1つの整数解 $x=-2,~y=5$ を見つけることができる。与えられた方程式 $37x+15y=1$ と辺々の差をとることで1&=15-(37-15\times2)\times2 \\[4pt]
&=15\times5-37\times2
\end{align*}
\begin{align*}
&37(x+2)+15(y-5)=0
\end{align*}
と変形できる。37と15が互いに素であるから，整数 $k$ を用いて&37(x+2)+15(y-5)=0
\end{align*}
\begin{align*}
\begin{cases}
x+2=15k \\[4pt]
y-5=-37k
\end{cases}
\end{align*}
と表すことができる。よって，与えられた方程式の整数解は\begin{cases}
x+2=15k \\[4pt]
y-5=-37k
\end{cases}
\end{align*}
\begin{align*}
x=15k-2,~y=-37k+5
\end{align*}
と表せる。x=15k-2,~y=-37k+5
\end{align*}
\begin{align*}
x&=15k-2 \\[4pt]
&=15(k-1)+13
\end{align*}
と変形することで，$x$ を15で割った余りは13であることが分かる。また $y$ を37で割った余りは5である。x&=15k-2 \\[4pt]
&=15(k-1)+13
\end{align*}