Showing numbers are Carmichael Numbers

Question

I'm currently working through a problem set for mathematical cryptography and came across a question which asks:

Say why $ 676, 75, 143 $ are not Carmichael Numbers

Furthermore, explain why 105 is the smallest candidate for a Carmichael number but using Korselt's Criterion show that 105 is not Carmichael.

I've tried looking this up and have seen mentioned many times that you use Fermat's Little Theorem however the issue is I'm self-teaching and have gotten confused trying to figure it out.

If anyone can help with the question above I'd really appreciate it, thanks.

Answer 1

A positive integer $n$ is a Carmichael number if and only if

• $n$ is squarefree and odd
• $n$ has at least three distinct prime factors
• for every prime $p$ dividing $n$, we have $p-1|n-1$

$105$ is the smallest candidate because it has $3$ distict odd prime factors and is squarefree, but it is no Carmichael number because $6$ does not divide $104$. The smallest example is $561=3\cdot 11\cdot 17$

Answer 2

According to Korselt's criterion Carmichael number $n$ should be square-free and for any prime $p|n$ should be $p-1|n-1$.

Numbers $676 = 26^2$ and $75 = 3\cdot 5^2$ are not square-free. For number $143 = 11\cdot 13$ we see that $11-1 = 10$ does not divide $143 - 1 = 142$. Thus these numbers are not Carmichael numbers.

Answer 3

Perhaps this completely basic illustration helps for the understanding. If it is not needed, I can delete that answer.

The little theorem of Fermat says, that for all primes $p$ and bases $b$ where $\gcd(b,p)=1$ we have that $b^{p-1} \equiv 1 \pmod p $ . So this suggests, that we could test some $n$ for primeness with this very easy to compute relation. But unfortunately, not only primes $p$ satisfy this, but also some composites $n$ - at least this depends also on the selection of the base $b$ .

I've made a little program to show this for some $n$ and some $b$ in a spreadsheet-like display:

base\ n --> 
  |  \
  V   \  2    3    4    5    6    7    8    9   10   11   12
-------+----------------------------------------------------
    2  | 0    1    0    1    2    1    0    4    2    1    8
    3    1    0    3    1    3    1    3    0    3    1    3
    4    0    1    0    1    4    1    0    7    4    1    4
    5    1    1    1    0    5    1    5    7    5    1    5
    6    0    0    0    1    0    1    0    0    6    1    0
    7    1    1    3    1    1    0    7    4    7    1    7
    8    0    1    0    1    2    1    0    1    8    1    8
    9    1    0    1    1    3    1    1    0    9    1    9
   10    0    1    0    0    4    1    0    1    0    1    4
   11    1    1    3    1    5    1    3    4    1    0   11
   12    0    0    0    1    0    1    0    0    2    1    0
   13    1    1    1    1    1    1    5    7    3    1    1
   14    0    1    0    1    2    0    0    7    4    1    8
   15    1    0    3    0    3    1    7    0    5    1    3
   16    0    1    0    1    4    1    0    4    6    1    4
   17    1    1    1    1    5    1    1    1    7    1    5
   18    0    0    0    1    0    1    0    0    8    1    0
   19    1    1    3    1    1    1    3    1    9    1    7
   20    0    1    0    0    2    1    0    4    0    1    8
   21    1    0    1    1    3    0    5    0    1    1    9
   22    0    1    0    1    4    1    0    7    2    0    4

The entries are always $ b^{n-1} \pmod n$ and we see for instance at the $n$ which are primes $p=3$ or $p=5$ and so on, that indeed for all bases $b$ that do not contain $p$ the result is indeed $1$. At composite $n$ this is not so; in most cases the entries are different from $1$ and thus the little Fermat would work in this cases. For instance, for $n=4,6,8,10,12 $ there occur $1$ - but only at bases $b=k\cdot n+1$ meaning $(k \cdot n+1)^{n-1} \equiv 1 \pmod n$
But it becomes a bit more complicated for larger $n$.

base\ n --> 
  |  \
  V   \ 7    9   11   13   15   17   19   21   23   25   27
 ------------------------------------------------------------
   2    1    4    1    1    4    1    1    4    1   16   13
   3    1    0    1    1    9    1    1    9    1    6    0
   4    1    7    1    1    1    1    1   16    1    6    7
   5    1    7    1    1   10    1    1    4    1    0   16
   6    1    0    1    1    6    1    1   15    1   21    0
   7    0    4    1    1    4    1    1    7    1    1    4
   8    1    1    1    1    4    1    1    1    1   21   10
   9    1    0    1    1    6    1    1   18    1   11    0
  10    1    1    1    1   10    1    1   16    1    0   19
  11    1    4    0    1    1    1    1   16    1   16   22
  12    1    0    1    1    9    1    1   18    1   11    0
  13    1    7    1    0    4    1    1    1    1   11   25
  14    0    7    1    1    1    1    1    7    1   16   25
  15    1    0    1    1    0    1    1   15    1    0    0
  16    1    4    1    1    1    1    1    4    1   11   22
  17    1    1    1    1    4    0    1   16    1   21   19
  18    1    0    1    1    9    1    1    9    1    1    0
  19    1    1    1    1    1    1    0    4    1   21   10
  20    1    4    1    1   10    1    1    1    1    0    4
  21    0    0    1    1    6    1    1    0    1    6    0
  22    1    7    0    1    4    1    1    1    1    6   16

We see, that regularly simple composite numbers like $n=9,15,21,25$ have $1$ at some small bases, so using that bases for the little Fermat prime-test would sign false positives. However, the base $b=2$ works nice so far: it perfectly separates between primes and composites. The same is true for $b=3$.
But still we get in troubles. Let's look around $n=341$

     |  337  339  341  343  345  347  349  351  353  355  357
-----|-------------------------------------------------------
    2|    1    4    1  162   31    1    1  121    1  229   67
    3|    1    9   56  337   96    1    1  243    1  294   30
    4|    1   16    1  176  271    1    1  250    1  256  205
    5|    1   25   67  141  220    1    1  259    1  270  319
    6|    1   36   56   57  216    1    1  270    1  231  225
    7|    1   49   56    0  301    1    1  166    1  129  259
    8|    1   64    1   43  121    1    1   64    1   49  169

For the primes around $n=341$ things are ok, and also for the composites around $n$ when using base $b=2$. Only, $n=341$ gives a false positive. So this is called a "pseudoprime (to base 2)" Here base $b=3$ would still detect correctly the compositeness. But let's see some more base-2-pseudoprimes:

     |  341  561  645 1105 1387 1729 1905 2047 2465 2701 2821
-----|-------------------------------------------------------
    2|    1    1    1    1    1    1    1    1    1    1    1
    3|   56  375   36    1  875    1  276 1013    1    1    1
    4|    1    1    1    1    1    1    1    1    1    1    1
    5|   67    1  595  885 1122    1  400  622 1480 2554    1
    6|   56  375   36    1  875    1  276 1013    1    1    1
    7|   56    1  436    1 1122  742 1561 1013    1 2554 2016
    8|    1    1    1    1    1    1    1    1    1    1    1
    9|   67  375    6    1    1    1 1881  622    1    1    1
   10|   67    1  595  885 1122    1  400  622 1480 2554    1
   11|  253  154    1    1 1141    1  226    1    1 2554    1
   12|   56  375   36    1  875    1  276 1013    1    1    1

We see, that a couple of them are correctly signalled by base-3, some still not and a really hard beast is $n=1729$ which needs tests up to $b=7$ to detect the compositeness.

The introduction of the concept of the Carmichael numbers is now to denote that numbers $n$ which are pseudoprime to all bases $b$ which are coprime to $n$ itself - so they are in a sense "stronger" pseudoprimes than that for only a single base. For instance, $n=561$ is a strong pseudoprime for bases $ b=2,4,5,7,8,10,...$ and only bases which happen to have a common factor with $n$ indicate correctly compositeness.

---

Other answers have indicated some properties of that Carmichael-numbers, such like squarefreeness, number of primefactors $\ge 3$ and some more - that is what you actually have asked for (and can find in the other answers).

Additional remark, in which way "Carmichael-numbers" is an interesting concept: stronger prime-test-procedures than the simple little Fermat on base $b=2$ use a couple of bases first for pseudoprime-tests before they enter more complicated and time-consumptive procedures (and it is somehow a kind of art to define the optimal set of bases for mutually correcting pseudoprime-tests up to some lower bound $n \le N$ which costs least and are still perfect indicators)