Uso de Fermat ' s teorema para probar 10001 es compuesto

Question

Necesito utilizar Teorema de Fermat para demostrar que no es primer 10001. Entiendo que sólo tengo que encontrar un contraejemplo donde <span class="math-container">$a^{10000}$</span> 10001 = 1 mod mod 10001 no verdadera, pero esto parece difícil con tal cantidad. ¿Alguna idea?

Answer 1

Otro método, también basado en el de Fermat poco teorema, es la siguiente.

Primer aviso de $$10001=10^4+1=\frac{10^8-1}{10^4-1}$$

Por lo que encontrar un primer factor de $10^8-1$ que no es también un factor de $10^4-1$ es suficiente. Los factores primos de a$10^4-1$ son fáciles de determinar, incluso, por la mano de cálculo : $3,11,101$ Otro primer dividiendo $10^8-1$ debe ser de la forma $8k+1$

Esto es debido a que el menor entero positivo $k$ con $\ 10^k\equiv 1\mod q\ $ (el orden de $10$ modulo $q$) $8$ y Fermat poco teorema da $\ 10^{q-1}\equiv 1\mod q\ $ que muestra $8\mid q-1$. Así, sólo tenemos que verificar los números primos de la forma $8k+1$. Los tres primeros se $17,41,73$

$73$ que resulta de dividir $10001$ , y se demuestra que $10001$ es compuesto.

Para un poco de números más grandes (pero no demasiado grande) de una forma especial este método debe ser superior a la del cálculo directo de la energía.

Answer 2

Pseudoprimes Fermat a cualquier base dada son realmente muy raros, por lo que así sólo podría iniciar <span class="math-container">$2$</span> y esperanza de lo mejor. Esto es un poco tedioso pero repetido perfectamente factible por cuadratura: <span class="math-container">%#% $ #%</span> por lo que sólo necesitará mantener escuadra <span class="math-container">$$10000 = 2^{13}+2^{10}+2^9+2^8+2^4$</span> (modulo <span class="math-container">$2$</span>) trece veces.

Answer 3

Esto es un poco un truco, pero otro Teorema de Fermat dice que <span class="math-container">$10001$</span> no puede ser primer porque tiene dos diferentes representaciones como la suma de dos cuadrados:

<span class="math-container">$$10001=100^2+1^2=65^2+76^2$$</span>

El "truco" aquí es que, mientras que <span class="math-container">$100^2+1^2$</span> es bastante fácil encontrar el punto, el otro suma de dos cuadrados involucrados casi como trabajar mucho buscando los factores ellos mismos habrían tomado.

Answer 4

De 5 dígitos tamaño de los números aún puede utilizar la factorización de Fermat método y una diferencia de dos cuadrados. Si su número de $10001$ tiene un mínimo de dos factores, que no será en una gran distancia entre uno y otro. En este caso sucedió que sólo $5$ plazas a partir de $100$ es necesario examinar:

$105^2-32^2=11025-1024=10001$

Así que la solución es que $10001$ es un número compuesto con dos factores primos:

$(105+32)\cdot(105-32)=137 \cdot 73=10001$

Para números muy grandes hay otro método, sin embargo a la larga a describir aquí, lo que resulta en:

$10001= 3\cdot3333+2=\sum (5403+3333+1263)+2$

En este 3-término de una progresión aritmética de la diferencia entre los términos se puede expresar:

$d=2\cdot x\cdot y=2\cdot1035=2\cdot23\cdot45$

... donde $x$ e $y$ son variables de dos números primos. Plugin de ellos junto con un coeficiente inicial número $3$ resultados en:

$(3\cdot23+4)(3\cdot45+2)=73\cdot137=10001$