難しい数列の問題

質問

f(x)=x^2+px+q（p,qは自然数の定数）に対して
a(1)=1, a(n+1)=f(an)
で定義される数列｛An｝がある。

(1)q=p^3-2p^2　の時、a( 3)をpで割った余りを求めよ。
(2)Anを3で割った余りをBn（bn=0,1,2）とする。b（n+1）-f（bn）は3の倍数であることを示せ。
(3)1≦p≦3m,　1≦q≦3m（mは自然数）とする。このとき｛An｝のすべての項が
3で割り切れないような（p,q）の組の数をmで示せ。

という問題で、

(1)
（mod p）として、（合同式だけは大数で勉強しましたが他は高校レベルです）
a(2)＝p+q+1
a(3)＝（p+q+1）^2+p（p+q+1）+q
　　＝（p^3-2p^2+p+1）^2+p（p^3-2p^2+p+1）+p^3-2p^2
　　≡1　（∵p≡0）

∴余りは　1

(2)
(ⅰ)bn=1のとき
（mod 3）として、
a(n)=a(n-1)^2+pa(n-1)+q≡1

これ以降（(2)以降）が分かりません。
(2)は合同式は使わないと思いますが一応分かる分だけ書いてみました。
答えを教えていただける方よろしくお願いいたします。

回答No.2

Meowth · ベストアンサー

bn=α(α＝０、１、２）
とすると、
an=３k+α
an+1=(3k+α）^22+p(3k+α)+q
=3(3k^2+2kα+pk)+α^2+pα+q
したがって
an+1＝＝α^2+pα+q　（mod p）　＝＝は合同
bn+1はα^2+pα+qを３で割ったときのあまりに等しい
bn+1＝＝α^2+pα+q　（mod p）　
f(bn)＝α^2+pα+q
だから、
f(bn)＝＝α^2+pα+q　（mod p）
したがって、
b（n+1）-f（bn）
は、３の倍数

(3)
bn=1のとき　bn+1=1+p+q を３で割ったあまり
bn=2のとき　bn+1=4+2p+qを３でわったあまり
　　=1+2p+pを３でわったあまり
b1=1
だから、｛An｝のすべての項が3で割り切れない
すなわち、bnが0とならないためには、
p+q==2 (mod 3)でない
2p+q==2(mod 3)でない
ことが必要で、かつ、この条件を満たせば、bn=0となることはない。
2つの条件から
(1)p==0 のとき q== 0,1 かつ0,1 →q==0,1
(2)p==1 のとき　q==0,2 かつ 1,2 →q==2
(3) p=2 のとき　q==　0,1 かつ 0,2 →q==0
1≦p≦3m,　1≦q≦3m（mは自然数）では、
p==0,p==1,p==2 q==0,q==1,q==2 それそれm個ある
(1-1) p==0,q==0
m個のpのそれぞれにm個のqが対応　　m^2個
(1-2)　p==0,q==１
　　　m個のpのそれぞれにm個のqが対応　m^2個
(2)、(3)　　同様に　m^2個づつ
合計　4m^2

お礼

ありがとうございます。
(2)は分かりました。
(3)は難しいですね・・・メモしておいてゆっくり考えてみます。

回答No.1

Tacosan

(2) は
a(n) ≡ b(n) (mod 3)
を使えば簡単ですね.

お礼

ありがとうございます。(2)が解けました。