# Can a Mersenne number ever be a Carmichael number?

Can a Mersenne number ever be a Carmichael number?

More specifically, can a composite number $m$ of the form $2^n-1$ ever pass the test: $a^{m-1} \equiv 1 \mod m$ for all intergers $a >1$ (Fermat's Test)?

Cases potentially proved so far: (That are never Carmichael numbers)

• where $n$ is odd
• where $n$ is prime

Work using "main" definition:

First off take the definition of a Carmichael number:

A positive composite integer $m$ is a Carmichael number if and only if $m$ is square-free, and for all prime divisors $p$ of $m$, it is true that $p - 1 \mid m - 1$.

Let's assume $m=2^n-1$ is squarefree. (Best case, and I believe it always is for $2^p-1$)

Take the case where $n$ (in $2^n-1$) is a prime $p$. All factors of $2^p-1$ must of the form: $2kp+1$ for some constant $k$. So will $2kp$ ever divide $2^p-2$? Factoring a $2$ out gives us $kp \mid 2^{p-1}-1$, or split into two: $k \mid 2^{p-1}-1$ and $p \mid 2^{p-1}-1$ must both be true. By Fermat's little theorem, $2^{p-1} \equiv 1 \mod p$, so $p \mid 2^{p-1}-1$ is always true.

So if $k \mid 2^{p-1}-1$ for $k = {q-1 \over p}$, is false for at least one factor $q$ of $2^p-1$, no Carmichael numbers can exist of form $2^p-1$.

Now for other cases where $n$ is composite, lets say $n=cp$, for some prime $p$, and some number $c$:

\begin{align}2^{cp}-1&=(2^p-1)\cdot \left(1+2^p+2^{2p}+2^{3p}+\cdots+2^{(c-1)p}\right)\end{align}

Thus: $2^{n-1} \mid 2^p-1$

Because of that, we must look at the factors of $2^p-1$ when considering if $2^{cp}-1$ is a Carmichael number. So we know those factors are already of form $2kp+1$, and then $kp \mid 2^{cp-1}-1$.

This is where I'm left. on an incomplete proof.

Using Bernoulli definition:

An odd composite squarefree number $m$ is a Carmichael number iff $m$ divides the denominator of the Bernoulli number $B_{n-1}$.

Using the Von Staudt–Clausen theorem, there may be a way to proof that that factors of the Bernoulli number denominators may never divide a mersenne number.

• You should add that $a$ must be coprime to $m$. Jul 28 '14 at 20:25
• You're going to run out of Fermat primes... Jul 28 '14 at 21:24
• @alex.jordan, I don't think that has been proven, their still could be an infinite amount of fermat primes. Jul 28 '14 at 21:27
• That's not what I meant exactly. Go up a few more $B_{2^n}$, and you will still be too small for another Fermat prime, but too big to only be built out of first powers of $2, 3, 5, 17, 257$, and $65537$. Maybe Fermat numbers pick up the slack, but they aren't prime. Jul 28 '14 at 21:29
• You would have to look at $B_{2^n-2}$, not at $B_{2^n}$. Jul 28 '14 at 22:02

Just some initial observations:

Suppose $m=2^n-1$ and suppose $m$ is Carmichael. If $p$ is prime and $p \mid m$, then $p -1\mid m-1=2(2^{n-1}-1)$. Since $2^{n-1}-1$ is odd, we must have $p \equiv 3 \pmod 4$ for all $p \mid m$.

For $n \ge 2$, $m \equiv 3 \pmod 4$. $m$ is Carmichael and hence square free. If $$m = \prod_{i=1}^kp_i\qquad\text{for p_i distinct primes}$$

then

\begin{align} m&\equiv \prod_{i=1}^k3 \pmod 4\\ &\equiv \prod_{i=1}^k(-1) \pmod 4\\ &\equiv (-1)^k \pmod 4 \end{align}

So $k$ must be odd, and $m$ is the product of an odd number of distinct primes with $p_i \equiv 3 \pmod 4$.

Certainly $2^n \equiv 1 \pmod m$, and since $2^k<m$ for $m<n$, $2$ has order $n$ modulo $m$. But $$2^{m-1} \equiv 1 \pmod m$$ so $n \mid m-1$. In particular, $2^n \equiv 2 \pmod n$, so $n$ is either prime, a pseudoprime to the base $2$ or $n$ is even and $2^{n-1} = 1 \pmod{\frac n2}$.

None of these conclusions are that restrictive, since we know that a Mersenne number can be prime! I'll try to post more as I think of it.

Let say $2^t-1$ has n prime factors like {$p_1,p_2,p_3,..,p_n$}.

If it is Carmichael number than $2^t-2$ should divisible by all n numbers which are like {$num_1=p_1-1,num_2=p_2-1,num_3=p_3-1,..,num_n=p_n-1$} and all those numbers are even.

$2^t-2=2*(2^{t-1}-1))$ because of that equality n numbers all should just be just divisible by 2 once.Then the prime factors should like {$p_1=2^{k_1}+4*m_1-1,p_2=2^{k_2}+4*m_2-1,p_3=2^{k_3}+4*m_3-1,..,p_n=2^{k_n}+4*m_n$$-1} .Then 2^t-1= \prod_{i=1}^n{(2^{k_i}+4*m_i-1)} , from there we understand n\pmod2=1 because (-1)^n==-1 should satisfy for equality else 2^{t-1}= even+even+even+...+even+1 will broke equality.That is where i am at when i do some more i send progress. Your argument must be corrected first. You assume that 2^p-1 nay have the possibility of being Carmichael number. In the next step you use the theorem of A Korsel t (1899) that 2^p-1=m is a Carmichael number if and only if m is square free and every prime factor q of m is such that q-1|m-1 In your proof you have assume that2^p-1=2kp+1=m which is true.m-1=2^p-2 and it is true that p is a factor of m-1 which is obvious. Also ,k is a factor of m-1=2^p-2 . You have not use the theorem correctly .First of all you must find the prime factors of m but not m-1. Theorem (A. Korselt 1899): A positive composite integer is a Carmichael number if and only if is square-free, and for all prime divisors of , it is true that . You want to know what is k. 2^p-1=(1+1)^p-1=1+C_1^p+-------------+C_(p-1)^p=1+kp Every binomial constant is divisible by p for a prime p, then k is obvious. Use your argument in the following way. Example. Take p=11, 2^p-1=2047=m Prime factors of m are 23 and 89. m is square free. Take p=23,p-1=22,m-1=2046,22|2046 Now take p=89,p-1=88. Note that 88 does not divide 2046. Therefore 2^p-1 is not a Carmichael number when p=11. Partial Proof I have found a proof for numbers with an even number of factors, and a prime exponent. (m = 2^p-1 and p > 2) First note that 2^p-1 \equiv 3 \mod 4 for p > 1. Next note the following table for a*b \mod 4:$$ \begin{array}{c|lcr} b & a = 0 & a = 1 & a = 2 & a = 3 \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 \\ 2 & 0 & 2 & 0 & 2 \\ 3 & 0 & 3 & 2 & 1 \\ \end{array}$$Because the only results$3 \mod 4$in the table involve$3 \mod 4$as a factor. At least one factor of$2^n-1$must be congruent to$3 \mod 4$because$2^n-1 \equiv 3 \mod 4$. And because$3*3 \equiv 1 \mod 4$The amount of such factors must be odd. Note that factors of$2^p-1$must be of the form$2kp+1$for some value$k$. Assuming$p$to be odd,$p = 2a+1$, and then$2kp+1 = 2k(2a+1)+1 = 4ka+2k+1$. Next$4ka+2k+1 \equiv 2k+1 \mod 4$Based of the fact that the amount of factors congruent to$3 \mod 4$have to be odd, if the number of factors of$m = 2^p-1$is even, then for at least one factor$q$,$q \equiv 1 \mod 4$. Thus$2kp+1 \equiv 1 \mod 4$, so$2k+1 \equiv 1 \mod 4$and$2k \equiv 0 \mod 4$. Which means$k$is even. From a portion proved above, if there is a value$k$in which$q = 2kp + 1$for which$q$is a factor of$2^p-1$, in which$k$does not divide$2^{p-1}-1$, then$2^p-1$is never a Carmichael number. Because an even number never divides an odd number, an even$k$does not divide$2^{p-1}$. This even$k$value is the one proven above. So if the number of factors of$2^p-1$is even,$2^p-1\$ is never a Carmichael number.