A367566 a(n) is the product of the primes p <= n+1 such that n * k^n == +-1 (mod p) for every k that is not a multiple of p.

2, 3, 2, 15, 6, 35, 6, 3, 2, 33, 6, 13, 6, 15, 14, 255, 6, 19, 6, 3, 2, 69, 6, 5, 6, 15, 14, 87, 6, 31, 6, 3, 2, 15, 6, 1295, 6, 3, 2, 123, 6, 43, 6, 15, 22, 705, 6, 7, 6, 3, 2, 159, 6, 5, 6, 15, 14, 177, 6, 61, 6, 3, 2, 15, 66, 4355, 6, 3, 14, 213, 6, 73, 6

Offset: 1

Author

Jon E. Schoenfield, Nov 23 2023

Keywords

• nonn

Comments

By definition, all terms are squarefree. However, not all squarefree numbers are present.

a(n) = 1 first occurs at n = 252.

If n+1 = p is a prime, then for every k that is not a multiple of p, k^n == 1 (mod p), so n * k^n == -1 (mod p), so p divides a(n).

a(n) is even iff n is odd; 3 | a(n) iff 3 !| n and n > 1; and for primes p > 3, p | a(n) iff n == +-(p-1) (mod p*(p-1)/2). It follows that no term is divisible by q*r where q and r are primes and 2*q | r-1.

If A239735(n) > 1 then a(n) divides A239735(n); this can make it practical to find large terms of A239735. E.g., A239735(46) = 15044700, but since a(46) = 705 (see Example section), only the first 15044700/705 = 21340 multiples of 705 need to be tested. (Additionally, almost 90% of those multiples can be quickly ruled out by testing whether (46 * k^46) mod q = 1 or q-1 for any prime q < 2500, leaving fewer than 2200 remaining numbers k for which to test whether 46 * k^46 - 1 and 46 * k^46 + 1 are probable primes.)

Examples

			For n = 46, n+1 = 47 is a prime, so 46 * k^46 == -1 (mod p) for every k that is not a multiple of 47, so 47 divides a(46). Additionally, 46 * k^46 == 1 (mod 3) if k !== 0 (mod 3), so 3 divides a(46), and 46 * k^46 == +-1 (mod 5) if k !== 0 (mod 5), so 5 also divides a(46). Since 3, 5, and 47 are the only primes p such that 46 * k^46 == +-1 (mod p) for all k !== 0 (mod p), a(46) = 3*5*47 = 705.
		

Links

• Jon E. Schoenfield, Table of n, a(n) for n = 1..10000
• Jon E. Schoenfield, Magma program.

Crossrefs

Cf. A000040, A239735, A367576.

Programs

Python

from math import prod
from sympy import primerange
def A367566(n): return prod(p for p in primerange(n+2) if all((m:=n*pow(k,n,p)%p)==1 or m==p-1 for k in range(1,p))) # Chai Wah Wu, Nov 24 2023