4
$\begingroup$

I'm having some trouble while trying to prove the well known fact that a Carmichael number has at least 3 prime factors.

Basically, how I see it, I have 2 options:

  1. building a number b that will satisfy $b^{n-1}\not\equiv 1(n)$ thus creating a fermat witness

  2. trying to contradict the condition of: $p|n \iff\ p-1|n-1$

Maybe I'm missing something very simple but I can't seem to get this done.

Addition: we are talking about the case where $n=pq$, the case $n=p$ is trivial.

$\endgroup$
8
$\begingroup$

Assume that $n=pq$, with $p<q$ two distinct primes, is a Carmichael number. Then we have $$ q\equiv1\pmod{q-1}\implies n=pq\equiv p\mod{q-1}\implies n-1\equiv p-1\pmod{q-1}. $$ Here $0<p-1<q-1$, so $n-1$ is not divisible by $q-1$. A contradiction.

The same argument can be extended to prove that any prime factor of a Carmichael number $n$ is less than $\sqrt n$. Namely, as above we get for all primes $p\mid n$ $$ n-1\equiv p\frac{n}{p}-1\equiv \frac{n}{p}-1\pmod{p-1}. $$ Therefore $n/p-1$ must be a (positive) multiple of $p-1$. Thus $$ \frac{n}{p}-1\ge p-1\implies\frac{n}{p}\ge p\implies n\ge p^2. $$

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

In a carmicheal number, you need at least three prime factors. These primes might be written in the form $p_x = a_x n + 1$ where $n$ is the common divisor of $p_x-1$.

If there were just two prime factors, this would expand to $a_1 a_2 n^2 + (a_1 + a_2)n + 1$. This number is required to be a multiple of both $a_1$ and $a_2$, but it can not be, when $a_1$ and $a_2$ are un-equal, and it won't work when it is (because the maximum period of a square of $p$ is divisible by $p$).

In order to make the term on $n$ be a multiple of $a_j$ over all $j$, you need at least three separate primes, so that any two can be complementry relative to the third. For example, in a base where $1,1$, $2,1$, and $3,1$ are all prime, then the product of pairs are not divisible by $p-1$, but in the product of all 3, you have $6,11,6,1$, which is divisible by $1,0$, $2,0$ and $3,0$, since the base would be a multiple of $6$ anyway.

Carmichael Numbers and Primes

These are involved in the process test of large number for primeness.

The simple test of dividing $n$ by every $p$ up to the square root, has a cost in the order of the square root of $n$. For $n$ of the order of $1,000,000$, this can cost, eg £1000. There are other tests that can reduce the cost to eg the cost per digit: ie £6.

The oldest of these is that for any number $x$, $x^p \mod p = x$ is true whenever p is prime, and if it is not true, then $p$ is definitely composite. You can see the results by looking at the remainders of $2^p$, when divided by $p$.

     3   4   5   6   7   8   9   10   11    12    13    n
     8  16  32  64 128 256 512 1024 2048  4096  8192   2^n
     2   0   2   4   2   0   8    4    2     4     2   remainder
     y   n   y   n   y   n   n    n    y     n     y   prime?

Raising 2 to large powers to find the remainder when divided by some $n$, can be made much easier if multiples of $n$ are cast out as one goes. This brings the calculations well into range of hand or desktop calculator.

For example, for 341, one might note that $2^{10} \mod 341 = 1$. One then calculates $1^{34}*2 \mod 341$ to get $2$. Although this is a marker of a prime, it is in fact composite. There is a very small proportion of composite numbers that sneak through the test. These are called pseudo-primes to $2$.

Most of the pseudo-primes to $2$ are not pseudo-primes to $3$ or some other number. So doing the test for two numbers, one will filter out most of the pseudo-primes. There is however a class of number that are pseudo-prime to all bases: the Carmichael numbers. These are rarer than pseudoprimes, but still one needs to be aware of these.

On the other hand, the number $5461 = 43 \cdot 127$ divides all $(2^a\;5^b)^{42n}-1$, this includes $5460$ itself, so doing a test over two different bases do not exactly remove all pseudoprimes. $5461$ is a pseudoprime to all bases $2^a\;5^b$.

The test for primeness supposes that if $p$ is prime, then some $b^{p-1}=1 \mod p$, for all $b$ co-prime to $p$. In a pseudo-prime, both $p$ and $q$, divide some $2^m-1$, while $m$ divides both $p-1$ and $q-1$. In the case of $341$ above, $m=10$, which divides both $11-1$ and $31-1$. The reason it usually fails, is that selecting a different base $b$, will mean that the period (the smallest $x$ that satisfies $p \mid b^x-1$), does not divide the other prime's $p-1$.

A Carmichael number is a pseudo-prime to every base. For a composite number, the period $\lambda = \operatorname{lcm}(p-1, q-1, \cdots...)$, where the composite number is $pq..$. The lcm can not divide both $pq-p-q$ since it would require $p-1$ to divide $q$, which does not happen. When three names are involved, one gets $\operatorname{lcm}(p-1, q-1, r-1)$, and it is then possible for any two to complement the third.

For example, $1729$ is a carmichael number. It has three factors: $7, \; 13, \; 19$. When one finds $\operatorname{lcm}(7-1, 13-1, 19-1)=36$, one sees that $36 \mid 1729-1$, and so one can't tell this by this test if it were prime or not. Of course, there are quite large numbers, like $601 \cdot 1201 \cdot 1801$, whose period is $3600$, divides the product of these numbers, less 1.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I find the term Carmichael primes to be very confusing, after all, they are not primes. Maybe, you should replace this by Carmichael numbers $\endgroup$ – Tomas Jul 1 '13 at 8:32
0
$\begingroup$

(Personally, I find the following proof very unsatisfying, because it provides me no insight: it seems to all boil down to rather tedious numerical nitty-gritty. Unfortunately, this seems to be par for the course in number theory, at least in my limited experience.)

Suppose $n = pq$, where $p$ and $q$ are prime, $p < q$, and $(q - 1)|(n - 1)$. We show that these conditions lead to a contradiction.

The last condition is equivalent to saying that there exists an integer $k$ such that

$$ n - 1 = pq - 1 = k(q - 1)\, \tag{1} $$

Since $q > p > 1$, it follows that $n = pq > q$, and therefore $n - 1 > q - 1$.

This, together with $(1)$, implies that $k > 1$.

Now, rearranging the second equality in $(1)$ we get

$$ k = q(k - p) + 1 \,. $$

Since we already established that $k > 1$, the last equality implies that

$$k - p \geq 1\,.\tag{2}$$

Now, once more rearranging the second equality in $(1)$, to

$$ 0 = k(q - 1) - pq + 1\, $$

and adding $p$ to both sides, we arrive at a contradiction:

$$ p = k(q - 1) - pq + p + 1 = (k - p)(q - 1) + 1 > (k-p)(p-1) + 1 \geq (p-1) + 1 = p \,. $$

Note that the last inequality above follows from $(2)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.