基礎問題集
数学A 整数問題「合同式」の問題5 解説
数学Aの整数問題「合同式」にある問題5の基礎問題と解説ページです。問題と保存済み解説を公開し、ログイン後はAI質問と学習履歴も利用できます。
MathGrAIl の基礎問題集にある公開問題ページです。ログイン前でも問題と保存済み解説を確認でき、ログイン後はAI質問と学習履歴の保存を利用できます。
- 基礎問題の問題画像と保存済み解説を公開
- ログイン後にAI質問で復習
- ログイン後に学習履歴を保存
解説
方針・初手
$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
$$
のすべての値をとる。