login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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 * A035077 A032164 A177122

Adjacent sequences:  A318552 A318553 A318554 * A318556 A318557 A318558

KEYWORD

nonn

AUTHOR

Barry Fagin, Aug 28 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 7 23:16 EDT 2022. Contains 355995 sequences. (Running on oeis4.)