(1) bn は an を p で割った余りであるから an≡bn(modp) である。同様に an+1≡bn+1(modp) である。したがって an+1≡bn+1(modp) であり、積についても an+1(an+1)≡bn+1(bn+1)(modp) が成り立つ。
漸化式より an+2=an+1(an+1) だから、an+2 を p で割った余り、すなわち bn+2 は、bn+1(bn+1) を p で割った余りと一致する。
(2) r=2 なので b1=2,b2=3 である。(1) の結果を使って順に計算する。 b3≡b2(b1+1)=3(2+1)=9(mod17) より b3=9 である。次に b4≡b3(b2+1)=9(3+1)=36≡2(mod17) より b4=2 である。さらに b5≡b4(b3+1)=2(9+1)=20≡3(mod17) より b5=3 である。
ここで (b4,b5)=(2,3)=(b1,b2) となった。以後は同じ漸化式で決まるので、余りは 2,3,9 を周期として繰り返す。したがって、10 以下の自然数 n に対してnbn122339425369728399102である。
(3)
仮定より bn+1=bm+1>0,bn+2=bm+2 である。c=bn+1=bm+1 とおくと、c は p で割った余りであり、0<c<p である。
(1) より bn+2≡bn+1(bn+1)=c(bn+1)(modp) であり、同様に bm+2≡bm+1(bm+1)=c(bm+1)(modp) である。bn+2=bm+2 だから c(bn+1)≡c(bm+1)(modp) である。両辺を引いて c(bn−bm)≡0(modp) を得る。
ここで p は素数で、c は p で割り切れない。したがって bn−bm≡0(modp) である。bn,bm はどちらも 0 以上 p−1 以下の整数なので、合同であることから bn=bm が従う。
Evolton