login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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).
1
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
Amiram Eldar, Table of n, a(n) for n = 1..8000 (terms 1..2773 from Barry Fagin)
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
KEYWORD
nonn
AUTHOR
Barry Fagin, Aug 28 2018
STATUS
approved