|
|
A211671
|
|
Least prime p such that the polynomial x^n - x^(n-1) -...- 1 (mod p) has n distinct zeros.
|
|
1
|
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
This is the characteristic polynomial of the n-step Fibonacci and Lucas sequences. For composite p, the polynomial can have more than n zeros! See A211672.
|
|
LINKS
|
|
|
EXAMPLE
|
For p = 11, x^2-x-1 = (x+3)(x+7) (mod p).
For p = 47, x^3-x^2-x-1 = (x+21)(x+30)(x+42) (mod p).
For p = 137, x^4-x^3-x^2-x-1 = (x+12)(x+79)(x+85)(x+97) (mod p).
|
|
MATHEMATICA
|
Clear[x]; Table[poly = x^n - Sum[x^k, {k, 0, n - 1}]; k = 1; While[p = Prime[k]; cnt = 0; Do[If[Mod[poly, p] == 0, cnt++], {x, 0, p - 1}]; cnt < n, k++]; p, {n, 5}]
|
|
PROG
|
(PARI)
N=10^9; default(primelimit, N);
a(n)={my(P=x^n-sum(k=0, n-1, x^k) ); forprime(p=2, N, if( #polrootsmod(P, p)==n, return(p) ) ); }
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|