Publicaciones de la categoría: Fermat

Absolutamente … Pseudoprimo

de cosas el septiembre 18, 2016 | 1 comentario

images

Sabemos que un número compuesto se dice «pseudoprimo» si divide la expresión $\displaystyle\mathit{\mathbf{2^n-2}}$ , lo cual no es otra cosa que un caso especial del llamado Pequeño Teorema de Fermat.

Si un número compuesto $\displaystyle\mathit{\mathbf{n}}$ divide la expresión $\displaystyle\mathit{\mathbf{3^n-3}}$ , o a la expresión $\displaystyle\mathit{\mathbf{4^n-4}}$ , o a $\displaystyle\mathit{\mathbf{5^n-5}}$ , etc podemos decir que dicho número tiene la «propiedad de la pseudoprimalidad«.

El próximo paso consiste en plantear el caso general: un número compuesto que divida a $\displaystyle\mathit{\mathbf{2^n-2}}$ , $\displaystyle\mathit{\mathbf{3^n-3}}$ , $\displaystyle\mathit{\mathbf{4^n-4}}$ , $\displaystyle\mathit{\mathbf{a^n-a}}$ para cada número entero $\displaystyle\mathit{\mathbf{a}}$ . En este caso estamos en presencia de lo que podríamos denominar un «número pseudoprimo absoluto«.

Cabe preguntarse si este número pseudoprimo absoluto existe realmente, y la respuesta es sí!!. El más pequeño de los números pseudoprimos absolutos es el 561, o sea el número 561 es un número compuesto que divide la expresión $\displaystyle\mathit{\mathbf{a^{561}-a}}$ para cualquier valor de $\displaystyle\mathit{\mathbf{a}}$ . Esto es relativamente fácil de demostrar a partir del Pequeño Teorema de Fermat, de la siguiente manera:

(1) La descomposición del número 561 en sus factores primos es la siguiente: 3 x 11 x 17; necesitamos entonces demostrar que $\displaystyle\mathit{\mathbf{a^{561}-a}}$ es divisible en cada uno de los factores primos de 561.

(2) Analizamos primero la divisibilidad en el factor 3:

$\displaystyle\mathit{\mathbf{a^{561}-a=a(a^{560}-1)=a[(a^2)^{280}-(1^2)^{280}]}}$

$\displaystyle\mathit{\mathbf{a^{561}-a=a(a^{560}-1)=a[(a^2-1) (.....)]}}$

$\displaystyle\mathit{\mathbf{a^{561}-a=a(a^{560}-1)=(a^3-a) (.....)}}$

Al ser 3 un número primo por el Pequeño Teorema de Fermat divide a la expresión $\displaystyle\mathit{\mathbf{a^3-a}}$ por lo tanto también divide a $\displaystyle\mathit{\mathbf{a^{561}-a}}$ .

(3) Analizamos la divisibilidad en el factor 11:

$\displaystyle\mathit{\mathbf{a^{561}-a=a(a^{560}-1)=a[(a^{10})^{56}-(1^{10})^{56}]}}$

$\displaystyle\mathit{\mathbf{a^{561}-a=a(a^{560}-1)=a[(a^{10}-1) (.....)]}}$

$\displaystyle\mathit{\mathbf{a^{561}-a=a(a^{560}-1)=(a^{11}-a) (.....)}}$

Al ser 11 un número primo por el Pequeño Teorema de Fermat divide a la expresión $\displaystyle\mathit{\mathbf{a^{11}-a}}$ por lo tanto también divide a $\displaystyle\mathit{\mathbf{a^{561}-a}}$ .

(4) Finalmente analizamos la divisibilidad en el factor 17:

$\displaystyle\mathit{\mathbf{a^{561}-a=a(a^{560}-1)=a[(a^{16})^{35}-(1^{16})^{35}]}}$

$\displaystyle\mathit{\mathbf{a^{561}-a=a(a^{560}-1)=a[(a^{16}-1) (.....)]}}$

$\displaystyle\mathit{\mathbf{a^{561}-a=a(a^{560}-1)=(a^{17}-a) (.....)}}$

Al ser 17 un número primo por el Pequeño Teorema de Fermat divide a la expresión $\displaystyle\mathit{\mathbf{a^{17}-a}}$ por lo tanto también divide a $\displaystyle\mathit{\mathbf{a^{561}-a}}$ .

Otros números pseudoprimos absolutos son:

2.821 = 7 x 13 x 31 ; 10.585 = 5 x 29 x 73 ; 15.841 = 7 x 31 x 73

Al día de hoy no se sabe si existen infinitos números pseudoprimos absolutos.

Notas:

(1) Este es post es una traducción y resumen de parte del capitulo 1 del libro Mathematical Gems (ver referencia) y es el tercer post de una serie de cinco a publicar sobre el tema.

Serie Teoría de Números:

Post N° 1: El Pequeño Teorema de Fermat – Una demostración directa y simple.

Post Nº 2: Un antiguo Problema Chino.

Referencias:

# Mathematical Gems I – Ross Honsberger – Mathematical Association of America – 1973 – (Colección: The Dolcialni Mathematical Expositions Vol. 1) – Chapter 1 – pp 4-5.

Maravilloso libro, lleno de gemas matemáticas como su título así lo indica. Todo lo que escribió Ross Honsberger es un placer de leer y trabajar al mismo tiempo. Casi todos sus libros están colgados en alguna parte de internet y se puede acceder a ellos.

Publicado en: Fermat, Teoría de Números

Un antiguo Teorema Chino

de cosas el May 20, 2014 | 2 comentarios

El Pequeño Teorema de Fermat establece que:

Si $\displaystyle \mathit{\mathbf {p}}$ es un número primo, entonces para cada número $\displaystyle \mathit{\mathbf {a}}$ el número $\displaystyle \mathit{\mathbf {a^p-a}}$ es divisible en $\displaystyle \mathit{\mathbf {p}}$ .

Para $\displaystyle\mathit{\mathbf{a=2}}$ , el Pequeño Teorema de Fermat nos dice que la expresión $\displaystyle\mathit{\mathbf{2^p-2}}$ es divisible en $\displaystyle\mathit{\mathbf{p}}$ si $\displaystyle\mathit{\mathbf{p}}$ es un número primo. Es natural, entonces, preguntarse si el recíproco de esta afirmación es válida tambien, o sea:

Si un númeto entero positivo $\displaystyle \mathit{\mathbf {n>1}}$ divide la expresión $\displaystyle \mathit{\mathbf {2^n-2}}$ ´¿es $\displaystyle \mathit{\mathbf {n}}$ un número primo?.

Hace 2500 años los chinos llegaron a la conclusión que la afirmación era válida, para ello chequearon infinidad de valores de $\displaystyle \mathit{\mathbf {n}}$ y luego cálculos posteriores confirmaron que para $\displaystyle\mathit{\mathbf{1<n<300}}$ los únicos valores de $\displaystyle\mathit{\mathbf{n}}$ que dividen la expresión $\displaystyle \mathit{\mathbf {2^n-2}}$ son números primos.

No es difícil demostrar que este antiguo teorema chino es incorrecto. El número $\displaystyle\mathit{\mathbf{n=341}}$ proporciona un contraejemplo. Al ser 341 el resultado de hacer 11 veces 31, el número 341 no es primo, pero divide la expresión $\displaystyle \mathit{\mathbf {2^{341}-2}}$ . Esto último se puede demostrar fácilmente partiendo del hecho que toda expresión de la forma $\displaystyle\mathit{\mathbf{x^m-y^m}}$ tiene como factor a $\displaystyle\mathit{\mathbf{x-y}}$ para cualquier número positivo $\displaystyle\mathit{\mathbf{m}}$ . Entonces tenemos que:

$\displaystyle\mathit{\mathbf{2^{341}-2=2(2^{340}-1)}}$

$\displaystyle\mathit{\mathbf{2^{341}-2=2[(2^{10})^{34}-1^{34}]}}$

$\displaystyle\mathit{\mathbf{2^{341}-2=2[(2^{10}-1)(....)]}}$

$\displaystyle\mathit{\mathbf{2^{341}-2=2[(1023)(....)]}}$

$\displaystyle\mathit{\mathbf{2^{341}-2=2[3(341)(....)]}}$ entonces los números enteros $\displaystyle\mathit{\mathbf{n}}$ como el 341, que no son números primos pero dividen la expresión $\displaystyle \mathit{\mathbf {2^n-2}}$ se denominan «números pseudoprimos«.

Diversas preguntas respecto de los números pseudoprimos se pueden plantear: ¿es 341 el único número pseudoprimo?, ¿hay infinitos números pseudoprimos?. Resulta que para cada número pseudoprimo impar existe un número pseudoprimo impar mayor, por lo tanto a partir del 341 existen infinitos números pseudoprimos impares.

Otra pregunta que se deriva naturalmente del párrafo anterior es ¿existen números pseudoprimos pares?. En el año 1950 el americano D.H. Lehmer descubrió el número pseudoprimo par 161038 y si bien el descubrimiento en sí fue dificultoso es fácil demostrar que 161038 es un número pseudoprimo. Partimos del análisis de los factores primos que lo forman: 2 . 73 . 1103 y a partir de los mismos tenemos que:

$\displaystyle\mathit{\mathbf{2^{161038}-2=2(2^{161037}-1)}}$

Por lo tanto es necesario demostrar solamente que tanto el número 73 como el 1103 dividen a la expresión $\displaystyle\mathit{\mathbf{(2^{161037}-1)}}$ .

(#) Comenzamos con en número 73, para ello descomponemos en sus factores primos a 161037 de la siguiente manera: $\displaystyle\mathit{\mathbf{3^{2} . 29 . 617}}$ por lo tanto tenemos que:

$\displaystyle\mathit{\mathbf{2^{161037}-1=(2^{9})^{29617}-1^{29617}}}$

$\displaystyle\mathit{\mathbf{2^{161037}-1=(2^{9}-1)(....)}}$

$\displaystyle\mathit{\mathbf{2^{161037}-1=(511)(....)}}$

$\displaystyle\mathit{\mathbf{2^{161037}-1=7(73)(....)}}$

Así demostramos que la expresión $\displaystyle\mathit{\mathbf{(2^{161037}-1)}}$ es divisible en 73.

(#) Análisis similar hacemos para el número 1103:

$\displaystyle\mathit{\mathbf{2^{161037}-1=(2^{29})^{9617}-1^{9617}}}$

$\displaystyle\mathit{\mathbf{2^{161037}-1=(2^{29}-1)(....)}}$

$\displaystyle\mathit{\mathbf{2^{161037}-1=1103(486737)(....)}}$

También demostramos, entonces, que la expresión $\displaystyle\mathit{\mathbf{(2^{161037}-1)}}$ es divisible en 1103.

Por lo tanto dado que 73 y 1103 son ambos números primos, que la divisibilidad de uno no afecta la devisibilidad del otro y a la vez ambos son divisores de la expresión $\displaystyle\mathit{\mathbf{(2^{161037}-1)}}$ , entonces 161308 es un númeto pseudoprimo par.

En el año 1951 el holandés N.G.W. Beeger demostró que existen, también, infinitos números pseudoprimos pares.

Notas:

(1) Este es post es una traducción y resumen de parte del capitulo 1 del libro Mathematical Gems (ver referencia) y es el segundo post de una serie de cinco a publicar sobre el tema.

Serie Teoría de Números:

Post N° 1: El Pequeño Teorema de Fermat – Una demostración directa y simple.

(2) Número Pseudoprimo ( Pseudoprime ).

(3) Se pueden ver tablas de números pseudoprimos aquí.

Referencias:

# Mathematical Gems I – Ross Honsberger – Mathematical Association of America – 1973 – (Colección: The Dolcialni Mathematical Expositions Vol. 1) – Chapter 1 – pp 3-4.

Maravilloso libro, lleno de gemas matemáticas como su título así lo indica. Todo lo que escribió Ross Honsberger es un placer de leer y trabajar al mismo tiempo. Casi todos sus libros estan colgados en alguna parte de internet y se puede acceder a ellos.

# Pseudoprime – Wolfram Math World.

Publicado en: Fermat, Historia Matemática, Teoría de Números, Teoremas

El Pequeño Teorema de Fermat – Una demostración directa y simple

de cosas el May 7, 2014 | 10 comentarios

En una carta a Bernard Frenicle de Bessy in 1640, el gran teórico de los números francés Pierre de Fermat propuso el siguiente teorema (en realidad no era un teorema propiamente dicho sino más bien una conjetura):

Ejemplo: Tomamos $\displaystyle p=23$ un número primo, entonces $\displaystyle a^p-a$ es divisible en $\displaystyle p$ sea $\displaystyle a$ un número entero cualquiera (positivo, negativo o cero).

Fermat sostenía que tenía una demostración del teorema, pero según le cuenta a Frenicle de Bessy, esta era demasiado extensa para incluirla en la carta. El primero en demostrar el teorema fue Gottfried Leibniz en un manuscrito en 1683 que no llegó a publicar. La primera demostración publicada, casi cien años después, es de Leonhard Euler, quien en 1736 la presentó en un artículo titulado Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio.

Hasta los inicios del siglo XX este teorema era conocido como «teorema de Fermat» , en 1913 el matemático Kurt Hensel en su libro Zahlentheorie lo rebautiza como «pequeño teorema de Fermat» tal como se conoce actualmente.

Si bien parace que demostrar este teorema requiere de una matemática avanzada, es sorprendente encontrar que puede demostrarse de manera sencilla y directa utilizando nada más que inducción matemática y el teorema del binomio.

A continuación el desarrollo la demostración:

(1) Sea $\displaystyle p$ un número primo:

Si $\displaystyle a=0$ $\longrightarrow$ $\displaystyle 0^p-0=0$ divisible en $\displaystyle p$
Si $\displaystyle a=1$ $\longrightarrow$ $\displaystyle 1^p-1=0$ divisible en $\displaystyle p$

(2) Suponemos que si para todos los valores positivos de $\displaystyle a$ tenemos que $\displaystyle a^p-a$ es divisible en $\displaystyle p$ por inducción matemática la hipótesis es válida también para $\displaystyle a+1$ , entonces tenemos que:

$\displaystyle a^p-a$ es divisible en $\displaystyle p$
$\displaystyle (a+1)^p-(a+1)$ es divisible en $\displaystyle p$

Por Teorema del Binomio sabemos que:

$\displaystyle (a+1)^p = a^p+ \binom{p}{1} a^{p-1}+ \binom{p}{2} a^{p-2}+...+\binom{p}{p-1} a+1$

Hacemos pasaje de términos y obtenemos:

$\displaystyle (a+1)^p-a^p-1 = \binom{p}{1} a^{p-1}+ \binom{p}{2} a^{p-2}+...+\binom{p}{p-1} a$

$\displaystyle (a+1)^p-(a^p+1) = \binom{p}{1} a^{p-1}+ \binom{p}{2} a^{p-2}+...+\binom{p}{p-1} a$ (1)

En el lado derecho de la ecuación (1) encontramos que cada coeficiente $\displaystyle \binom{p}{k}$ con $\displaystyle k=1,2,3,...,p-1$ es divisible en $\displaystyle p$ . Por la propia definición de $\displaystyle \binom{p}{k}$ tenemos que:

$\displaystyle \binom{p}{k}k!=p(p-1)(p-2)...(p-k-1)$ aquí $\displaystyle p$ divide la parte derecha de la ecuación. Para todos los coeficientes de la expresión, $\displaystyle k$ es un valor menor a $\displaystyle p$ , entoces el factor primo $\displaystyle p$ no ocurre en el producto $\displaystyle k!$ , por lo tanto $\displaystyle p$ divide a $\displaystyle \binom{p}{k}$ .

Entonces como $\displaystyle p$ divide a cada coeficiente del lado derecho de la ecuación (1), debe dividir también a la expresión completa del lado derecho y consecuentemente divide también el lado izquierdo $\displaystyle \longrightarrow (a+1)^p-(a^p+1)$ .

A partir de la hipótesis inductiva que $\displaystyle p$ divide a $\displaystyle a^p-a$ , tenemos que:

$\displaystyle [(a+1)^p-a^p-1]+[a^p-a]$ $\displaystyle =$ $\displaystyle (a+1)^p-\not{a^p} -1+\not{a^p} -a$

$\displaystyle [(a+1)^p-a^p-1]+[a^p-a]$ $\displaystyle =$ $\displaystyle \mathbf {(a+1)^p-(a+1)}$

Por lo tanto por inducción matemática la hipótesis es valida para todos los valores positivos de $\displaystyle a$ .

(3) La demostración se completa considerando los valores negativos de $\displaystyle a$ . Entonces definimos a los valores negativos de $\displaystyle a$ como $\displaystyle\mathbf {-a}$ .

– Si $\displaystyle p$ es igual a $\displaystyle 2$ , tenemos que:

$\displaystyle (-a)^p-(-a)=(-a)^p+a=a^2+a=\mathbf{a(a+1)}$

Los factores $\displaystyle\mathbf {a}$ y $\displaystyle\mathbf {(a+1)}$ son consecutivos, entonces uno de ellos es par y su producto divisible en $\displaystyle 2$ .

– Si $\displaystyle p$ es impar:

$\displaystyle (-a)^p-(-a)=-a^p+a=\mathbf{-(a^p-a)}$

Sabemos que si $\displaystyle a$ es positivo divide a $\displaystyle (a^p-a)$ , por lo tanto tambien divide a $\displaystyle -(a^p-a)$ .

$\displaystyle \mathbf{Q.E.D}$ (quod erat demonstrandum).

Notas:

(1) Este post es una traducción y resumen de parte del capitulo 1 del libro Mathematical Gems (ver referencia) y forma parte de una serie de cinco posts a publicar sobre el tema.

(2) El Pequeño Teorema de Fermat se puede enunciar de diferentes maneras:

Si $\displaystyle p$ es un número primo, entonces $\displaystyle p$ divide a $\displaystyle a^{p-1}-1$ para cada número entero $\displaystyle a$ coprimo con $\displaystyle p$ .
Si $\displaystyle p$ es un número primo, entonces, para cada número natural $\displaystyle a$ , $\displaystyle a^p \equiv a$ (mod $\displaystyle p$ ).
Si $\displaystyle p$ es un número primo, entonces, para cada número natural $\displaystyle a$ coprimo con $\displaystyle p$ , $\displaystyle a^{p-1} \equiv 1$ (mod $\displaystyle p$ ).

(3) Se dice que dos números $\displaystyle\mathbf a$ y $\displaystyle\mathbf b$ son números primos entre sí ( coprimos – coprime – o primos relativos – relatively prime – ), si no tienen ningún factor primo en común, o sea no tienen otro divisor común más que 1 o -1.

(4) En un post anterior «Números Primos: Una fórmula para generarlos» explicamos como utilizar el pequeño teorema de Fermat como test de primalidad, o sea un test para definir si un determinado número es primo o compuesto.

Referencias:

# Mathematical Gems I – Ross Honsberger – Mathematical Association of America – 1973 – (Colección: The Dolcialni Mathematical Expositions Vol. 1) – Chapter 1 – pp 1-3.

Maravilloso libro, lleno de gemas matemáticas como su título así lo indica. Todo lo que escribió Ross Honsberger es un placer de leer y trabajar al mismo tiempo. Casi todos sus libros estan colgados en alguna parte de internet y se puede acceder a ellos.

# Pequeño Teorema de Fermat – Wikipedia (consultado 07/05/2014).

# Fermat´s Little Theorem – Wolfram Math World.

Publicado en: Fermat, Historia Matemática, Teoría de Números, Teoremas

Apuntes Matemáticos

Publicaciones de la categoría: Fermat

Absolutamente … Pseudoprimo

Un antiguo Teorema Chino

El Pequeño Teorema de Fermat – Una demostración directa y simple

Temas

Estadísticas del sitio