Carmichael number divisible by a given positive integer

Question

Prove or disprove this conjecture : If $k>2$ is an integer with $\gcd(k,\varphi(k))=1$ , then there is a Carmichael number $N$ with $k\mid N$

The condition $\gcd(k,\varphi(k))=1$ is necessary. Otherwise, $k$ would not be squarefree and therefore also $N$ , which is impossible. Or there would be prime factors $p,q$ of $k$ and therefore $N$, with $p\mid q-1$. This is also impossible since this would imply $p\mid N-1$ because of $q-1\mid N-1$ contradicting $p\mid N$

But is it also sufficient ? And if yes, is there an efficient method to construct a Carmichael number divisible by $k$ ? A particular hard case seems to be $k=885=3\cdot 5\cdot 59$.

Is there a Carmichael number divisble by $885$ ?

Answer 1

A Carmichael number divisible by $885$ is:
$$164488660061020788061329257343567786500424705$$ factors are: $3\cdot5\cdot53\cdot59\cdot257\cdot353\cdot929\cdot1613\cdot2729\cdot6449\cdot7937\cdot43649\cdot514229\cdot8227649$

It is probably not the smallest Carmichael number divisible by $885$.
After all, we know that Carmichael numbers are infinite . However, we do not know if there is an infinite number of them with a certain number of prime factors.

The above 45-digit number was found by an algorithm proposed by P. Erdős. If you want to have the Pari/GP code, please write in the comments. I will expand my answer accordingly.

$Edit:$

The Pari/GP code I used:

\\ Input factorset A as Vector e.g.: A=[2^6,3^2,5,7,11,19].
\\ Returns Carmichael numbers and its factorisation as vector. 

erdoes(A)={my(a=vecprod(A),s=3,V=[],Vc=[],Ve=[],vm);    
  print("calculating prime vector ["s" .. "precprime(a/2)"] ...");print;
    while(s<a/2,   \\ Get prime Vector V: primes with p-1 divides a.
    if(!Mod(a,s-1)&Mod(a,s),V=concat(V,[s]));
    s=nextprime(s+1)
    );
  print(V);
  print;print("#primes to combine: ",#V);print("#combinations to test: "2^(#V-3)" ...");print;
  forstep(t=2^#V-1,1,-1,Ve=vecextract(V,t);   \\ Search for combinations of V with #V elements.
    if(#Ve>2,
      vm=vecprod(Ve);
      if(Mod(vm,a)==1,print(vm);print(Ve);print);
      vm=1  
      )
    )
};

The factorset I used to find the number above was:

A=[2^8,11,13,29,31];
erdoes(A)

Note: primes and primepowers used in the factorset are excluded in the final prime vector. Thus for our purpose $3$, $5$ and $59$ may not be in the list, otherwise any returning Carmichael number is not divisible by $885$.

A smaller Carmichael number divisible by $885$ can be determined by:

A=[2^6,7^3,13,29];
erdoes(A)

returns:

168657937545500817238651149859325089665
[3, 5, 53, 59, 197, 233, 449, 929, 3137, 11369, 17837, 285377, 1034489]

However, this algorithm is not capable of finding the least Carmichael numbers. Rather, its strength lies in determining those with many prime factors, even several hundred.

Answer 2

Your conjecture seems to be true. Here are some ideas i had (this was a bit too long for a comment)

Firts of all, by Bezout's lemma, as $\gcd(k,\varphi(k))=1$, then there exist $x,y$ such that $\forall z$

$$k\big(x+\varphi(k)\cdot z\big)=\varphi(k)\big(y+k\cdot z\big)+1$$

I will prove that there exists a $z$ such that $k\big(x+\varphi(k)\cdot z\big)$ is a Carmichael number. For this to happen, $\forall n$, $\gcd\big(n;k\big(x+\varphi(k)\cdot z\big)\big)=1$ we have

$$n^{k\big(x+\varphi(k)\cdot z\big)-1}=n^{\varphi(k)\big(y+k\cdot z\big)}\equiv 1\pmod{k\big(x+\varphi(k)\cdot z\big)}$$

Because $n$ and $k$ are coprime, $$n^{\varphi(k)\big(y+k\cdot z\big)}\equiv 1\pmod{k}$$.

So we must have $$n^{\varphi(k)\big(y+k\cdot z\big)}\equiv 1\pmod{x+\varphi(k)\cdot z}$$

From $$k\big(x+\varphi(k)\cdot z\big)=\varphi(k)\big(y+k\cdot z\big)+1$$ we can observe that $x$ and $\phi(k)$ are coprime and $kx\equiv1\pmod{\varphi(k)}$

From here I had some ideas of using Dirichlet's theorem, to make $x+\varphi(k)\cdot z$ a prime or to make $x+\varphi(k)\cdot z=k\cdot (x^2+l\cdot \varphi(k))$, but both approaches failed.

If my initial idea doesn't do the job, I think that some other application of Bezout's lemma finishes it.

Answer 3

The smallest Carmichael number that is a multiple of 885, is:

3399464645479365585

Below 2^64, there are only two more Carmichael numbers that are divisible by 885:

15165761619468172065
15885147377097813585

It's an open-problem whether every odd cyclic number has at least one Carmichael multiple.

See also:

• https://oeis.org/A253595
• https://www.numericana.com/data/crump.htm

Several methods for constructing Carmichael numbers (including source-code implementations), are listed at:

• https://trizenx.blogspot.com/2020/08/pseudoprimes-construction-methods-and.html