Números enteros | Gaussianos

Los números de Smith

Hoy os traigo un tipo de números curiosos tanto por su definición como por la historia de su denominación: los números de Smith.

Vamos con la definición de este tipo de números:

Un número de Smith es un número natural compuesto que cumple que la suma de sus dígitos es igual a la suma de los dígitos de todos sus factores primos (si tenemos algún factor primo repetido lo sumamos tantas veces como aparezca).

Con esta definición es sencillo ver que el primer número de Smith es el $4$ :

$\begin{matrix} 4=2 \cdot 2 \\ 4=2+2 \end{matrix}$

Y el siguiente es el $22$ :

$\begin{matrix} 22=2 \cdot 11 \\ 2+2=2+1+1 \end{matrix}$

Pero hay muchos más, de hecho hay infinitos números de Smith. Otro ejemplo, esta vez con un número más grande, $9985$ :

$\begin{matrix} 9985=5 \cdot 1997 \\ 9+9+8+5=5+1+9+9+7 \end{matrix}$

Los números de Smith fueron presentados por el matemático Albert Wilanski en 1982. Pero, ¿por qué no llevan su nombre? Muy sencillo. Al parecer el número de teléfono de teléfono del cuñado de Wilanski era 493-7775 y Albert se dio cuenta de que el número $4937775$ es un número de este tipo:

$\begin{matrix} 4937775=3 \cdot 5 \cdot 5 \cdot 65837 \\ 4+9+3+7+7+7+5=3+5+5+6+5+8+3+7 \end{matrix}$

El nombre de este tipo de números se debe a que el cuñado de Wilanski (que no tenía nada que ver con las matemáticas) se llamaba Harold Smith. Se vuelve a cumplir la sentencia de Klein.

En el momento en el que aparecieron los números de Smith éste era el mayor número de este tipo conocido. Pero a partir de aquí comenzaron a aparecer artículos dando propiedades y ejemplos mayores que el citado $4937775$ . Por ejemplo, en 1983 Oltikar y Wayland descubrieron que si $p$ es un número primo repuit (es decir, con todos sus dígitos iguales a uno), entonces el número $3304p$ es un número de Smith. Pero no es el único caso. Descubrieron muchos más números tales que multiplicados por un repunit primo dan siempre un número de Smith. Por ejemplo los números $1540, 1720, 2170, 2440, 5590$ y $6040$ también tienen esa propiedad. En la sucesión-pedia tenéis la lista de los mismos.

En 1984 Pat Costello encontró 75 nuevos números de Smith de la forma $p \cdot q \cdot 10^k$ , siendo $p$ un primo pequeño y $q$ un primo de Mersenne. El mayor de ellos (con 65319 dígitos) fue el siguiente:

$191 \cdot (2^{216091} - 1) \cdot 10^{266}$

En 1986 se presentó otro método distinto para generar números de Smith con el que se encontró, por ejemplo, el siguiente número de Smith:

$5 \cdot 1110110110111 \cdot (2 \cdot 5)^5=555055055055500000$

Pero no fue el único Se encontraron números realmente colosales, por ejemplo un número de Smith con 2592699 dígitos.

Pero fue en 1987 cuando se produjo el descubrimiento más importante sobre este tipo de número. Wayne Mc Daniel descubrió que hay infinitos números de Smith. De hecho descubrió más cosas. Introdujo los k-números de Smith, que son los que cumplen que la suma de los dígitos de los factores primos es el producto de $k$ por la suma de los dígitos del número y demostró que los k-números de Smith son infinitos, para todo $k$ .

En este mismo año también se definieron los números de Smith palindrómicos (es decir, capicúas), como el $12345554321$ , o los hermanos de Smith, que son parejas de números de Smith consecutivos, como el $728$ y el $729$ o el $67728$ y el $67729$ . A partir de esto se han descubierto tripletes de Smith (por ejemplo, $225951, 225952$ y $225953$ ), conjuntos de cuatro consecutivos (el más pequeño de este tipo es el formado por los números $4463535, 4463536, 4463537$ y $4463538$ ), y así sucesivamente.

Para terminar os dejo la lista de números de Smith de la sucesión-pedia y el mayor número de Smith conocido hasta la fecha:

$9 \cdot R_{1031} (10^{4594}+3 \cdot 10^{2297}+1)^{1476} \cdot 10^{3913210}$

donde $R_{1031}$ es el primo repunit compuesto por 1031 unos.

Fuentes:

La maravilla de los números, de Clifford A. Pickover.
Fascinating Smith Numbers: Sección de la web de Shyam Sunder Gupta con mucha información sobre los números de Smith.

Autor: ^DiAmOnD^ | Publicado el 19 de October de 2009 | Comments Off
Categorías: Curiosidades, Números enteros

Una demostración visual sobre números naturales y secuencias contadoras

Este artículo es una colaboración enviada por fede a gaussianos (arroba) gmail (punto) com.

Este post sobre una curiosa propiedad de determinadas particiones en dos conjuntos de algunos conjuntos finitos de números me recordó una curiosa propiedad de cualquier partición en dos conjuntos infinitos del conjunto de todos los números naturales que leí en algún libro de Honsberger.

Sea $P = \{2, 3, 5, 7, 11, \cdots \}$ una secuencia cualquiera no decreciente,esto es, $P(n), \ n \ge 0$ , de enteros no negativos.

La función $\pi(h)$ que da el número de términos de la secuencia $P(n)$ que son menores o iguales que $h, \ h \ge 0$ , define una nueva secuencia no decreciente de enteros no negativos que para la secuencia anterior $P$ resulta ser $\pi = \{0,0,1,2,2,3,3,4, \cdots \}$

A esta segunda secuencia, cuyos términos cuentan los términos de la primera menores o iguales que $h$ , la llamamos secuencia contadora de la primera secuencia.

Como la secuencia contadora es una secuencia no decreciente de no negativos, podemos obtener a su vez la secuencia contadora de esta secuencia contadora y así sucesivamente.

Pero sucede que:

Dada cualquier secuencia no decreciente de enteros no negativos, la secuencia contadora de la secuencia contadora es la secuencia inicial.

La curiosa conexión con las particiones de números está en:

Si tomamos dos secuencias de forma que una sea la secuencia contadora de la otra, y sumamos vectorialmente a cada una de ellas la secuencia de todos los naturales $N= \{1,2,3,4,5, \cdots \}$ , resulta una partición $\{A, B\}$ de los números naturales.

En el caso de las secuencias anteriores $P$ y $\pi$ resulta la partición:

$A= \{3, 5, 8, 11, \cdots \}$

$B= \{1, 2, 4, 6, 7, 9, 10, 12, \cdots \}$

Recíprocamente, si partimos en dos subconjuntos infinitos el conjunto de todos los naturales y restamos la secuencia $N= \{1,2,3,4,5, \cdots \}$ de los naturales de las dos secuencias resultantes de la partición, obtenemos dos secuencias no decrecientes de enteros no negativos que son cada una contadora de la otra.

Los resultados anteriores tienen una demostración visual sin palabras, debida a Dijkstra.

Si busca, el lector encontrará representadas en la figura adjunta las 4 secuencias que hemos usado como ejemplo:

$P = \{2, 3, 5, 7, 11, \cdots \}$

$\pi = \{0,0,1,2,2,3,3,4, \cdots \}$

$A= \{3, 5, 8, 11, \cdots \}$

$B= \{1, 2, 4, 6, 7, 9, 10, 12, \cdots \}$

y la secuencia
$N= \{1,2,3,4,5, \cdots \}$ , de los números naturales.

Y, tras unos momentos de reflexión, verá que la posibilidad de construir una figura análoga para cualquier partición en dos de los naturales da una demostración de los hechos anteriormente expuestos.

Autor: ^DiAmOnD^ | Publicado el 8 de October de 2009 | Comments Off
Categorías: Curiosidades, Números enteros

El algoritmo de Euclides

Introducción

El lunes pasado, en el post donde se desarrollaba un método para resolver ecuaciones diofánticas lineales, comentábamos la existencia de un método para el cálculo del máximo común divisor que no desarrollamos. Dicho método se atribuye a Euclides y este post va a servir para presentarlo.

El algoritmo de Euclides

El problema inicial es el siguiente:

Encontrar el máximo común divisor entre dos números enteros positivos $a$ y $b$ .

Todos conocemos el método que se nos enseña en el colegio para ello:

Descomponemos en factores primos los dos números y tomamos los factores comunes a ambos con el menor exponente con el que aparezcan.

Aunque es un método bastante útil y sencillo para conseguirlo que queremos tiene un evidente problema: si los números son muy grandes, o si sus factores primos lo son, la cosa se complica ya que el cálculo de la descomposición se torna bastante tedioso.

Por ello es interesante tener a mano otro método para casos en los que el procedimiento inicial se complique. El llamado algoritmo de Euclides nos servirá.

El algoritmo de Euclides nos dice lo siguiente:

Para calcular el máximo común divisor entre dos números enteros positivos $a$ y $b$ dividimos el más grande, digamos $a$ , entre el más pequeño, digamos $b$ . Esta división nos proporcionará un cociente, $c_1$ , y un resto, $r_1$ . Si $r_1=0$ , entonces $mcd(a,b)=b$ . Si no es cero dividimos el divisor, $c_1$ , entre el resto, $r_1$ , obteniendo otro cociente, $c_2$ , y otro resto, $r_2$ . Si $r_2=0$ , entonces $mcd(a,b)=r_1$ . Si no es cero volvemos a dividir divisor entre resto. Y así sucesivamente.

Esto es, el máximo común divisor entre $a$ y $b$ es el último resto distinto de cero que obtengamos con el procedimiento anterior.

Si analizamos el algoritmo de Euclides se ve claramente que necesitamos demostrar que el máximo común divisor entre $a$ y $b$ es igual al máximo común divisor entre $b$ y $r_1$ . Así esa igualdad se mantendrá durante todo el proceso y llegaremos a que el último resto distinto de cero es el máximo común divisor de los dos enteros positivos iniciales. Vamos a demostrar este hecho para después ilustrar el algoritmo con un ejemplo:

Teorema:

El máximo común divisor de dos números enteros positivos $a$ y $b$ , con $a > b > 0$ , coincide con el máximo común divisor de $b$ y $r$ , siendo $r$ el resto que se obtiene al dividir $a$ entre $b$ .

Demostración:

Sean $d=mcd(a,b)$ y $t=mcd(b,r)$ . Vamos a demostrar que $d=t$ .

Por definición de máximo común divisor, se tiene que $d$ es un divisor tanto de $a$ como de $b$ . Por tanto $a=a_1d$ y $b=b_1d$ .

Por otro lado, por el algoritmo de la división se tiene que

$a=bq+r$ , con $0 \le r < b$ (1)

de donde llegamos a

$r=a-bq=a_1d-b_1dq=(a_1-b_1q)d$

Por tanto $d$ es un divisor de $r$ . Como ya teníamos que también es un divisor de $b$ entonces debe dividir a su máximo común divisor, esto es, $d$ es un divisor de $t$ .

Por otro lado, $t$ es un divisor tanto de $b$ como de $r$ . Por ello se tiene que $b=pt$ y $r=st$ . Sustituyendo estas dos igualdades en (1) obtenemos lo siguiente:

$a=ptq+st=(pq+s)t$

Por tanto $t$ es un divisor de $a$ . Como también lo era de $b$ debe ser un divisor de su máximo común divisor, es decir, $t$ es un divisor de $d$ .

Como $d$ es un divisor de $t$ y $t$ es un divisor de $d$ no queda otra opción más que $t=d$ . Por tanto el algoritmo de Euclides funciona. $\Box$

Ejemplos de aplicación del algoritmo

En esta sección del artículo vamos a ver un par de ejemplos de aplicación del algoritmo de Euclides. Vamos con ellos:

Cálculo de $mcd(721,448)$

Como hemos explicado antes dividimos el número mayor entre el menor; si el resto no es cero dividimos el divisor entre el resto; y así sucesivamente hasta que llegamos a un punto en el que el resto es cero. Los resultado de las divisiones (expresados como dividendo=divisor · cociente + resto) son:

$721=448 \cdot 1+273$
$448=273 \cdot 1+175$
$273=175 \cdot 1+98$
$175=98 \cdot 1+77$
$98=77 \cdot 1+21$
$77=21 \cdot 3+14$
$21=14 \cdot 1+7$ *
$14=7 \cdot 2+0$

Como marca el *, se tiene que $mcd(721,448)=7$ , el último divisor que no es nulo.

Cálculo de $mcd(25134,19185)$

Vamos con el segundo ejemplo, con números más grandes en este caso. Expresamos los resultados parciales de la misma forma que en el ejemplo anterior:

$25134=19185 \cdot 1+5949$
$19185=5949 \cdot 3+1338$
$5949=1338 \cdot 4+597$
$1338=597 \cdot 2+144$
$597=144 \cdot 4+21$
$144=21 \cdot 6+18$
$21=18 \cdot 1+3$ *
$18=3 \cdot 6+0$

Vemos que aunque los números son bastante mayores que los anteriores el número de operaciones necesarias para el cálculo es el mismo. Concluyendo, tenemos que, como marca el *, $mcd(25134,19185)=3$ .

Autor: ^DiAmOnD^ | Publicado el 5 de October de 2009 | Comments Off
Categorías: Aprenda como, Matemáticas discreta, Números enteros

La ecuación de Pell

Introducción

El pasado lunes presentábamos un método de resolución de ecuaciones diofánticas lineales. También vimos que no sólo existen este tipo de ecuaciones diofánticas: dependen de los exponentes de sus variables. Por desgracia cuando los exponentes no son 1 (es decir, cuando no son lineales) no tenemos un procedimiento general para resolverlas. Esto lo sabemos desde 1970, cuando Yuri Matiyasévich consiguió demostrar (después de 20 años de trabajo) que no es posible encontrar un algoritmo que nos diga si una ecuación diofántica tiene soluciones o no las tiene. Este fue uno de los 23 problemas, concretamente el décimo, que David Hilbert propuso en el año 1900.

Después de este mazazo vamos a alegrar un poco el asunto: aunque no tengamos un procedimiento para todas las ecuaciones diofánticas sí que sabemos resolver algunos casos particulares de ellas. El artículo de hoy trata sobre uno de estos casos: la ecuación de Pell.
(Leer el resto del post)

Autor: ^DiAmOnD^ | Publicado el 1 de October de 2009 | Comments Off
Categorías: Historia, Números enteros

Cómo resolver ecuaciones diofánticas

Este artículo ha sido promovido en Menéame. Si te ha gustado y quieres votarlo entra aquí y menéalo.

Motivación

Supongamos que nos encontramos el siguiente problema:

Un hombre va a una tienda de ropa y compra 12 trajes, unos negros y otros grises, por 1200 €. Si los trajes negros valen 30 € más que los grises y ha comprado el mínimo posible de estos últimos, ¿cuántos trajes ha comprado de cada color?

Vamos a plantearlo:

$\{trajes \; negros \}=x$
$\{trajes \;grises \}=12-x$ $\{precio \; de \; un \; traje \; gris \}=y$
$\{precio \; de \; un \; traje \; negro \}=y+30$

La ecuación queda:

$x(y+30)+(12-x)y=1200$

Haciendo cuentas nos queda lo siguiente:

$30x+12y=1200$

Si estabais pensando que nos iba a quedar un sistema de ecuaciones sencillo de resolver estáis equivocados. Nos ha quedado una única ecuación con dos incógnitas. ¿Nos faltan datos? No. Podemos resolverla. Bienvenidos al maravilloso mundo de las ecuaciones diofánticas.
(Leer el resto del post)

Autor: ^DiAmOnD^ | Publicado el 28 de September de 2009 | Comments Off
Categorías: Aprenda como, Matemáticas discreta, Números enteros

Los números de Carmichael

La aventura de buscar qué números enteros positivos son primos es tan antigua como las propias matemáticas. Desde siempre los números primos han fascinado a los matemáticos. Los números primos, los átomos a partir de los cuales se pueden obtener todos los números naturales. Para no fascinar al personal.

Esto conlleva que desde siempre se hayan intentado desarrollar métodos para la búsqueda de los números primos. Quizás el más antiguo de los que se conocen sea la Criba de Eratóstenes, que consiste en lo siguiente:

Escribimos todos los números naturales desde el 2 hasta un cierto $n$ , por ejemplo hasta 120 (como aparece en la figura, tomada de la Wikipedia en español). Nos quedamos con el 2, que es primo, y tachamos todos los múltiplos de 2. Nos quedamos con el siguiente número no tachado, que en este caso es el 3, y lo declaramos como primo, tachando después todos los múltiplos de 3. Seguimos de esta forma, quedándonos con el primer número no tachado como primo y tachando sus múltiplos. Conseguimos así descartar todos los compuestos y localizar todos los primos.

Interesante método, pero con un gran inconveniente: el proceso es larguísimo si $n$ es muy grande. Por ello no serviría para localizar primos grandes, ya que costaría demasiado aplicar el método hasta el final. Imaginaos que quisiéramos determinar si un número de ocho cifras es primo…las dimensiones del cuadro y el tiempo que tardaríamos en terminar no son ni mucho menos asumibles.
(Leer el resto del post)

Autor: ^DiAmOnD^ | Publicado el 31 de August de 2009 | Comments Off
Categorías: Números enteros, Números primos

¿Por qué el caso n=4 es tan importante?

Introducción

Mucho se ha hablado en Gaussianos de Fermat y su último teorema. Pero que yo recuerde todavía no se ha mostrado ninguna demostración relacionada con él. En este artículo vamos a ver la de un caso, concretamente $n=4$ , que a la postre resulta determinante para la demostración global del teorema.

Primer paso: demostrar el teorema para n=4

Sello del Teorema de Fermat-Wiles
Por si alguien no sabe todavía de qué va este último teorema vamos a enunciarlo otra vez:

No existen enteros positivos $x,y,z$ y $n$ tales que $x^n+y^n=z^n$ para n > 2.

En esta parte del artículo vamos a demostrar que este resultado es cierto para $n=4$ , es decir:

Teorema: No existen enteros positivos $x,y$ y $z$ tales que $x^4+y^4=z^4$ .

Demostración:

Vamos a utilizar el método de reducción al absurdo. Supongamos que existen $x,y$ y $z$ tales que $x^4+y^4=z^4$ . Podemos suponer que cada par de ellos son primos relativos (ya que si dos de ellos tuvieran un divisor común el otro también debería tenerlo y por tanto podríamos simplificarlo). Esto implica que $x^2,y^2$ y $z^2$ son una terna pitagórica (es decir, terna de números cuyas longitudes son los lados de un triángulo rectángulo), por lo que, intercambiando los papeles de $x$ e $y$ si fuera necesario, tenemos lo siguiente (echad un ojo al artículo sobre ternas pitagóricas enlazado en esta misma frase si no sabéis por qué):

$x^2=2pq$
$y^2=p^2-q^2$
$z^2=p^2+q^2$

donde $p$ y $q$ tienen distinta paridad y cumplen que $0 < q < p$ .

Pero la segunda ecuación se puede escribir como $y^2 + q^2 = p^2$ y, como $p$ y $q$ son primos relativos, se sigue que $y, p$ y $q$ forman una terna pitagórica primitiva. Por lo tanto $p$ es impar y, como $p$ y $q$ tienen distinta paridad, $q$ es par.

De aquí:

$q = 2ab$
$y = a^2 – b^2$
$p = a^2 + b^2$

donde $a$ y $b$ son primos relativos de paridad opuesta y $a > b > 0$ . Así:

$x^2 = 2pq = 4ab(a^2 + b^2)$

Esto demuestra que $ab(a^2 + b^2)$ es un cuadrado (exactamente el cuadrado de $\textstyle{\frac{x}{2}}$ ). Pero $ab$ y $a^2 + b^2$ son primos relativos, ya que si un primo $P$ divide a $ab$ debería dividir también a $a$ o a $b$ , pero no a ambos, ya que $a$ y $b$ son primos relativos. Por tanto no puede dividir a $a^2 + b^2$ .

En consecuencia $ab$ y $a^2 + b^2$ deben ser ambos cuadrados. Pero si $ab$ es un cuadrado deben ser $a$ y $b$ los dos cuadrados (al ser primos relativos). Digamos entonces que $a = X^2$ y $b = Y^2$ . Por tanto $X^4 + Y^4 = a^2 + b^2$ es un cuadrado. Pero esto es suficiente para aplicar el método del descenso infinito, ya que la única suposición que se hizo al principio es que $z^4$ era un cuadrado, no una cuarta potencia. En otras palabras, si $x$ e $y$ son enteros positivos tal que $x^4 + y^4$ es un cuadrado la demostración anterior nos permite encontrar otros dos enteros positivos, $X$ e $Y$ , tales que $X^4 + Y^4$ es un cuadrado. Además:

$X^4 + Y^4 = a^2 + b^2 = p < p^2 + q^2 = z^2 < z^4 = x^4 + y^4$

Por tanto tenemos una sucesión decreciente infinita de enteros positivos, lo cual es imposible. Es decir, este razonamiento prueba que el último teorema de Fermat se cumple para $n = 4$ .

¿Qué tiene de especial el caso $n=4$ ?

Partiendo de lo que acabamos de demostrar se tiene que $x^{4m} + y^{4m} = z^{4m}$ no se puede dar para $x, y$ y $z$ enteros positivos cuando $m$ es un entero positivo, ya que $X = x^m$ , $Y = y^m$ y $Z = z^m$ serían solución de $X^4 + Y^4 = Z^4$ , pudiendo aplicarles entonces la demostración anterior. Por tanto el último teorema de Fermat es cierto para todo $n$ múltiplo de 4.

Ahora, un entero positivo $n > 2$ que no es múltiplo de 4 no es una potencia de 2. Entonces debe ser divisible por algún primo $p \ne 2$ , digamos $n = pm$ . Por tanto es obvio que para demostrar que $x^n + y^n = z^n$ es imposible será suficiente demostrar que $x^p + y^p = z^p$ es imposible. Esto es:

Una vez que el último teorema de Fermat ha sido probado en el caso $n = 4$ la demostración del caso general se reduce a probarlo en el caso en el que $n > 2$ es primo.

Esta es la importancia del caso $n=4$ : demostrando el teorema sólo en este caso permite tenerlo demostrado para todos los no primos.

Ahora sólo faltaría demostrarlo para los exponentes números primos.

Imagen tomada de Kelso Images.

Autor: ^DiAmOnD^ | Publicado el 20 de August de 2009 | Comments Off
Categorías: Demostraciones, Números enteros, Números primos, Teoremas

La sucesión de Goodstein

En este artículo os traigo otra de esas paradojas para la intuición que en realidad están perfectamente demostradas matemáticamente (tipo la de Banach-Tarski). Me refiero, como podéis ver en el título, a la sucesión de Goodstein.

Introducción

Tomamos un número natural cualquiera, por ejemplo el $252$ (que ya apareció por aquí hace un tiempo). Vamos a expresarlo en base 2:

$252=2^7+2^6+2^5+2^4+2^3+2^2$

Expresemos ahora cada uno de los exponentes también en base 2:

$252=2^{2^2+2+1}+2^{2^2+2}+2^{2^2+1}+2^{2^2}+2^{2+1}+2^2$

Esto que hemos hecho se denomina expresar un número natural en su forma normal de Cantor en base $b$ .

Ahora aplicamos lo que podríamos llamar un salto de base, que en una situación así es básicamente sustituir todas las ocurrencias de $b$ por $b+1$ , y después restamos 1 al resultado. Por tanto, en este caso sustituimos todas las apariciones del número 2 por el 3 y restamos 1:

$3^{3^3+3+1}+3^{3^3+3}+3^{3^3+1}+3^{3^3}+3^{3+1}+3^3-1$

Utilizando que $3^3-1=2 \cdot 3^2+2 \cdot 3+2$ (ver ¹ al final del artículo) obtenemos:

$3^{3^3+3+1}+3^{3^3+3}+3^{3^3+1}+3^{3^3}+3^{3+1}+2 \cdot 3^2+2 \cdot 3+2$

El resultado es un número de 15 cifras, concretamente el $854066918318651$ . La cosa ha crecido bastante.

Volvemos a realizar la misma operación: ahora sustituimos todas las apariciones del número 3 por el 4 (los números menores que 3 quedan igual) y restamos 1:

$4^{4^4+4+1}+4^{4^4+4}+4^{4^4+1}+4^{4^4}+4^{4+1}+2 \cdot 4^2+2 \cdot 4+2-1$

Obtenemos el número

$4^{4^4+4+1}+4^{4^4+4}+4^{4^4+1}+4^{4^4}+4^{4+1}+2 \cdot 4^2+2 \cdot 4+1$

que tiene 156 cifras. La cosa sigue subiendo.

Otra paso más: ahora saltamos a base 5 y restamos 1:

$5^{5^5+5+1}+5^{5^5+5}+5^{5^5+1}+5^{5^5}+5^{5+1}+2 \cdot 5^2+2 \cdot 5+1-1$

Llegamos al número

$5^{5^5+5+1}+5^{5^5+5}+5^{5^5+1}+5^{5^5}+5^{5+1}+2 \cdot 5^2+2 \cdot 5$

que tiene la friolera de 2189 cifras. Vamos a realizar la misma operación una vez más (sustituimos cada 5 por un 6 y restamos 1):

$6^{6^6+6+1}+6^{6^6+6}+6^{6^6+1}+6^{6^6}+6^{6+1}+2 \cdot 6^2+2 \cdot 6-1$

Como $2 \cdot 6-1=6+5$ obtenemos el número:

$6^{6^6+6+1}+6^{6^6+6}+6^{6^6+1}+6^{6^6}+6^{6+1}+2 \cdot 6^2+6+5$

que alcanza la nada despreciable cantidad de 36311 cifras.

Si continuamos realizando la misma operación los números resultantes son cada vez más grandes. ¿Dónde terminará la cosa? Pues…

El teorema de Goodstein

…veamos dónde termina:

Teorema: (de Goodstein)

Toda sucesión de Goodstein creada con el procedimiento anterior termina en cero.

¿Cómo? ¿Que toda sucesión de Goodstein, comience en el número que comience, termina en el número cero? Pues sí, todas terminan en cero. De hecho la demostración no es excesivamente complicada. En la Wikipedia inglesa podéis verla.

Para imaginar por qué ocurre esto podéis coger un número pequeño, por ejemplo el 3, y crear su correspondiente sucesión de Goodstein. Quedaría algo así:

$2+1$
Sustituimos cada 2 por un 3 y restamos 1: $3+1-1=3$
Sustituimos cada 3 por un 4 y restamos 1: $4-1=3$
Sustituimos cada 4 por un 5 y restamos 1: $3-1=2$
Sustituimos cada 5 por un 6 y restamos 1: $2-1=1$
Sustituimos cada 6 por un 7 y restamos 1: $1-1=0$

Si escogemos para comenzar el número 4 la cosa se alarga bastante más. La secuencia comenzaría con los resultados $4,26,41,60$ y llegaría hasta un número de ¡121210695 cifras! desde donde comenzaría a decrecer hasta terminar irremediablemente en el cero.

Como curiosidad comentar que se sabe que el teorema de Goodstein no puede probarse con la aritmética de Peano, hecho que probaron Kirby y Paris en 1982. Ellos interpretaron el teorema de Goodstein como una hidra, creando el juego llamado hydra game, que parte de una hidra (un árbol, hablando en término de grafos) y consiste en ir cortándole cabezas. Las reglas del juego nos dicen que con ciertos cortes la hidra hará que le crezcan cierto número de cabezas y con otros la hidra se mantendrá tal cual quede después del corte. En esta web podéis ver tanto la explicación del juego como el enlace a un applet de java donde podéis jugar al hydra game. La analogía con el teorema de Goodstein es bien sencilla: por muy largo que sea el proceso (que lo será por muy pequeño que sea el número inicial de cabezas) siempre se llega a cortar todas las cabezas de la hidra.

Fuentes:

Página personal de Josep M. Albaigès.
Goodstein´s theorem en la Wikipedia (en inglés).

¹: En ese paso se usa la siguiente propiedad:

$b^n-1=(b-1)(b^{n-1}+b^{n-2}+ \ldots +b+1)$

Es sencillo comprobar que este hecho es cierto simplemente operando la parte derecha de la igualdad.

Autor: ^DiAmOnD^ | Publicado el 18 de May de 2009 | Comments Off
Categorías: Curiosidades, Números enteros, Teoremas

El teorema de Wilson

Introducción

El teorema de Wilson es un resultado de teoría de números relacionado con la primalidad de un número entero positivo. Fue atribuido a John Wilson por su profesor Edward Waring. Éste último comentó que Wilson había dejado anotado este resultado en un cuaderno pero que no lo había demostrado (os suena esta historia, ¿verdad?). El propio Waring tampoco pudo hacerlo y tuvo que ser Lagrange en 1771 quien dio la primera prueba.

En esta entrada vamos a dar una sencilla demostración que utiliza propiedades más o menos elementales de teoría de números.

El teorema de Wilson

Teorema: Sea $p$ un número entero mayor que 1. Entonces $p$ es primo si y sólo si

$(p-1)! \equiv -1 \; (mod \; p)$

Demostración:

De forma sencilla puede comprobarse que este resultado es cierto para $p=2$ y para $p=3$ . Supongamos entonces que $p > 3$ .

Para demostrar la implicación de derecha a izquierda (si $(p-1)! \equiv -1 \; (mod \; p)$ entonces $p$ es primo) vamos a demostrar su contrarrecíproco, es decir, vamos a demostrar que si $p$ es compuesto entonces no se cumple esa igualdad:

$\Longleftarrow)$ Supongamos que $p$ es compuesto. Entonces sus divisores positivos se encuentran entre los enteros $1,2, \ldots ,p-1$ . Por tanto es claro que $mcd ((p-1)!,p$ >1$. En particular $p$ tiene algún divisor $d > 1$ .

Supongamos ahora que el resultado es cierto, es decir, que $(p-1)! \equiv -1 \; (mod \; p)$ . Como $d$ divide a $p$ entonces $d$ también divide a $(p-1)!$ y, por la congruencia, $d$ divide a $(p-1)!+1$ . Por tanto $d$ divide a 1, hecho que nos lleva a una contradicción con la condición $d >1$ . En consecuencia la implicación de derecha a izquierda es cierta.

$\Longrightarrow)$ Supongamos ahora que $p$ es primo. Por tanto todos los enteros $1,2, \ldots , p-1$ son primos relativos con $p$ . Por otra parte ese conjunto de números forma un grupo con la multiplicación, en concreto el grupo $\mathbb{Z}_p$ de los enteros módulo $p$ (en realidad, al ser $p$ primo ese conjunto es un cuerpo, pero ahora sólo nos interesa su condición de grupo con esa operación). Entre otras cosas eso significa que para todo $a \in \mathbb{Z}_P$ existe un único $b \in \mathbb{Z}_p$ tal que $a \cdot b \equiv 1 \; (mod \; p)$ . También por ser $p$ primo se tiene que $a=b$ si y sólo si $a=1$ ó $a=p-1$ , es decir, $1$ y $p-1$ son inversos el uno del otro. Por tanto para cualquier otro elemento del grupo distinto de éstos se tiene que su inverso también es distinto de éstos. En consecuencia podemos agrupar el resto de elementos por parejas (cada uno junto a su inverso) para que se cumpla lo siguiente:

$2 \cdot 3 \cdot \ldots \cdot p-2 \equiv 1 \; (mod \; p)$

Esto es, $(p-2)! \equiv 1 \; (mod \; p)$ . Multiplicando ahora a ambos lados por $(p-1)$ y utilizando que $p-1 \equiv -1 \; (mod \; p)$ obtenemos el resultado buscado.

Utilidad del teorema

El teorema tiene principalmente valor teórico ya que en la práctica es relativamente complicado calcular $(p-1)!$ para valores grandes de $p$ . Por eso generalmente antes que este teorema suelen usarse otros tests de primalidad, como el pequeño teorema de Fermat.

De todas formas es útil para generar a partir de él fórmulas de primos, es decir, fórmulas que generar números primos (en Gaussianos ya vimos algo así con los números primos pseudogemelos). Aunque, como en el caso anterior, suelen ser fórmulas poco prácticas por lo costoso que es calcular $(p-1)!$ para $p$ muy grande.

De todas formas, como dije antes, la belleza del resultado reside en su valor teórico. Y algunas, en ocasiones, tenemos suficiente con ello.

Fuentes:

Prime Pages
Wilson theorem en la Wikipedia (en inglés)

Autor: ^DiAmOnD^ | Publicado el 20 de October de 2008 | Comments Off
Categorías: Demostraciones, Números enteros, Números primos, Teoremas

Todo número de Mersenne con exponente compuesto es también compuesto

Sive, en este comentario, ha dado una demostración informática de que un número de Mersenne con exponente compuesto es también compuesto. En este post voy a dar yo una más matemática.

Definición

Un número de Mersenne es un número $M$ de la forma $M=2^n-1$ , con $n\in\mathbb{N}$ .

Teorema

Todo número de Mersenne $M=2^n-1$ con $n$ compuesto es también compuesto.

Demostración

Si $n$ es compuesto se puede descomponer como producto de al menos dos factores mayores que $1$ . Supongamos entonces $n=p \; q$ , con $p,q > 1$ .

Sabemos que $a^m-b^m=(a-b) \; (a^{m-1}+a^{m-2} \; b+ \ldots +a \; b^{m-2}+b^{m-1})$ . Además $2^n=2^{p \;q}=(2^p)^q$ . Tomando $a=2^p$ y $m=q$ en la igualdad anterior se tiene el resultado:

$(2^p)^q-1=(2^p)^q-1^q=(2^p-1) \; ((2^p)^{q-1}+(2^p)^{q-2}+ \ldots +2^p+1)$

Es decir, $2^{pq}-1$ tiene al menos dos factores mayores que $1$ y, por tanto, es compuesto.

¿Qué pasa si $n$ es primo? Pues que sus únicos divisores son $1$ y el propio $n$ . Por tanto, utilizando la igualdad anterior obtendríamos:

$2^n-1=2^n-1^n=(2-1) \; (2^{n-1}+2^{n-2}+ \ldots +2+1)=2^{n-1}+2^{n-2}+ \ldots +2+1$

número éste que podría ser primo o no. Por eso $2^n-1$ sólo puede ser primo si $n$ lo es.

Autor: ^DiAmOnD^ | Publicado el 29 de August de 2008 | Comments Off
Categorías: Demostraciones, Números enteros, Números primos

Los números de Smith

Una demostración visual sobre números naturales y secuencias contadoras

El algoritmo de Euclides

Introducción

El algoritmo de Euclides

Ejemplos de aplicación del algoritmo

La ecuación de Pell

Introducción

Cómo resolver ecuaciones diofánticas

Motivación

Los números de Carmichael

¿Por qué el caso n=4 es tan importante?

Introducción

Primer paso: demostrar el teorema para n=4

¿Qué tiene de especial el caso $n=4$ ?

La sucesión de Goodstein

Introducción

El teorema de Goodstein

El teorema de Wilson

Introducción

El teorema de Wilson

Utilidad del teorema

Todo número de Mersenne con exponente compuesto es también compuesto

Yo construí el poliedro de Császár

Suscripción

Buscar

Premios 20Blogs

Matemáticos célebres

Imprimir artículos

Carnaval de Matemáticas

Post aleatorio

Categorías

Enlaces

Introducción

El algoritmo de Euclides

Ejemplos de aplicación del algoritmo

Introducción

Motivación

Introducción

Primer paso: demostrar el teorema para n=4

¿Qué tiene de especial el caso ?

Introducción

El teorema de Goodstein

Introducción

El teorema de Wilson

Utilidad del teorema

Yo construí el poliedro de Császár

Suscripción

Buscar

Premios 20Blogs

Matemáticos célebres

Imprimir artículos

Carnaval de Matemáticas

Post aleatorio

Categorías

Enlaces

¿Qué tiene de especial el caso $n=4$ ?