A318555 "Strong impostors" not divisible by 4: Those numbers s !== 0 (mod 4) such that lambda(s) | 2(s-1), where lambda is the Carmichael function (A002322).

6, 15, 66, 91, 435, 561, 703, 946, 1105, 1729, 1891, 2465, 2701, 2821, 2926, 3367, 5551, 6601, 8646, 8695, 8911, 10585, 11305, 12403, 13981, 15051, 15841, 16471, 18721, 23001, 26335, 29341, 30889, 38503, 39865, 41041, 46657, 49141, 52633, 53131, 62745, 63973, 68101, 75361, 76627, 76798, 79003, 88561, 88831, 91001

Offset

1,1

Comments

Strong impostors not == 0 (mod 4) have the property that, even though they are composite, when paired with any odd prime r such that (s,r) = 1, they produce valid RSA key pairs. More specifically, if n=sr, all a in Z_n will be correctly encrypted and decrypted for any (e,d) key pair such that ed == 1 mod (s-1)(r-1). They include the Carmichael numbers and are squarefree. The set of their odd prime factors is always normal: If p_i and p_j are odd prime factors, no p_i == 1 mod p_j.

Links

Barry Fagin, Table of n, a(n) for n = 1..2773 (all terms up to 32 bits)

D. Borwein, J. M. Borwein, P. B. Borwein and R. Girgensohn, Giuga's Conjecture on Primality, Amer. Math. Monthly 103, No. 1, 40-50 (1996).

B. S. Fagin, Composite Numbers That Give Valid RSA Key Pairs For Any Coprime p, Information, 9, 216; doi:10.3390/info9090216.

J. M. Grau and Antonio Oller-Marcén, Generalizing Giuga's conjecture, arXiv:1103.3483 [math.NT], 2011.

Mathematica

Reap[For[s = 1, s < 10^5, s++, If[!Divisible[s, 4] && CompositeQ[s], If[ Divisible[2(s-1), CarmichaelLambda[s]], Print[s]; Sow[s]]]]][[2, 1]] (* Jean-François Alcover, Feb 18 2019 *)

Prog

(Python with numbthy library)
for s in range(min_s, max_s):
    if numbthy.is_prime(s):
        continue
    elif s % 4 == 0:
        continue
    elif (2*(s-1) % numbthy.carmichael_lambda(s) == 0):
        print("s =", s)
(PARI) isok(s) = s>1 && s%4>0 && !isprime(s) && (2*s-2)%lcm(znstar(s)[2])==0; \\ Jinyuan Wang, Mar 01 2020

Crossrefs

Cf. A002997 (Carmichael numbers), A005117 (squarefree numbers).

Subsequence of A231569.

Sequence in context: A233450 A298374 A324973 * A359923 A035077 A032164

Adjacent sequences: A318552 A318553 A318554 * A318556 A318557 A318558

Keyword

nonn

Author

Barry Fagin, Aug 28 2018

Status

approved