Puede un Mersenne número de nunca ser un número de Carmichael?

Question

Puede un Mersenne número de nunca ser un número de Carmichael?

Más específicamente, puede un número compuesto $m$ de la forma $2^n-1$ cada vez pasa la prueba: $a^{m-1} \equiv 1 \mod m$ para todos los intergers $a >1$ (Fermat Prueba)?

Los casos potencialmente resultó tan lejos: (Que nunca son los números de Carmichael)

• donde $n$ es impar
• donde $n$ es el prime
• donde $n = \lambda(m)$ (El Carmichael función)

Trabajo utilizando la "principal" de la definición:

En primer lugar toma la definición de un número de Carmichael:

Un positivo compuesto entero $m$ es un número de Carmichael si y sólo si $m$ es la plaza libre, y para todos los primos divisores de $p$ de $m$, es cierto que $p - 1 \mediados de los m - 1$.

Supongamos que $m=2^n-1$ es squarefree. (Mejor de los casos, y creo que siempre es por $2^p-1$)

Tomemos el caso donde $n$ (en $2^n-1$), es un excelente $p$. Todos los factores de $2^p-1$ debe de la forma: $2kp+1$ para algunas constantes de $k$. Así se $2kp$ nunca dividir $2^p-2$? El Factoring $2$ nos da $kp \mid 2^{p-1}-1$, o dividirse en dos: $k \mid 2^{p-1}-1$ y $p \mid 2^{p-1}-1$ deben ser ambos verdaderos. Por Fermat poco teorema, $2^{p-1} \equiv 1 \mod p$, entonces $p \mid 2^{p-1}-1$ siempre es cierto.

Así que si $k \mid 2^{p-1}-1$ para $k = {q-1 \sobre p}$, es falso por lo menos un factor de $p$ de $2^p-1$, no los números de Carmichael puede existir de forma $2^p-1$.

Ahora para otros casos donde $$ n es compuesto, digamos $n=cp$, para algunos el primer $p$, y algún número $de c$:

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

Por lo tanto: $2^{n-1} \mid 2^p-1$

Por eso, debemos mirar los factores de $2^p-1$ la hora de considerar si $2^{cp}-1$ es un número de Carmichael. Así que sabemos que esos factores son ya de la forma $2kp+1$, entonces $kp \mid 2^{cp-1}-1$.

Aquí es donde me quedo. en una prueba incompleta.

El uso de Bernoulli definición:

Un extraño compuesto squarefree número $m$ es un número de Carmichael iff $m$ divide el denominador del número de Bernoulli $B_{n-1}$.

El uso de Von Staudt–Clausen teorema, puede ser una forma de prueba de que los factores de Bernoulli número denominador nunca puede dividir un mersenne número.

Answer 1

Sólo algunas observaciones iniciales:

---

Supongamos que $m=2^n-1$ y supongamos que $m$ es de Carmichael. Si $p$ es primo y p $\mediados de m$, entonces $p -1\mediados de los m-1=2(2^{n-1}-1)$. Desde $2^{n-1}-1$ es impar, se debe tener $p \equiv 3 \pmod 4$ para todo $p \mediados de m$.

Para $n \ge 2$, $m \equiv 3 \pmod 4$. $m$ es Carmichael y, por tanto, de la plaza libre. Si $$m = \prod_{i=1}^kp_i\qquad\text{para $p_i$ distintos números primos}$$

entonces

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

Por lo que $k$ debe ser impar, y $m$ es el producto de un número impar de distintos primos con $p_i \equiv 3 \pmod 4$.

---

Ciertamente, $2^n \equiv 1 \pmod m$, y desde $2^k<m$ para $m<n$, $2$ es de orden $n$ modulo $m$. Pero $$2^{m-1} \equiv 1 \pmod m$$ por lo que $n \mediados de los m-1$. En particular, $2^n \equiv 2 \pmod n$, entonces $n$ es primo, un pseudoprime a la base de $2$ o de $n$ es par y $2^{n-1} = 1 \pmod{\frac n2}$.

---

Ninguna de estas conclusiones son que restrictiva, ya que sabemos que una de Mersenne número puede ser el primer! Voy a intentar publicar más como yo lo pienso de ella.

Answer 2

Digamos de $2^t-1$ n primer factores como {$p_1,p_2,p_3,..,p_n$}.

Si es Carmichael cantidad de $2^t-2$ debe divisible por todos los n números que son como {$num_1=p_1-1,num_2=p_2-1,num_3=p_3-1,..,num_n=p_n-1$} y todos los números son aún.

$2^t-2=2*(2^{t-1}-1))$, debido a que la igualdad n números sólo debe ser sólo divisible por 2 vez.A continuación, el primer factores como {$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$} .Entonces $2^t-1= \prod_{i=1}^n{(2^{k_i}+4*m_i-1)} $, a partir de ahí entendemos $n\pmod2=1$ porque $(-1)^n==-1$ debe satisfacer para la igualdad otro de $2^{t-1}=+incluso+incluso+...+incluso+1$ le rompió la igualdad.Que es de donde soy en cuando hago algunos más puedo enviar el progreso.

Answer 3

Su argumento se debe corregir primero. Se supone que 2^p-1 no tienen la posibilidad de ser Carmichael número. En el paso siguiente se utiliza el teorema de Korsel t (1899) que 2^p-1=m es un número de Carmichael si y sólo si m es la plaza libre y cada factor primo p de m es tal que p-1|m-1 En su prueba de que usted ha de asumir that2^p-1=2kp+1=m, lo cual es cierto.m-1=2^p-2 y es verdad que p es un factor de m-1, que es obvio. También ,k es un factor de m-1=2^p-2 . Usted no utilice el teorema correctamente .En primer lugar, usted debe encontrar los factores primos de m pero no m-1. Teorema (A. Korselt 1899): Una positiva compuesto entero es un número de Carmichael si y sólo si es cuadrado-libre, y para todos los primos divisores , es lo cierto que . Quieres saber lo que es k. 2^p-1=(1+1)^p-1=1+C_1^p+-------------+C_(p-1)^p=1+kp Cada binomio constante es divisible por p para un primo p, entonces k es obvio. Utilice su argumento de la siguiente manera. Ejemplo. Tomar p=11, 2^p-1=2047=m factores Primos de m son 23 y 89. m es la plaza libre. Tomar p=23,p-1=22,m-1=2046,22|2046 Ahora tomar p=89,p-1=88. Tenga en cuenta que el 88 no dividir 2046. Por lo tanto, 2^p-1 no es un número de Carmichael cuando p=11.

Answer 4

Parcial De La Prueba

He encontrado una prueba para los números con un número par de factores, y el principal exponente. ($m = 2^p-1$ y $p > 2$)

La primera nota que $2^p-1 \equiv 3 \mod 4$ para $p > 1$. La próxima nota en la tabla siguiente por $a*b \mod 4$: $$ \begin{array}{c|lcr} b & a = 0 y a = 1 y a = 2 y 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} $$

Debido a que los resultados de solo $3 \mod 4$ en la tabla de involucrar a $3 \mod 4$ como un factor. Al menos uno de los factores de $2^n-1$ debe ser congruente a $3 \mod 4$ porque $2^n-1 \equiv 3 \mod 4$. Y porque $3*3 \equiv 1 \mod 4$ La cantidad de factores debe ser impar.

Tenga en cuenta que los factores de $2^p-1$ debe ser de la forma $2kp+1$ para algún valor de $k$. Suponiendo que $p$ a ser impar, $p = 2a+1$, entonces $2kp+1 = 2k(2a+1)+1 = 4ka+2k+1$. Siguiente $4ka+2k+1 \equiv 2k+1 \mod 4$

Basado en el hecho de que la cantidad de factores congruentes a $3 \mod 4$ tiene que ser impar, si el número de factores de $m = 2^p-1$ es par, entonces por lo menos uno de los factores $q$, $q \equiv 1 \mod 4$. Mus $2kp+1 \equiv 1 \mod 4$, entonces $2k+1 \equiv 1 \mod 4$ y $2k \equiv 0 \mod 4$. Lo que significa que $k$ es par.

De una parte, demostró anteriormente, si hay un valor de $k$ que $q = 2kp + 1$ que $p$ es un factor de $2^p-1$, de los cuales $k$ no divide a $2^{p-1}-1$, entonces $2^p-1$ nunca es un número de Carmichael. Debido a que un número nunca se divide un número impar, incluso $k$ no divide a $2^{p-1}$. Esto incluso $k$ es el valor que uno demostrado anteriormente.

Así que si el número de factores de $2^p-1$ es, incluso, $2^p-1$ nunca es un número de Carmichael.