数学A 不定方程式 問題 8 解説

方針・初手

2つの余りの条件を合同式で表し、中国剰余定理の形に直す。まず $113$ で割った余りから $n=113k+7$ とおき、これを $11$ で割った余りの条件に代入する。

解法1

条件は

$$ n \equiv 7 \pmod{113}, \qquad n \equiv 10 \pmod{11} $$

である。

まず

$$ n=113k+7 $$

とおく。この式を $11$ を法として見ると、$113 \equiv 3 \pmod{11}$ であるから、

$$ n \equiv 3k+7 \pmod{11} $$

となる。

一方、条件より $n \equiv 10 \pmod{11}$ である。したがって

$$ 3k+7 \equiv 10 \pmod{11} $$

すなわち

$$ 3k \equiv 3 \pmod{11} $$

である。

$3$ と $11$ は互いに素なので、両辺を $3$ で割ることができ、

$$ k \equiv 1 \pmod{11} $$

を得る。

よって、ある整数 $m$ を用いて

$$ k=11m+1 $$

と書ける。これを $n=113k+7$ に代入すると、

$$ \begin{aligned} n &=113(11m+1)+7\\ &=1243m+120 \end{aligned} $$

となる。

したがって、条件を満たす整数はすべて

$$ n=1243m+120 \quad (m \in \mathbb{Z}) $$

で表される。

このうち負の整数で最大のものを求める。$m=0$ のとき

$$ n=120 $$

で正である。次に $m=-1$ とすると

$$ n=-1243+120=-1123 $$

で負になる。

$m$ をさらに小さくすると $n$ はさらに小さくなるので、負の整数のうち最大のものは

$$ n=-1123 $$

である。

次に、$n$ を $100$ で割った余りを求める。

$$ -1123=-1200+77 $$

であり、$77$ は $0$ 以上 $100$ 未満である。したがって、$100$ で割った余りは

$$ 77 $$

である。

解説

この問題では、まず2つの余りの条件を同時に満たす整数全体を求めることが重要である。

$113$ と $11$ は互いに素なので、条件を満たす整数は $113 \cdot 11=1243$ を法として一意に決まる。実際に計算すると

$$ n \equiv 120 \pmod{1243} $$

となる。

ただし、求めるのは正の最小値ではなく「負の整数のうち最大のもの」である。そのため、$120$ から $1243$ を1回引いた

$$ 120-1243=-1123 $$

が該当する。

答え

$$ n=-1123 $$

また、$n$ を $100$ で割った余りは

$$ 77 $$

である。