４番
r を 0 以上の整数とし、数列 {an } を次のように定める。
a1 = r, a2 = r + 1, an+2 = an+1 (an + 1) (n = 1, 2, 3, · · ·)
また、素数 p を１つとり、an を p で割った余りを bn とする。ただし、0 を p で
割った余りは 0 とする。
(1) 自然数 n に対し、bn+2 は bn+1 (bn + 1) を p で割った余りと一致することを
示せ。
(2) r = 2, p = 17 の場合に、10 以下のすべての自然数 n に対して、bn を求めよ。
(3) ある２つの異なる自然数 n, m に対して、
bn+1 = bm+1 > 0, bn+2 = bm+2
が成り立ったとする。このとき、bn = bm が成り立つことを示せ。
【2014 東京大学文系】
解答
(1) an+1 = pQ1 + bn+1 , an = pQ2 + bn とおくと、
an+2 = an+1 (an + 1)
= (pQ1 + bn+1 ) (pQ2 + bn + 1)
= pM + bn+1 (bn + 1)
∴ bn+2 ≡ bn+1 (bn + 1) (modp)
よって、bn+2 は bn+1 (bn + 1) を p で割った余りと一致する。
(2) r = 2, p = 17 の場合。(1) の結果を利用して、下表を得る。
n
1
2
3
4
5
6
7
8
9
10
bn
2
3
9
2
3
9
2
3
9
2
(3)
bn+1 = bm+1 = r1 > 0, bn+2 = bm+2 = r2
のとき、
r2 ≡ r1 (bn + 1) (modp)
r2 ≡ r1 (bm + 1) (modp)
r1 (bn + 1) ≡ r1 (bm + 1) (modp)
⇔ r1 (bn − bm ) ≡ 0 (modp)
c
Darumafactory
-1-
RadicalMath
ここに、0 < r1 < p, p, r は互いに素であるから、
bn − bm ≡ 0 (modp)
⇔ bn = bm
c
Darumafactory
-2-
RadicalMath
© Copyright 2024 ExpyDoc
![，V [ ¯X] = σ k] E[X E[(Xk − µ)(X ` − µ)] = E[X k X` − µ X k − µ X ` + µ2](http://s3.expydoc.com/store/data/007469701_1-a520c1e7aece68d9fe23460b1ac01f56-250x500.png)
![シュレディンガー作用素 H に対して, [T,H]=](http://s3.expydoc.com/store/data/007399069_1-ac85ef6aa09ec69b7f8f9c0887e1ad3c-250x500.png)
![H26厚木基地に関する要望書 [PDFファイル： 1223.4KB]](http://s3.expydoc.com/store/data/007338754_1-87edd7ddcb214ba43d6f51062df6b294-250x500.png)
