Publicaciones de la categoría: Teoría de Números

Absolutamente … Pseudoprimo

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

 

Anuncios

Un antiguo Teorema Chino

_matteo_ricci_05

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.

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

Fermat

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):

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}} .

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í ( coprimoscoprime – o primos relativosrelatively 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.

 

 

 

Estoy leyendo…

RTN

Encontré en internet una copia de Recreations in the Theory of Numbers de Albert H. Beiler (Dover – 1966). Con un inglés elemental se puede leer y disfrutar sin problemas. El libro cubre lo básico de Teoría de Números desde un punto de vista recreativo, bien explicado, buenos ejemplos, detallando distintas técnicas para la resolución de problemas, contexto histórico, etc.

En el primer capítulo el autor plantea una serie de problemas para ejemplificar el contenido de la Teoría de Números, los dejo aquí planteados para el que se anime:

1- Encontrar los divisores, si los tiene, de 16000001.

2- Un lado de un triángulo rectágulo cualquiera mide 48 cm. Encontrar diez pares de números enteros que representen la medida de los otros dos lados del triángulo dado.

3- ¿Cuántos números enteros positivos hay menores que y sin un divisor común con 5929?

4- Encontrar el mínimo número formado sólo de tres y sietes de manera que este número y la suma de sus dígitos sean divisibles en 3 y en 7.

5- Encontrar tres númetos cuadrados en progresión aritmética. ¿Habrá cuatro de ellos?

6- Encontrar el mínimo número con exactamente 100 divisores (propios).

7- Mostrar que 1\times 2\times 3\times 4...(n-1)+1 es siempre divisible en n si n es un númeto primo, pero nunca si n es un número compuesto.

8- Probar que cada número primo de la forma 4x+1 es expresable como la suma de dos enteros cuadrados en solo un única manera.

9- Encontrar números cada uno de los cuales sea igual a la suma de todos sus diferentes divisores (excluído el propio número, pero incluida la unidad).

10- Encontrar una fórmula general para los valores de x para los cuales 2^x-1 es un número primo.

11- Probar que cada número par se puede representar como la suma de dos números primos.

12- Probar que \displaystyle x^n+y^n=z ^n es imposible para números enteros con n mayor que 2.

De los doce problemas planteados, hay tres que al momento de editarse el libro, año 1966, no habían sido resueltos. A la fecha, el problema 12, que no es otro que el Último Teorema de Fermat, fue demostrado en 1993 por el matemático inglés Andrew Wiles, por lo que pasó a llamarse Teorema de Fermat-Wiles.

Es interesante aprender la opinión de grandes matemáticos a través de la historia respecto de la Teoría de Números, sobre todo en dos aspectos: la valoración de la inutilidad de la Teoría de Números para cualquier aplicación práctica y la dualidad manifiesta en la simpleza de sus planteos junto a la dificultad de sus soluciones.

El matemático alemán Ernst Kummer consideraba su trabajo sobre los números ideales como el más importante ya que no estaba “manchado” por ninguna aplicación práctica.

Otro grande como David Hilbert expresaba: “En Teoría de Números, valoramos la simplicidad de sus fundamentos, la exactitud de su concepción y la puresa de sus verdades; la exaltamos como el modelo para otras ciencias, como la más profunda e inagotable fuente de conocimiento matemático, pródiga en incitaciones a la investigación en otras áreas de la matemática…además la Teoría de Números es independiente a los cambios de moda,  y en ella no vemos, cómo sucede en otras áreas del conocimiento, nociones o métodos en un momento con excesiva importancia,  y en  otro sufriendo un descuido inmerecido; en Teoría de Números el más antiguo de los problemas es usualmente actual hoy en día, como una genuina obra de arte del pasado.”

El inglés G.H. Hardy, comentaba al respecto: “La Teoría de Números Elemental debe ser uno de los mejores temas en la más temprana educación matemática. Demanda muy poco conocimiento previo; trata de asuntos tangibles y familiares; el proceso de razonamiento que emplea es simple, general y resumido; y es única entre las ciencias metemáticas en cuanto a su atractivo a la natural curiosidad humana. Un mes de enseñanza inteligente en Teoría de Números debe ser el doble de instructiva, el doble de útil, y al menos diez veces más divertida que la misma cantidad de cálculo para ingenieros”.

El matemático J.V. Unspensky en su Elementary Number Theory concluye: “¿Qué, entonces, obliga a los hombres a  dedicar tanto tiempo y esfuerzo en investigaciones aritméticas?… La respuesta está en que toda la belleza de esta ciencia se vuelve aparente sólo a aquellos que se sumergen profundamente en ella… Es natural que el estudio preliminar del tema [teoría de números] no sea muy interesante en si mismo como para apreciar los tesoros aritméticos que contiene. Esto es inevitable: antes de aprender a caminar uno debe aprender a gatear.”

Lamentablemente, la enseñanza de la matemática, está lejos siquiera de acercarse a todo lo expuesto y con suerte, de grandes, como es mi caso, descubrimos todo este mundo increíble, como consuelo queda agregar: “mejor tarde que nunca”.

Referencia:

# Recreations in the Theory of Numbers – Albert H. Beiler – Dover (1966).

(Se puede descargar el libro desde aquí)