

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(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

Table of n, a(n) for n=0..48.
Kevin P. Thompson, Factorizations to support known terms of a(n) for n = 1..68


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

Cf. A239452, A298076 (see Ordowski's conjecture for b < 1 and odd n).
Sequence in context: A151863 A134142 A353390 * A138680 A171684 A123703
Adjacent sequences: A298307 A298308 A298309 * A298311 A298312 A298313


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



