A253236 The unique prime p <= n such that n-th cyclotomic polynomial has a root mod p, or 0 if no such p exists.

0, 2, 3, 2, 5, 3, 7, 2, 3, 5, 11, 0, 13, 7, 0, 2, 17, 3, 19, 5, 7, 11, 23, 0, 5, 13, 3, 0, 29, 0, 31, 2, 0, 17, 0, 0, 37, 19, 13, 0, 41, 7, 43, 0, 0, 23, 47, 0, 7, 5, 0, 13, 53, 3, 11, 0, 19, 29, 59, 0, 61, 31, 0, 2, 0, 0, 67, 17, 0, 0, 71, 0

Offset

1,2

Comments

There is at most one prime p <= n such that n-th cyclotomic polynomial has a root mod p.

For prime n and every natural number k, a(n^k) = n.

If a(n) != 0, then a(n)|n.

a(n) is either 0 or A006530(n). See Corollary 23 of the Shevelev et al. link. - Robert Israel, Sep 07 2016

Links

Eric Chen and Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 1500 terms from Chen)

V. Shevelev, G. Garcia-Pulgarin, J. M. Velasquez-Soto and J. H. Castillo, Overpseudoprimes, and Mersenne and Fermat Numbers as Primover Numbers, J. of Integer Sequences, Vol. 15 (2012), Art. 12.7.7.

Maple

N:= 1000: # to get a(1) to a(N)
f:= proc(n) local p, x, C, v;
    C:= numtheory:-cyclotomic(n, x);
    p:= max(numtheory:-factorset(n));
    for v from 0 to p-1 do
      if eval(C, x=v) mod p = 0 then return p fi
    od:
    0
end proc:
f(1):= 0:
seq(f(n), n=1..N); # Robert Israel, Sep 07 2016

Mathematica

a[n_] := Module[{p, x, c, v}, c[x_] = Cyclotomic[n, x]; p = FactorInteger[ n][[-1, 1]]; For[v=0, v<p, v++, If[Mod[c[v], p] == 0, Return[p]]]; 0];
a[1] = 0;
Array[a, 100] (* Jean-François Alcover, Jul 27 2020, after Maple *)

Prog

(PARI) a(n) = forprime(p=2, n, if(#polrootsmod(polcyclo(n), p), return(p)))
(PARI) a(n)=my(P=polcyclo(n), f=factor(n)[, 1]); for(i=1, #f, if(#polrootsmod(P, f[i]), return(f[i]))); 0 \\ Charles R Greathouse IV, Apr 07 2015

Crossrefs

For a(n) = 0, see A253235.

For a(n) = 2, see A000079.

For a(n) = 3, see A038754.

For a(n) = 5, see A245478.

For a(n) = 7, see A245479.

For a(n) = 11, see A245480.

For a(n) = 13, see A245481.

Cf. A006530.

Sequence in context: A076690 A262549 A086287 * A342257 A286516 A273289

Adjacent sequences: A253233 A253234 A253235 * A253237 A253238 A253239

Keyword

nonn

Author

Eric Chen, Apr 07 2015

Status

approved