Are there infinite many primes that cannot be the largest prime factor of a Carmichael-number

carmichael-numberselementary-number-theoryprime factorizationreference-request

Let $S$ be the set of prime numbers $p$ that cannot be the LARGEST prime factor of a Carmichael-number.

The first elements of $S$ are : $$[2, 3, 5, 7, 11, 13, 23, 43, 47, 53, 59, 83]$$

Does $S$ contain infinite many primes ?

I could only find out those primes by enumerating all $2^{25}$ odd squarefree numbers containing no prime factor larger than $101$ (the $26$ th prime) , but there should be a better method. Any ideas ?

Best Answer

The comments are getting kinda long, so here it is. I checked the larger database thanks to @MartinHopf.

I checked the database by checking for each pseudoprime if it is a Carmichael number and then finding the greatest prime factor of the number, I eliminated $p$ as possible addition to $S$ if I found that $p$ was the greatest factor of such a number.

The remaining candidates below $50\ 000$ are [25799, 40883, 42023, 42443, 42683, 42767, 44159].

Update: 77579217225595049581 is an example for $p = 25\ 799$.

The remaining candidates below $50\ 000$ are now [40883, 42023, 42443, 42683, 42767, 44159].

Update: 192231276682846353121 and 30691624706028820801 are examples for $p=40\ 883$. 361362050102075568481 for $p = 42\ 023$. 187245600667639628401 for $p = 42\ 443$. 1421298370313927469001 and 1475526798515376902401 for $p = 42\ 683$. 3276241962960743496721 and 824592027949741719361 for $p = 42\ 767$. And

18474317205530955301
25086959880820862401
32793227139330403201
35249365392461726881
626067460857971232001
20726926900955087905
941595098724511030801
1947595024403123504401
7625997271344313144921
1191134505408294459601
18598551907931088038401
3290982924650209776001
17875561355805607977121
11058363534498776939521
2426379943337261168401

are all examples for $p=44\ 159$. There are no remaining candidates below $50\ 000$.

Update: I raised the search limit to all $p$ below $100\ 000$ by eliminating the $120$ possible candidates (derived from the dataset) for $p$ between $50\ 000$ and $100\ 000$.

The algorithm I used to eliminate the candidates rests on finding primes $q$ and $r$ smaller than $p$ such that $n=mpqr$ (where $m$ is varied to search multiple numbers) is a Carmichael number with maximum factor $p$. (I first only used $p$ and $q$ but found that using three factors is even faster). Since $n$ is Carmichael, we have $p-1|n-1$, $q-1|n-1$ and $r-1|n-1$. Thus $n \equiv 1 \equiv mpr \pmod {q-1}$, $mqr \equiv 1 \pmod{p-1}$ and $mpq \equiv 1 \pmod{r-1}$. Using this we can find (using the Chinese Remainder Theorem) necessary congruences for $m$ and speed up our search.

Related Question