

A298310


Least k > 1 such that all divisors d of (k^(2n+1)+1)/(k+1) satisfy d == 1 (mod 2n+1).


3



2, 3, 2, 2, 9, 2, 2, 15, 2, 2, 15, 2, 32, 81, 2, 2, 55, 21, 2, 39, 2, 2, 4141, 2, 18, 51, 2, 551, 39, 2, 2, 21267, 21, 2, 1012, 2, 2, 826, 330, 2, 729, 2, 136, 204, 2, 3, 280, 20, 2
(list;
graph;
refs;
listen;
history;
text;
internal format)



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(42) requires factorization of a 132 digit composite.  M. F. Hasler, Oct 16 2018
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).
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

Cf. A239452, A298076 (see Ordowski's conjecture for b < 1 and odd n).


KEYWORD

nonn,hard,more


AUTHOR



EXTENSIONS



STATUS

approved



