cp's OEIS Frontend

A306330 Squarefree n with >= 3 factors that admit idempotent factorizations n = p*q.

%I A306330 #57 Nov 29 2023 20:12:20
%S A306330 30,42,66,78,102,105,114,130,138,165,170,174,182,186,195,210,222,246,
%T A306330 255,258,266,273,282,285,290,318,330,345,354,366,370,390,399,402,410,
%U A306330 426,434,435,438,455,462,465,474,498,510,518,530,534,546,555,570,582,602
%N A306330 Squarefree n with >= 3 factors that admit idempotent factorizations n = p*q.
%C A306330 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.
%C A306330 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).
%C A306330 (p and q are not required to be primes. - _N. J. A. Sloane_, Feb 08 2019)
%H A306330 Barry Fagin, <a href="/A306330/b306330.txt">Table of n, a(n) for n = 1..5920</a> (all terms <= 2^16)
%H A306330 Barry Fagin, <a href="/A306330/a306330.txt">Idempotent factorizations for all n < 2^26</a>
%H A306330 Barry Fagin, <a href="https://doi.org/10.3390/info10070232">Idempotent Factorizations of Square-Free Integers</a>, Information 2019, 10(7), 232.
%e A306330 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.
%o A306330 (PARI) isok3(p, q, n) = frac((p-1)*(q-1)/lcm(znstar(n)[2])) == 0;
%o A306330 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
%Y A306330 Cf. A115957, A138636, A002322.
%Y A306330 Subsequence of A120944 (composite squarefree numbers).
%K A306330 nonn
%O A306330 1,1
%A A306330 _Barry Fagin_, Feb 07 2019
%E A306330 Edited by _N. J. A. Sloane_, Feb 08 2019