OFFSET
0,1
COMMENTS
a(n) is the smallest k > 1 such that Phi_m(-k) has all its divisors == 1 (mod n) for all m > 1 dividing 2n+1, where Phi_m(x) are the cyclotomic polynomials.
By Schinzel's hypothesis H, a(n) exists for every n (see A298076).
If 2n+1 is a prime > 3, then a(n) = 2.
We have a(n)^(2n+1) == a(n) (mod 2n+1), so every composite number 2n+1 is a weak Fermat pseudoprime to base a(n).
a(n) >= A239452(2n+1).
a(42) requires factorization of a 132 digit composite. - M. F. Hasler, Oct 16 2018
From Kevin P. Thompson, Mar 30 2022: (Start)
Additional nontrivial terms: a(55) = 111, a(61) = 165, a(64) = 216, a(66) = 49.
a(49) >= 656811 (a C322 remains to be factored to verify k=656811).
a(52) >= 3547020 (a C288 remains to be factored to verify k=3547020).
a(57) >= 4900 (a C258 remains to be factored to verify k=4900).
a(58) > 784720.
a(59) >= 714 (a C299 remains to be factored to verify k=714).
a(60) >= 233 (a C240 remains to be factored to verify k=233).
a(62) >= 126 (a C191 remains to be factored to verify k=126). (End)
LINKS
FORMULA
a(n) = min{k > 1: for all prime p, if p | (k^(2n+1)+1)/(k+1) then p == 1 (mod 2n+1)}. - Kevin P. Thompson, Mar 18 2022
EXAMPLE
a(170) = 2 wherein 2*170 + 1 = 341 = 11*31 is the smallest psp(2).
From M. F. Hasler, Oct 15 2018: (Start)
a(0) = 2 is the least integer k > 1 for which (k+1)/(k+1) == 1 (mod 1). (Here we even have equality, but any integer is congruent to any other integer, modulo 1.)
a(1) = 3 is the least k > 1 for which (k^3+1)/(k+1) = k^2 - k + 1 = P3(-k) == 1 (mod 3). Indeed, P3(-3) = 7 == 1 (mod 3), while P3(-2) = 3 == 0 (mod 3). (End)
MATHEMATICA
Table[SelectFirst[Range[2, 100], AllTrue[Divisors[(#^(2 n + 1) + 1)/(# + 1)], Mod[#, 2 n + 1] == 1 &] &], {n, 21}] (* Michael De Vlieger, Feb 01 2018 *)
PROG
(PARI) isok(k, n) = {fordiv((k^(2*n+1)+1)/(k+1), d, if (Mod(d, (2*n+1)) != 1, return (0)); ); return(1); }
a(n) = {my(k = 2); while (!isok(k, n), k++); k; } \\ Michel Marcus, Jan 19 2018
(PARI) A298310(n)={n=n*2+1; for(k=2, oo, fordiv(n, m, m>1&&vecmax(factor(polcyclo(m, -k))[, 1]%n)!=1&& next(2)); return(k))} \\ M. F. Hasler, Oct 14 2018
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Thomas Ordowski and Krzysztof Ziemak, Jan 17 2018
EXTENSIONS
a(22) corrected by Robert Israel, Jan 18 2018
a(1) corrected by Michel Marcus, Jan 19 2018
a(27)-a(30) from Robert Price, Feb 17 2018
a(31)-a(41) from M. F. Hasler, Oct 15 2018
a(42)-a(48) from Kevin P. Thompson, Mar 18 2022
STATUS
approved