数学A 合同式 問題 5 解説

方針・初手

$13$ で割った余りを扱うので、合同式の考え方を使う。特に $a \equiv r(a) \pmod{13}$ であることから、積をとったときの余りも、余り同士の積から求められる。

解法1

(1)

整数 $a,b$ に対して、$a$ を $13$ で割った余りが $r(a)$、$b$ を $13$ で割った余りが $r(b)$ であるから、ある整数 $m,n$ を用いて

$$ a=13m+r(a),\qquad b=13n+r(b) $$

と表せる。

このとき

$$ \begin{aligned} ab &=(13m+r(a))(13n+r(b))\\ &=13(13mn+mr(b)+nr(a))+r(a)r(b) \end{aligned} $$

である。したがって、$ab$ と $r(a)r(b)$ は $13$ で割った余りが等しい。

よって

$$ r(ab)=r(r(a)r(b)) $$

である。

(2)

まず

$$ 2^3=8 $$

であるから

$$ r(2^3)=8 $$

である。

次に

$$ 2^6=64=13\cdot 4+12 $$

より

$$ r(2^6)=12 $$

である。

また、(1)を用いると

$$ r(2^{12})=r\left((2^6)^2\right)=r(12^2) $$

である。ここで

$$ 12^2=144=13\cdot 11+1 $$

より

$$ r(2^{12})=1 $$

である。

(3)

(2)より

$$ r(2^{12})=1 $$

である。したがって、$2^{12}$ は $13$ で割ると余りが $1$ である。

また

$$ 2019=12\cdot 168+3 $$

であるから、

$$ 2^{2019}=(2^{12})^{168}\cdot 2^3 $$

と書ける。

よって、(1)を繰り返し用いると

$$ r(2^{2019})=r(1^{168}\cdot 8)=8 $$

である。

(4)

まず、$n=0,1,2,\ldots,11$ に対して $r(2^n)$ を順に求める。

$$ \begin{aligned} r(2^0)&=1,\\ r(2^1)&=2,\\ r(2^2)&=4,\\ r(2^3)&=8,\\ r(2^4)&=r(16)=3,\\ r(2^5)&=r(32)=6,\\ r(2^6)&=12,\\ r(2^7)&=r(24)=11,\\ r(2^8)&=r(22)=9,\\ r(2^9)&=r(18)=5,\\ r(2^{10})&=r(10),\\ r(2^{11})&=r(20)=7. \end{aligned} $$

したがって

$$ r(2^0),r(2^1),\ldots,r(2^{11}) $$

は

$$ 1,2,4,8,3,6,12,11,9,5,10,7 $$

であり、これは $1$ 以上 $12$ 以下の整数をすべてちょうど一度ずつ含んでいる。

さらに、(2)より $r(2^{12})=1$ であるから、任意の $n\geqq 0$ について

$$ r(2^{n+12})=r(2^n\cdot 2^{12})=r(r(2^n)\cdot 1)=r(2^n) $$

である。

つまり、$r(2^n)$ は周期 $12$ で同じ値を繰り返す。よって $n$ が $0$ 以上の整数全体を動くとき、$r(2^n)$ は $1$ 以上 $12$ 以下のすべての整数の値をとる。

解説

この問題の中心は、余りの計算を合同式として扱うことである。

(1)は、余り同士をかけてからさらに余りを取ればよい、という性質の確認である。この性質により、大きな指数の計算でも実際に巨大な数を計算する必要がなくなる。

(3)では、$r(2^{12})=1$ を利用して指数を $12$ で割った余りに注目する。$2019$ を $12$ で割ると余りが $3$ なので、結局 $2^{2019}$ の余りは $2^3$ の余りと同じになる。

(4)では、$n=0$ から $11$ までを調べれば十分である。なぜなら $r(2^{12})=1$ により、以後は同じ並びが繰り返されるからである。

答え

(1)

$$ r(ab)=r(r(a)r(b)) $$

が成り立つ。

(2)

$$ r(2^3)=8,\qquad r(2^6)=12,\qquad r(2^{12})=1 $$

(3)

$$ r(2^{2019})=8 $$

(4)

$n$ が $0$ 以上の整数全体を動くとき、$r(2^n)$ は

$$ 1,2,3,\ldots,12 $$

のすべての値をとる。