-
![]()
-
![]()
は
る)。
D
a
うる。
る。
)
pk
k
2
2
演習 例題 122 合同式の利用・・・ 累乗の数の余り
合同式を利用して,次のものを求めよ。
ア) 13100 9で割った余り (イ) 20002000を12で割った余り [(イ) 早稲田大〕
(2) 472011 の一の位の数
(2) 類 自治医大]
指針 乗法に関する次の性質を利用する。
a=b (mod m), c=d (mod m) のとき
3ac=bd (mod m)
(1) 累乗の数に関する余りの問題では、余りの周期性に着目することがポイントである。
また、合同式を利用して、 指数の底を小さくしてから, 周期性を調べると計算がらくに
なる。 ･･････ 注意 α” のα を指数の底という。
解答
(1) (ア) 134 (mod9) であり
4² 16 7 (mod 9), 4°=64=1 (mod 9 )
ゆえに |42100=4.(43)=4 (mod9)
特に,a=1 (mod m) となるようなnが見つかれば、問題の見通しがかなり良くなる。
(2) ある自然数Nの一の位の数は, N10で割ったときの余りに等しい。 したがって,
10 を法とする剰余系を利用する。
CHART 累乗の数を割った余りの問題 余りの周期性に注目
よって
したがって 求める余りは 4
13100=4100=4 (mod9 )
4 自然数nに対し α"=6" (mod m)
(イ) 2000=8 (mod12) であり
8°=8.4=8 (mod 12),
ゆえに,kを自然数とすると
よって
82=64=4 (mod 12),
8'=(82)=42=4(mod 12)
82k4 (mod12)
20002000=820004 (mod12)
したがって 求める余りは
(2) 477 (mod10) であり
7³ 9-7=3 (mod 10),
ゆえに
よって
472011 720113 (mod10)
したがって 47 2011 の一の位の数は
7
72 49=9 (mod 10),
7=92=1 (mod 10)
72011 (74) 502.73 1502.3=1-3=3 (mod 10)
00000
p.492 基本事項 [③3]
3
次のものを求めよ｡
13-49 であるから, 13
と4は9を法として合同で
あることに着目し, 4 に関
する余りを調べる。
132, 13 を9で割った余り
を調べてもよいが, 一般に
42 4の方がらく。
2000" の計算は面倒。
2000 12で割った余りは
8 であるから 2000 と8は
12 を法として合同。
したがって, 8" に関する余
りを調べる。
47=10・4+7
2011=4・502+3
15245
(イ) 30003000 を14で割った余り
495
4章
19
発展合同式
る｡
る。
2)
-1)
でる
たと
は、
は,
な
満
3進
