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

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

Offset: 0

Author

Thomas Ordowski and Krzysztof Ziemak, Jan 17 2018

Keywords

• nonn
• hard
• more

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)

Examples

			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)
		

Links

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

Crossrefs

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

Programs

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 *)

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

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

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