OFFSET
1,1
COMMENTS
An idempotent factorization of n is a way of writing n = p*q such that b^(k(p-1)(q-1)+1) is congruent to b mod n for any integer k >= 0 and any b in Z_n. For example, p = 19, q = 15 is an idempotent factorization of n = 285. All factorizations of semiprimes are idempotent, so this sequence is restricted to n with >= 3 factors. Idempotent factorizations have the property that p and q generate correctly functioning RSA keys, even if one or both are composite.
We show in the reference below that a bipartite factorization of a squarefree integer n = pq is idempotent if and only if lambda(pq) divides (p-1)(q-1).
(p and q are not required to be primes. - N. J. A. Sloane, Feb 08 2019)
LINKS
Barry Fagin, Table of n, a(n) for n = 1..5920 (all terms <= 2^16)
Barry Fagin, Idempotent factorizations for all n < 2^26
Barry Fagin, Idempotent Factorizations of Square-Free Integers, Information 2019, 10(7), 232.
EXAMPLE
30 = 5 * 6, 42 = 7 * 6, 66 = 11 * 6, 78 = 13 * 6, 102 = 17 * 6, 105 = 7 * 15, 114 = 19 * 6, 130 = 13 * 10 are the idempotent factorizations for the first 8 terms in the sequence. 210 = 10 * 21 is the smallest n with a fully composite idempotent factorization, one in which both p and q are composite. The number n = p * 6 is idempotent for any prime p >= 5.
PROG
(PARI) isok3(p, q, n) = frac((p-1)*(q-1)/lcm(znstar(n)[2])) == 0;
isok(n) = {if (issquarefree(n) && omega(n) >= 3, my(d = divisors(n)); for (k=1, #d\2, if ((d[k] != 1) && isok3(d[k], n/d[k], n), return (1); ); ); ); } \\ Michel Marcus, Feb 22 2019
CROSSREFS
KEYWORD
nonn
AUTHOR
Barry Fagin, Feb 07 2019
EXTENSIONS
Edited by N. J. A. Sloane, Feb 08 2019
STATUS
approved