A352597 a(n) is the smallest k > 1 such that k^n + 1 has all prime divisors p == 1 (mod n).

2, 2, 6, 2, 10, 6, 28, 2, 18, 10, 22, 6, 52, 14, 60, 2, 102, 36, 190, 20, 756, 66, 46, 18, 2550, 26, 2970, 28, 58, 120, 310, 2, 330, 170, 11550, 6, 148, 570, 156, 140, 82, 2184, 172, 88, 3040020, 184, 282, 42, 7252, 110, 7548, 312, 106, 1440, 41800, 42, 11172

Offset: 1

Author

Kevin P. Thompson, Mar 21 2022

Keywords

• nonn
• hard

Comments

Equivalently, a(n) is the smallest k > 1 such that for all divisors d of k^n + 1, d == 1 (mod n).

A298299 is a subsequence.

All terms in this sequence are even since for odd k the expression k^n + 1 is divisible by 2 which is not congruent to 1 (mod n) for any n > 1.

If n is odd, a(n)^n + 1 is divisible by a(n) + 1. Therefore, a(n) + 1 == 1 (mod n) and so n | a(n) for odd n.

Theorem: a(n) = 2 if and only if n is a power of 2.

Examples

			a(3) = 6 since 6^3 + 1 = 217 = 7 * 31 and both factors are congruent to 1 (mod 3).
		

Crossrefs

Cf. A298076, A298299 (bisection), A298310, A298398.

Programs

PARI

isok(k,n) = my(f=factor(k^n+1)); for (i=1, #f~, if (Mod(f[i,1], n) != 1, return(0))); return(1);
a(n) = my(k=2); while (!isok(k, n), k+=2); k; \\ Michel Marcus, Mar 22 2022

Formula

a(2n) = A298299(n).