◆広島県 清川 育男 さんからのコメント。
数列サイトで検索しました。
「Perrin pseudoprimes」 と言うそうです。
ID Number: A013998
Sequence:
271441,904631,16532714,24658561,27422714,27664033,
46672291,102690901,130944133,196075949,214038533,
517697641,545670533,801123451,855073301,903136901,
970355431
Name: Unrestricted Perrin pseudoprimes.
Comments:
"The column Mathematical Recreations by Ian Stewart in the June issue of Scientific American discusses the Perrin sequence [A001608] A(n) with: A(0)=3, A(1)=0, A(2)=2, A(n+1)=A(n-1)+A(n-2). Motivated by a theorem of E. Lucas: If n is prime it divides A(n) exactly, the question
whether primality of n follows from n divides A(n) exactly was formulated 1899. So far, they say, nobody has found a composite n that divides A(n). Such a number would be called a Perrin pseudoprime. The article quotes an experiment by Steven Arno of the Supercomputing Research Center in Bowie, Md., where a lower bound of 15 digits for the size of the smallest Perrin pseudoprime was obtained in 1991. On July 3rd, 1996, I was able to find the two smallest Perrin pseudoprimes:" - Holzbaur References W. W. Adams and D. Shanks, Strong primality tests that are not sufficient, Math. Comp. 39 (1982), 255-300.
Links:
Christian Holzbaur, Perrin pseudoprimes
E. W. Weisstein, Link to a section of The World of Mathematics.
Index entries for sequences related to pseudoprimes
◆東京都 Air さんからの解答。
| n:素数⇒ | ｆ(ｎ) ｎ |
:自然数・・(*) は真で、 |
| ｆ(ｎ) ｎ |
:自然数⇒n:素数 は偽です。 |
逆の反例としては、n=27664033=3037・9109 などがあるようです。
（参考URL：http://www.mathpages.com/home/kmath345.htm）
調べただけだと物足りないので、以下では(*)を示してみます。
まず、f(n)=f(n-2)+f(n-3) (n≧4)の一般項を求めることを考えます。
漸化式の一般論から、この4項間漸化式に対応する特性方程式、
x3-x-1=0 の解をα,β,γとするとき、
f(n)=aαn+bβn+cγn
（∃a,b,c∈C）
と書けます。
ここで、条件f(1)=0,f(2)=2,f(3)=3 から、a,b.cを決定しましょう。
f(1)=aα+bβ+cγ=0・・(1)
f(2)=aα2+bβ2+cγ2=2・・(2)
f(3)=aα3+bβ3+cγ3
=a(α+1)+b(β+1)+c(γ+1)=a+b+c(∵(1))=3・・(3)
(1)〜(3)を連立させてa,b,cを求めます。
詳細は省略しますが、連立方程式を行列表示して、クラメルの公式、
及びx3-x-1=0の解と係数の関係、即ち、
α+β+γ=0 αβ+βγ+γα=-1 αβγ=1
及び、α3=α+1等を使えば、a=b=c=1と求まります。
従って、f(n)=αn+βn+γn となることが分かりました。
ゆえに、p:素数とすると、
f(p)=αp+βp+γp
| =(α+β+γ)p-p・納 | (p-1)! i!j!k! |
αiβjγk] |
すると、納〜〜] 部分は、x3-x-1=0の解α,β,γの対称式なので、基本対称式によって表されます。
今、α,β,γの基本対称式は、解と係数の関係から上にも書いたように全て整数の値を持ちます。
従って納〜〜]も整数です。
従って、f(p)≡(α+β+γ)p=0p=0(mod p)
| ゆえに、 | f(p) p |
は自然数となります。 |