login
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
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)
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: A366782 A134142 A353390 * A138680 A171684 A123703
KEYWORD
nonn,hard,more
AUTHOR
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