34
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You should add that $a$ must be coprime to $m$. $\endgroup$ – ccorn Jul 28 '14 at 20:25
  • $\begingroup$ You're going to run out of Fermat primes... $\endgroup$ – alex.jordan Jul 28 '14 at 21:24
  • $\begingroup$ @alex.jordan, I don't think that has been proven, their still could be an infinite amount of fermat primes. $\endgroup$ – Dane Bouchie Jul 28 '14 at 21:27
  • 1
    $\begingroup$ 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. $\endgroup$ – alex.jordan Jul 28 '14 at 21:29
  • 1
    $\begingroup$ You would have to look at $B_{2^n-2}$, not at $B_{2^n}$. $\endgroup$ – ccorn Jul 28 '14 at 22:02
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\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.