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