Can a Mersenne number ever be a Carmichael number?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.