ここでは1次不定方程式の整数解を利用する問題について説明します。
1次不定方程式の解き方について，この記事ではそれほど詳しく説明していないため，「1次不定方程式って何それ？」という方は次の記事から知識を吸収してください。
Contents
余りの条件から整数を求める問題
ヒロ
まずは丁寧な誘導がある問題を解くことで考え方に慣れよう。
2020年 名城大46で割ると余りが7であり，97で割ると余りが11であるような自然数のうち，4桁で最大のものを $n$ とする。以下，$n$ を求めたい。
条件から，$n$ は自然数 $x,~y$ を用いて，
条件から，$n$ は自然数 $x,~y$ を用いて，
\begin{align*}
n=46x+7=97y+11
\end{align*}
と表される。これを整理すると，n=46x+7=97y+11
\end{align*}
\begin{align*}
46x-97y=\myhako
\end{align*}
となる。このとき，46と97についての互除法の計算より，46x-97y=\myhako
\end{align*}
\begin{align*}
1&=46-\myBox{ア}\times\myhako \\[4pt]
&=46-\mybox{ア}\times\left(97-\myhako\times46\right) \\[4pt]
&=\myhako\times46-\myhako\times97
\end{align*}
が成り立つ。よって，1&=46-\myBox{ア}\times\myhako \\[4pt]
&=46-\mybox{ア}\times\left(97-\myhako\times46\right) \\[4pt]
&=\myhako\times46-\myhako\times97
\end{align*}
\begin{align*}
46\left(x-\myBox{イ}\right)=97\left(y-\myBox{ウ}\right)
\end{align*}
となる。ただし，$0\leqq\mybox{イ}<97$, $0\leqq\mybox{ウ}<46$ とする。46と97は互いに素であるから，$x$ は整数 $k$ を用いて 46\left(x-\myBox{イ}\right)=97\left(y-\myBox{ウ}\right)
\end{align*}
\begin{align*} x=97k+\myhako \end{align*}
と表される。$n$ の最大性より，$n=\myhako$ である。【考え方と解答】
誘導に乗って解いていこう。 $46x+7=97y+11$ より
誘導に乗って解いていこう。 $46x+7=97y+11$ より
\begin{align*} 46x-97y=4 \end{align*}
互除法の計算をしていく。\begin{align*} &97=46\times2+5 \\[4pt] &46=5\times9+1 \end{align*}
この計算結果から\begin{align*} 1&=46-9\times5 \\[4pt] &=46-9\times(97-2\times46) \\[4pt] &=19\times46-9\times97 \end{align*}
が成り立つ。両辺に4をかけて \begin{align*} 46\times76-97\times36=4 \end{align*}
したがって\begin{align*} &46(x-76)-97(y-36)=0 \\[4pt] &46(x-76)=97(y-36) \end{align*}
46と97は互いに素であるから，整数 $k$ を用いて\begin{align*} &x-76=97k \\[4pt] &x=97k+76 \end{align*}
と表される。このとき \begin{align*} n&=46(97k+76)+7 \\[4pt] &=4462k+3503 \end{align*}
$n$ が4桁で最大の整数になるのは $k=1$ のときであり，このとき\begin{align*} n=4462+3503=7965 \end{align*}