数学A 合同式 問題 3 解説

方針・初手

$7$ で割った余りを扱うので、合同式で計算する。中心になるのは $5^6 \equiv 1 \pmod{7}$ であり、これにより $5^n$ の余りは周期 $6$ で繰り返す。

解法1

まず $5^6$ を $7$ で割った余りを調べる。

$$ 5^2=25\equiv 4 \pmod{7} $$

$$ 5^3\equiv 5\cdot 4=20\equiv 6\equiv -1 \pmod{7} $$

したがって、

$$ 5^6=(5^3)^2\equiv (-1)^2=1 \pmod{7} $$

である。

(1)

任意の負でない整数 $n$ に対して、

$$ 5^{n+6}=5^n\cdot 5^6 $$

である。ここで $5^6\equiv 1 \pmod{7}$ だから、

$$ 5^{n+6}\equiv 5^n\cdot 1=5^n \pmod{7} $$

となる。

よって、

$$ \overline{5^{n+6}}=\overline{5^n} $$

が成り立つ。

(2)

(1)より、$\overline{5^n}$ は $n$ を $6$ で割った余りだけで決まる。そこで $n=0,1,2,3,4,5$ の場合を調べる。

$$ \begin{aligned} 5^0&\equiv 1 \pmod{7},\\ 5^1&\equiv 5 \pmod{7},\\ 5^2&\equiv 25\equiv 4 \pmod{7},\\ 5^3&\equiv 20\equiv 6 \pmod{7},\\ 5^4&\equiv 6\cdot 5=30\equiv 2 \pmod{7},\\ 5^5&\equiv 2\cdot 5=10\equiv 3 \pmod{7}. \end{aligned} $$

したがって、負でない整数 $n$ に対して、

$$ \overline{5^n}= \begin{cases} 1 & (n\equiv 0 \pmod{6}),\\ 5 & (n\equiv 1 \pmod{6}),\\ 4 & (n\equiv 2 \pmod{6}),\\ 6 & (n\equiv 3 \pmod{6}),\\ 2 & (n\equiv 4 \pmod{6}),\\ 3 & (n\equiv 5 \pmod{6}) \end{cases} $$

である。

(3)

まず $12192$ を $7$ で割った余りを求める。

$$ 12192=7\cdot 1741+5 $$

より、

$$ 12192\equiv 5 \pmod{7} $$

である。したがって、

$$ 12192^4\equiv 5^4 \pmod{7} $$

となる。

(2)より、

$$ 5^4\equiv 2 \pmod{7} $$

であるから、

$$ 12192^4\equiv 2 \pmod{7} $$

よって、$12192^4$ を $7$ で割った余りは $2$ である。

解説

この問題の要点は、累乗の余りが周期的に繰り返すことを示す点にある。$5^6\equiv 1 \pmod{7}$ が分かれば、指数を $6$ 増やしても余りが変わらないため、$5^n$ の余りは $n$ を $6$ で割った余りだけで決まる。

(3)では巨大な数をそのまま扱う必要はない。底である $12192$ をまず $7$ で割った余りに置き換え、$12192\equiv 5 \pmod{7}$ としてから累乗を考えればよい。

答え

(1)

$$ \overline{5^{n+6}}=\overline{5^n} $$

がすべての負でない整数 $n$ に対して成り立つ。

(2)

$$ \overline{5^n}= \begin{cases} 1 & (n\equiv 0 \pmod{6}),\\ 5 & (n\equiv 1 \pmod{6}),\\ 4 & (n\equiv 2 \pmod{6}),\\ 6 & (n\equiv 3 \pmod{6}),\\ 2 & (n\equiv 4 \pmod{6}),\\ 3 & (n\equiv 5 \pmod{6}) \end{cases} $$

(3)

$$ 2 $$