OFFSET
1,1
COMMENTS
Fully composite idempotent factorizations are bipartite factorizations n=p*q such that p and q are composite numbers with the property that for any b in Z_n, b^(k(p-1)(q-1)+1) is congruent to b mod n for any integer k >= 0. Idempotent factorizations have the property that p and q generate correctly functioning RSA keys, even if one or both are composite.
2730 has more than one fully composite idempotent factorization (10*273, 21*130). It is the smallest positive integer with that property. 7770 and 8463 are similar.
LINKS
Barry Fagin, Table of n, a(n) for n = 1..63737
Barry Fagin, Idempotent Factorizations of Square-Free Integers, Information 2019, 10(7), 232.
Barry Fagin, Search Heuristics and Constructive Algorithms for Maximally Idempotent Integers, Information (2021) Vol. 12, No. 8, 305.
EXAMPLE
210=10*21, 462=22*21, 570=10*57, 1155=21*55, 1302=6*217, 1330=10*133, 1365=15*91 and 1785=21*85 are the fully composite idempotent factorizations for the first eight terms.
PROG
(Python)
for n in range(2, max_n):
factor_list = numbthy.factor(n)
numFactors = len(factor_list)
if numFactors <= 3:
continue
if not bsflib.is_composite_and_square_free_with_list(n, factor_list):
continue
fciFactorizations = bsflib.fullyCompositeIdempotentFactorizations(n, factor_list)
numFCIFs = len(fciFactorizations)
if numFCIPs > 0:
fcIdempotents += 1
print(n)
(PARI) isokc(p, q, n) = (p != 1) && !isprime(p) && !isprime(q) && (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 (isokc(d[k], n/d[k], n), return (1); ); ); ); } \\ Michel Marcus, Feb 22 2019
CROSSREFS
KEYWORD
nonn
AUTHOR
Barry Fagin, Feb 20 2019
STATUS
approved