Why do Carmichael numbers (appear to) frequently end in $1$?

Solution 1:

Thomas has answered a very similar problem in the following thread: Why are Carmichael Numbers less common with an arithmetic progression

The fact that you're seeing this phenomena has nothing to do with the number 10 specifically.

Using Korselt's criterion - $n$ is a Carmichael number iff $n$ is composite, square free, and for all prime divisors of $n$, we have $p − 1 ∣ n − 1$.

Suppose you're "trying to assemble" a Carmichael number of the form $n = p\cdot k + a$, for some prime number $p$. For every prime factor, $q|n$, we'll have $\ q-1|(p\cdot k+a-1)$. Therefore, for $q$ to be of the form $p\cdot k + 1$, we must have $a=1$.

That means, that if $a \ne 1$ then $n$ won't have prime factors of the form $p\cdot k+1$, making it a lot harder to assemble Carmichael numbers, because you have less primes to work with (especially for small $p$'s).

Note that for every prime $p \ne 2$ that we choose, $n=1 \ mod\ p\ $ iff $\ n=1\ mod\ 2p$, because all Carmichael numbers are odd. Then specifically for 10, the group of Carmichael numbers of the form $10\cdot k + 1$ are the same as the group of Carmichael numbers of the form $5\cdot k + 1$

The following table shows the number (denoted as $M$) of Carmichael numbers $n < 10^{16}$, satisfying $n = 1\ mod\ p$, for different primes, out of the total $246683$ Carmichaels numbers $n < 10^{16}$.

+---------------------+----------+
| p        | M        | M/246683 |
+---------------------+----------+
|3         |245288    |99.43%    |
|5         |215713    |87.44%    |
|7         |168856    |68.45%    |
|11        |100071    |40.56%    |
|13        |77178     |31.28%    |
|17        |55109     |22.34%    |
|19        |36363     |14.74%    |
+---------------------+----------+

Solution 2:

The main reason is that if a Carmichael number $n$ has a prime of the form $10k+1$ in it, then $10|n-1$, and so $n\equiv1\pmod{10}$. If we assume the distribution of primes in a factorization is average according to last digit, then as only one needs to be of this form, the feature becomes increasingly likely (P($n$ is Carmichael $\land$ $n\equiv 1\pmod{10})\approx1-\left(\frac34\right)^k$ if $n$ has $k$ prime factors).

There is a list of factorizations of small 3-Carmichael numbers here, and the only other possibility is that the last digits product to $1\pmod{10}$, for example $23\times199\times353=1,615,681$ and $29\times113\times1093=3,581,761$.