# New method for constructing a Carmichael Number from two primes

I came up with a quick method for constructing a Carmichael number, with three distinct prime factors $p$, $q$, $r$. Choosing two odd primes, $p$ and $q$ such that $p-1$ $∤$ $q$ and $q-1$ $∤$ $p$, Let $k$ be the lcm (least common multiple) of $(p-1, q-1)$. Let $d$ $=$ ($pq-1$)/($\gcd(k, pq-1)$. $r$ $=$ $1$ $\pmod d$. Also, let $t$ be the solution to $pqt$ $=$ $1$ $\pmod k$. $r$ $=$ $t$ $\pmod k$. So the third prime factor, $r$ is congruent to $t$ $\pmod k$ and $1$ $\pmod d$. The problem I do not know how to do is find this last prime $r$. Please someone help with this example I am trying to construct a Carmichael number. Thanks in advance.

Example using the primes $p$ $=$ $43$ and $q$ $=$ $53$:

$43*53*r$ is a Carmichael number, and $r$ is prime. $43$ $∤$ $52$ and $53$ $∤$ $42$. Lcm of $42$ and $52$ is $1092$. $43*53-1$ $=$ $2278$. $\gcd(2278, 1092)$ $=$ $2$ since $2278$ $=$ $2*17*67$ and $1092$ $=$ $2^2*3*7*13$. Now we conclude that $r$ $=$ $1$ $\pmod {2278}$. Now we have that $pqr-1$ $|$ $(2^2*3*7*13*17*67)$ and $pqr$ $|$ $(43*53)$. There are no errors in the division statements. The next step is to find $t$ such that $43*53*t$ $=$ $1$ $\pmod {1092}$. $t$ $=$ $23$. Unfortunately, $23*43*53$ is not a Carmichael number since $22$ $=$ $2*11$, $11$ does not appear as a factor of $pqr-1$ as described earlier. So now we have that $r$ $=$ $23$ $\pmod {1092}$ and $r$ $=$ $1$ $\pmod {2278}$. This concludes that $r$ is a prime congruent to $1191395$ $\pmod {1243788}$. What I have trouble with is checking whether or not $43*53*(1191395+1243788x)$ is a Carmichael number for every positive integer value of $x$. What is the fastest way that I can easily find this prime $r$ without testing continuous $x$ values? If so, can someone please find the prime $r$ and construct the Carmichael number $pqr$ using my example primes $p$ $=$ $43$ and $q$ $=$ $53$ as I described above?

Quick link to the wiki page: https://en.wikipedia.org/wiki/Carmichael_number

• Finding primes is in general a hard thing to do. As far as I know there is no known efficient algorithm for generating primes of any kind, let alone ones that satisfy some condition. Nov 5, 2016 at 21:28

There are no such Carmichael numbers composed of three primes with two of the primes being $43$ and $53$.

Given $p=43, q=53$ with $r$ to be determined to make Carmichael $c=pqr$, you rightly establish that $r \equiv 23 \bmod 1092$. Also notice that $c \equiv 43\cdot 53 = 2279 \bmod (r-1)$. This obviously means that $r$ cannot be more than $2279$. Given the previous $r \equiv 23 \bmod 1092$, there are only $3$ values $\{23,1115,2207\}$ to check for suitability, none of which answer the requirement.

Note the general result that for a three-prime Carmichael number, you require $pq>r, pr>q, qr>p$ .

Using the method described in Löh & Niebuhr, I found the following 10-prime Carmichael number which includes $43$ and $53$ as factors:

$$19 \cdot 29 \cdot 43 \cdot 53 \cdot 73 \cdot 127 \cdot 313 \cdot 547 \cdot 937 \cdot 1093 \approx 2.04133 \cdot 10^{21}$$

• Are there Carmichael numbers of the form $43*53*n$ then? $n$ does not have to be prime? How would they be constructed? Nov 6, 2016 at 17:12
• Potentially yes; $n$ would be a product of other primes. Löh and Niebuhr's paper gives an interesting method for constructing higher-factor-count Carmichael numbers. Nov 6, 2016 at 17:22
• I guess one way would be to take all the divisors $k$, $k_2$, ....$k_n$ of $1092$ and find the primes of the form $k+1$, $k_2+1$, ..... $k_n+1$ and take the product $y$ of $k+1$*$k_2+1$*$k_3+1$...*$k_n+1$, and compute divisors of $y$ $\pmod {1092}$. Whichever divisors $x$ of $y$ are $1$ $\pmod 1092$ are Carmicheal numbers. Just check that $43$ and $53$ are factors. Do you know of other ways? Nov 6, 2016 at 17:26
• $1092$ doesn't generate enough variety of primes to meet the criteria. See update above; I used factors of $6552$ to generate the candidate prime set. Nov 6, 2016 at 18:48