余りの条件と1次不定方程式

整数 \(x~,~y\) を用いて、自然数 \(n\) は \(7\) で割ると \(3\) 余るので、

---

　\(n=7x+3~~~\cdots {\small [\,1\,]}\)

---

\(5\) で割ると \(1\) 余るので、

---

　\(n=5y+1~~~\cdots {\small [\,2\,]}\)

---

\({\small [\,1\,]}~,~{\small [\,2\,]}\) より、

---

　\(\begin{eqnarray}~~~7x+3&=&5y+1\\[3pt]~~~7x-5y&=&-2~~~\cdots {\small [\,3\,]}\end{eqnarray}\)

---

\(x=-1~,~y=-1\) は \(7x-5y=-2\) の整数解の \(1\) つであるので、

---

　\(7 \cdot (-1)-5 \cdot (-1)=-2~~~\cdots {\small [\,4\,]}\)

---

\({\small [\,3\,]}-{\small [\,4\,]}\) より、

---

　\(\begin{eqnarray}~~~~~7x-5y&=&-2\\-~\big{)}~~~7 \cdot (-1)-5 \cdot (-1)&=&-2\\[3pt]\hline 7(x+1)-5(y+1)&=&0\end{eqnarray}\)

---

　\(7(x+1)=5(y+1)\)

---

\(7\) と \(5\) は互いに素より、\(x+1\) は \(5\) の倍数となるので、
整数 \(k\) を用いて、

---

　\(\begin{eqnarray}~~~x+1&=&5k\\[3pt]~~~x&=&5k-1\end{eqnarray}\)

---

\({\small [\,1\,]}\) に代入すると、

---

　\(\begin{eqnarray}~~~n&=&7 \cdot (5k-1)+3\\[3pt]~~~&=&35k-7+3\\[3pt]~~~&=&35k-4\end{eqnarray}\)

---

\(3\) 桁の自然数となるので、

---

　\(\begin{eqnarray}~~~35k-4&{\small ~≧~}&100\\[3pt]~~~35k&{\small ~≧~}&104\\[3pt]~~~k&{\small ~≧~}&\displaystyle \frac{\,104\,}{\,35\,}=2.97\cdots\end{eqnarray}\)

---

これを満たす最小の \(k\) は \(k=3\) であるので、

---

　\(\begin{eqnarray}~~~n&=&35 \cdot 3-4\\[3pt]~~~&=&105-4\\[3pt]~~~&=&101\end{eqnarray}\)

---

したがって、\(3\) 桁で最小の自然数 \(n\) は \(101\) となる