# Construction of Carmichael numbers with many factors

Is there an efficient method to construct random Carmichael-numbers with $50-100$ prime factors ?

The method with vectors $p_1,...,p_k$ , where $\frac{1}{p_1}+...\frac{1}{p_k}=1$ which gives a formula like $(6n+1)(12n+1)(18n+1)$ , which is a Carmichael number, if all the factors are prime, is useless because it is too difficult to find a number $n$, such that so many factors are simultanoeusly prime.

Erdoes method produces Carmichael numbers with not too many factors relatively easy, but it would take rather long to find a subset of $50-100$ primes with $\prod_{j=1}^k p_j\equiv 1\ (\ mod \ L)$

Do the quadratic residues help ? Which method is best to construct my own Carmichael-"monster-numbers" ?

• For other folks landing here, this answer gives references for construction of Carmichael numbers with 1m+ and 10m+ factors. – Armadillo Jim Jan 27 '17 at 21:43

If you want to Construct a Carmichael number with many factors, follow this procedure:

I. First pick a "highly composite number $n$" (A number with many divisors)

II. Find all divisors of $n$ are $d_k$.

III. Construct a subset $S$ of primes $p_k$ that are relatively prime to $n$ and are of the form $d_k+1$ $=$ $p_k$, (Again, $d_k$ must divide $n$) $S$ $=$ {$p, p_2, p_3,...p_k$}

Now choose one of the following procedures based on how large your subset $S$ is:

IV. If the subset of primes $p_k$ in $S$ is small (no more than $12$ primes) you can find the product of all your primes in your subset: $p*p_2*p_3*p_4...*p_{12}$ $=$ $x$. Now find all divisors $v_k$ of $x$ and compute all $v_k$ $\pmod n$. If the result is $1$ $\pmod n$ for any $v_k$, then $v_k$ is a Carmichael number. Otherwise it is not.

V. If the subset $S$ is larger (say more than $12$ primes), multiply all the primes in your subset $S$ (as in option $4$), $p*p_2*p_3*p_4...*p_k$ $=$ $x$. Compute $x$ $\pmod n$. If the result is $1$ $\pmod n$, we have a Carmichael Number $x$ with $k$ distinct factors. If it is not $1$ $\pmod n$, then suppose that $x$ $=$ $y$ $\pmod n$. Now find a divisor of $x$ $=$ $v_k$ such that $v_k$ $=$ $y$ $\pmod n$. Then $(x/v_k)$ is a Carmichael number. If we are searching for a $v_k$ $|$ $x$ with at least $3$ distinct prime factors, then you can search for $v_k$ $|$ $x$ such that $v_k$ $=$ $1$ or $y$ $\pmod n$. If $v_k$ is $1$ $\pmod n$, (and at least $3$ distinct prime factors) we have a Carmichael number $v_k$ instead. In fact, this leads to the last (least efficient) procedure.

VI. Construct a divisor $v_k$ (must have $3$ prime factors at least) such that $v_k$ $=$ $1$ $\pmod n$. You can start multiplying primes $p_k$ from subset $S$ (only once however) until your result $\pmod n$ is $1$. The product of those primes will be a Carmichael Number.

Important: I left this out on the procedure, sorry I should have added it in earlier: If $n+1$ is prime, then do NOT include it in your subset of primes $S$ which are $p_k$. Every Carmichael number $x$ that you do construct that is not a multiple of $n+1$, $x(n+1)$ will be a Carmichael number.

Here is an example using the second of all three methods:

$2^6*3^2*5*7$ $=$ $20160$. The divisors of $20160$ are:

$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 28, 30, 32, 35, 36, 40, 42, 45, 48, 56, 60, 63, 64, 70, 72, 80, 84, 90, 96, 105, 112, 120, 126, 140, 144, 160, 168, 180, 192, 210, 224, 240, 252, 280, 288, 315, 320, 336, 360, 420, 448, 480, 504, 560, 576, 630, 672, 720, 840, 960, 1008, 1120, 1260, 1344, 1440, 1680, 2016, 2240, 2520, 2880, 3360, 4032, 5040, 6720, 10080, 20160$ (84 divisors)

The primes $p_k$ which are one more than a divisor $d_k$ of $20160$ and relatively prime to $20160$ are:

$11, 13, 17, 19, 29, 31, 37, 41, 43, 61, 71, 73, 97, 113, 127, 181, 193, 211, 241, 281, 337, 421, 449, 577, 631, 673, 1009, 2017, 2521, 3361, 20161$ (31 primes)

Remember when constructing the subset to leave out $n+1$ $=$ $20161$.

$S$ $=$ {$11, 13, 17, 19, 29, 31, 37, 41, 43, 61, 71, 73, 96, 113, 127, 181, 193, 211, 241, 281, 337, 421, 449, 577, 631, 673, 1009, 2017, 2521, 3361$}

Using method $IV$:

The product is $x$ of all the primes in subset $S$ is $17377$ $\pmod {20160}$. Now the problem is finding a $v_n$ $|$ $x$ such that $v_n$ $=$ $17377$ $\pmod {20160}$.

I started by taking the $\gcd$ of numbers of the form $17377+20160*a$, $x$. If the $\gcd(17377+20160*a, x)$ was not $1$, I divided ($x$/$\gcd(17377+20160*a, x)$ $=$ $x_2$ I repeated the process using ($x_k$/$\gcd(17377+20160*a, x)$ $=$ $x_{k+1}$ until all factors are used up in subset $S$ or we end up with a product of factors that is congruent to $1$ or $y$ $\pmod {20160}$. (But be careful not to use the same factor you removed, otherwise $x$ will not be square free).

$17377+20160*3$ $=$ $13*53*113$, (since $13$, $113$ are factors of $x$, but $53$ is not, I continue below.)

$53+20160*1$ $=$ $17*29*41$ ($17$, $29$, and $41$ are all factors of $x$ which are not $13$ or $113$.) This process is complete.

$13*17*29*41*113$ $=$ $17377$ $\pmod {20160}$

Now $(x/(13*17*29*41*113)$ $=$ $11*19*31*37*43*61*71*73*97*127*181*193*211*241*281*337*421*449*577*631*673*1009*2017*2521*3361$ $=$ $5394154199929997636795937494499572299377721256273675947201$ is a Carmichael number with $24$ prime factors.

The other methods I will not do and I suppose you could use the subset I used in this example, (eg. you could make it bigger by increasing the number of divisors, although you will have a tougher time with it, try $2^8*3^4*5^3*7^2*11*13*17*19*23*29$ $=$ $3912870465504000$ for instance or maybe $n!$ for larger numbers.

Hope this helps.

FYI the quadratic residues I find are not important for constructing larger Carmichael Numbers with many factors.