ある3桁の整数を6で割ると3余り、13で割ると7余る。このような3桁の整数で最大のものを求めよ。

1. 問題の内容

ある3桁の整数を6で割ると3余り、13で割ると7余る。このような3桁の整数で最大のものを求めよ。

2. 解き方の手順

求める整数を $x$ とすると、問題文より以下の2つの式が成り立つ。

$x \equiv 3 \pmod{6}$

$x \equiv 7 \pmod{13}$

1つ目の式より、$x = 6k + 3$ ( $k$ は整数) と表せる。これを2つ目の式に代入すると、

$6k + 3 \equiv 7 \pmod{13}$

$6k \equiv 4 \pmod{13}$

$6k \equiv 4 \pmod{13}$ を解くために、6の逆元を求める。

$6 \times x \equiv 1 \pmod{13}$ となる $x$ を探す。

$6 \times 11 = 66 = 13 \times 5 + 1 \equiv 1 \pmod{13}$ より、6の逆元は11。

したがって、$k \equiv 4 \times 11 \pmod{13}$

$k \equiv 44 \pmod{13}$

$k \equiv 5 \pmod{13}$

よって、$k = 13m + 5$ ( $m$ は整数) と表せる。

$x = 6k + 3 = 6(13m + 5) + 3 = 78m + 30 + 3 = 78m + 33$

$x$ は3桁の整数であるから、$100 \le x \le 999$

$100 \le 78m + 33 \le 999$

$67 \le 78m \le 966$

$\frac{67}{78} \le m \le \frac{966}{78}$

$0.8589 \le m \le 12.3846$

$m$ は整数なので、$1 \le m \le 12$。

$x$ が最大になるのは、$m = 12$ のときである。

$x = 78 \times 12 + 33 = 936 + 33 = 969$

3. 最終的な答え

969