-
![]()
547
演習 例題130 合同式の利用 累乗の数の余り
合同式を利用して、 次のものを求めよ。
0000
(1) (ア) 13100 9で割った余り
(2) 472011 の一の位の数
(イ) 20002000 を12で割った余り [(イ) 早稲田大]
[(2) 類 自治医大]
p.544 基本事項 3
4章
発展 合同式
指針 乗法に関する次の性質を利用する。
a=b (modm),c=d(modm) のとき
3 ac=bd (mod m) 4 自然数nに対しα=b (mod m)
(1)累乗の数に関する余りの問題では、余りの周期性に着目することがポイントであ
る。また, 合同式を利用して、 指数の底を小さくしてから, 周期性を調べると計算が
らくになる。
注意 αのαを指数の底という。
特に, "≡1(mod m) となるnが見つかれば、問題の見通しがかなり良くなる。
(2)ある自然数 N の一の位の数は,Nを10で割ったときの余りに等しい。 したがっ
て 10 を法とする剰余系を利用する。
CHART 累乗の数を割った余りの問題 余りの周期性に注目
(1) (ア) 134 (mod9) であり
解答
42=16=7 (mod 9). 43=64≡1(mod 9 )
ゆえに
4100=4•(43)33=4・133=4(mod9)
よって 13100=4100≡4 (mod9)
したがって 求める余りは 4
13-49 であるから, 13
と4は9を法として合同
であることに着目し、4"
に関する余りを調べる。
132 13 を9で割った余
りを調べてもよいが,
般に 42 43の方がらく。
2000 の計算は面倒。
-
2000を12で割った余り
は8であるから, 2000 と
8は12を法として合同。
したがって, 8" に関する
余りを調べる。
(イ) 2000=8 (mod12) であり
82=644 (mod 12),
8°=8・4=8 (mod12)
8'≡(82)2=42=4 (mod12)
ゆえに, kを自然数とすると
よって
82k=4 (mod12)
2000200082000=4(mod12)
したがって, 求める余りは 4
(2)477 (mod 10) であり
72=499 (mod 10),
<47=10・4+7
7°=9.7≡3(mod 10),
7=92=1 (mod 10 )
ゆえに
よって
72011 (74) 502.78=1502.3=1・3=3(mod 10 )
2011=4・502+3
472011=72011=3 (mod10)
したがって, 472011 の一の位の数は 3
合同式を利用して 次のものを求めて
