A323214 Composite numbers k such that p^(k-1) == 1 (mod k) for every prime p strongly prime to k.

4, 6, 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461, 530881, 552721

Offset: 1

Author

Peter Luschny, Apr 01 2019

Keywords

• nonn

Comments

A positive number k <= n is strongly prime to n if and only if k is prime to n and k does not divide n-1. See A322937 and the link to 'Strong Coprimality'.

Apparently essentially the Carmichael numbers A002997.

Examples

			2, 3 and 5 are not in this sequence because primes are not in this sequence.
4 and 6 are in this sequence because there are no primes strongly prime to 4 respectively 6.
For n = 1729 there are 1296 test cases using the definition of A002997 but only 264 test cases using the definition of a(n).
		

Links

• K. Bouallègue, O. Echi and R. G. E. Pinch, Korselt numbers and sets, International Journal of Number Theory, 6 (2010), 257-269.
• A. Korselt, G. Tarry, I. Franel and G. Vacca, Problème chinois, L'intermédiaire des mathématiciens 6 (1899), 142-144.
• Peter Luschny, Strong Coprimality
• C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to 25*10^9, Math. Comp., 35 (1980), 1003-1026.
• V. Šimerka, Zbytky z arithmetické posloupnosti, (On the remainders of an arithmetic progression), Časopis pro pěstování matematiky a fysiky. 14 (1885), 221-225.
• L. Wang, The Korselt set of a power of a prime, International Journal of Number Theory, 14 (2018), 233-240.

Crossrefs

Cf. A002997, A322937.

Programs

Julia

using IntegerSequences
PrimesPrimeTo(n) = (p for p in Primes(n) if isPrimeTo(p, n))
function isStrongCarmichael(n)
    if isComposite(n)
        for k in PrimesPrimeTo(n)
            if ! Divides(k, n-1)
                if powermod(k, n-1, n) != 1
                    return false
                end
            end
        end
        return true
    end
    return false
end
L323214(len) = [n for n in 1:len if isStrongCarmichael(n)]
L323214(30000) |> println

Sage

def is_strongCarmichael(n):
    if n == 1 or is_prime(n): return False
    for k in (1..n):
        if is_prime(k) and not k.divides(n-1) and is_primeto(k, n):
            if power_mod(k, n-1, n) != 1: return false
    return true
def A323214_list(len):
    return [n for n in (1..len) if is_strongCarmichael(n)]
print(A323214_list(600000))