noticias y última hora

El problema de las 100 puertas y los divisores de un número natural

En matemáticas hay conceptos sencillos de comprender y de manejar y conceptos con los que es muy complicado trabajar; por otra parte, hay temas de los que se puede sacar mucha chicha, y también los hay del tipo contrario, de los que se puede tirar poco.

Pero sencillo no es ni mucho menos sinónimo de simple. Un concepto sencillo, como puede ser el de divisor de un número natural, puede dar lugar a problemas maravillosos, cuyo resultado sorprende por su belleza y cuya explicación termina por elevarlos a la categoría de maravilla matemática.
(Leer el resto del post)

¿Quién no tiene una demostración de la conjetura de Goldbach?

En mi última charla ¿Se puede “hacer” matemáticas a través de un blog? en la Universidad de Sevilla (podéis ver mis impresiones sobre ella en este enlace), me hicieron dos preguntas. Una de ellas la realizó Raven_Neo (gracias otra vez por la grabación; cuando subas el vídeo no te olvides de avisarme) y trataba sobre las formas que usamos para promocionar el blog en sus inicios (a lo que, por cierto, respondí en principio que la mejor promoción es salir en Microsiervos). La otra la formuló Tito Eliatron, y en ella me preguntaba sobre comentarios que me han sorprendido de entre todos los que me han dejado en Gaussianos.

Aparte de destacar lo mucho que os involucráis en los comentarios, sobre todo en los problemas que planteo semanalmente (ya hablé del perro y los soldados de josejuan, pero hay más, como el programa que creó Lek en el post sobre la constante de Kaprekar, por destacar uno de los primeros), comenté que me sorprendía mucho que haya gente que continúa comentando cosas como que la cuadratura del círculo con regla y compás es posible y que tiene una prueba de ese hecho (que, como ya vimos, es una construcción imposible con regla y compás), y también que sigue habiendo gente que comenta y me envía al mail demostraciones de resultados tipos la conjetura de Goldbach o la conjetura de Collatz.
(Leer el resto del post)

El final de la historia sobre la naturaleza de M67

Como ya sabemos, un número de Mersenne es un número de la forma

M_p=2^p-1

con p un número natural. También sabemos que si p es un número compuesto, entonces M_p también lo es, por lo que M_p sólo puede ser primo si el propio p lo es.

La cuestión es que esto no ocurre siempre, es decir, no siempre que p es primo se tiene que M_p lo es. Cuando esto ocurre se dice que M_p es un primo de Mersenne.

En Gaussianos ya hemos hablado sobre los primos de Mersenne en muchas ocasiones. De hecho hemos anunciado descubrimientos de nuevos primos de Mersenne varias veces. Lo que hoy vamos a contar es una anécdota de uno de los números de Mersenne, el número M_{67}=2^{67}-1.
(Leer el resto del post)

En GIMPS están muy callados…

GIMPS…qué raro. GIMPS, la mayor comunidad de búsqueda de primos de Mersenne lleva ya bastante tiempo sin dar señales de vida en lo que a encontrar nuevos números de este tipo se refiere. La última noticia que tenemos de ellos es la confirmación (¡¡siete años después de su descubrimiento!!) de que 2^{20996011}-1 es efectivamente el primo de Mersenne número 40 si los colocamos en orden creciente.

Posiblemente el hecho de que cada vez se busque entre números más grandes hace que el tiempo necesario para encontrar un primo de Mersenne se alargue, pero teniendo en cuenta que entre el 45 y el 46 pasó escasamente un mes (aquí hablábamos de la confirmación del descubrimiento de los dos) y del 46 al 47 unos 6 meses, se hace raro que llevemos más de año y medio si saber nada sobre ellos.

Teniendo en cuenta que su forma de trabajar se basa en la colaboración desinteresada de la gente mediante la utilización del programa de ordenador que ellos ponen a disposición de todo el mundo, ¿será que la gente colabora menos? No lo sé, aunque no lo creo.

Esperemos que pronto nos den una sorpresa en forma de un nuevo número primo de Mersenne.

Por cierto, hace ya bastante tiempo me descargué su programa y lo estuve probando, aunque debo reconocer que no le dediqué demasiado tiempo al tema. ¿Alguno de vosotros colabora o ha colaborado alguna vez con ellos? ¿Alguien ha encontrado alguno de los primos de Mersenne que aparecen en su lista? ¿Alguna anécdota que contar al respecto?

Los números primos (y algo más) van a hacer que ganemos el mundial

Existe una especie de teoría que dice que en los equipos de cualquier deporte, en particular de fútbol, los dorsales que corresponden a números primos son los que se asignan a los jugadores más importantes. Hasta donde yo sé, este artículo de Marcus du Sautoy es el máximo exponente de esta creencia (aunque en el artículo también se habla del género de cada tipo de número). Uno de los casos más llamativos de los últimos años es el Real Madrid que montó Florentino Pérez en su primera etapa en la presidencia del club de Concha Espina. En él los pesos pesados portaban números primos en su dorsal. A saber:

  • 3: Roberto Carlos
  • 5: Zidane
  • 7: Raúl
  • 11: Ronaldo
  • 23: Beckham
  • 1: Casillas (éste lo añado yo, ya que aunque el 1 no es un número primo sí que puede considerarse como la base los números naturales)

En cierto modo tiene sentido. Los números primos son los ladrillos a partir de los cuales se construyen todos los números naturales, por lo que sería razonable asignar dorsales primos a los jugadores en torno a los que se construye el equipo. Y la verdad es que, en general, no les salió mal.
(Leer el resto del post)

¿Que tiene que ver el número e con los números primos?

Desde los comienzos del blog ciertas constantes han tenido un gran protagonismo en muchos artículos. Cierto es que el número \pi se lleva la palma, pero pero también ha habido otras constantes a las que se les han dedicado artículos por su importancia y sus características, como \sqrt{2}, la constante de Euler-Mascheroni \gamma o el número e.

Número e

Número e

Sobre este último tenemos varios artículos en los que aparece como protagonista principal o como actor secundario con un papel importante. Por ejemplo, hemos visto que es irracional y que es trascendente, dos características muy interesantes de un número que aparece tanto en nuestra vida diaria (más de lo que muchos piensan). También hablamos de cómo aparece al no formar ninguna pareja en el matching problem y, por otra parte, sabemos que es uno de los componentes de la identidad de Euler.
Los primeros 25 números primos

Los primeros 25 números primos


Y qué decir de los números primos, ellos sí que han aparecido en multitud de ocasiones por Gaussianos, ya sea demostrando su infinitud de varias formas (la demostración topológica me parece genial), generándolos o anunciando la aparición de nuevos miembros en esta familia tan peculiar.

Lo que no habíamos visto todavía (al menos que yo recuerde) es una relación más o menos clara y directa entre el número e y los números primos. Vamos, una expresión que involucre a esta constante con este tipo tan especial de números, a este número irracional con estos números tan naturales. Pues ha llegado el momento.
(Leer el resto del post)

La función Phi de Euler: otra genialidad del maestro

Introducción

Pierre de Fermat
Tras la muerte de Pierre de Fermat, muchas de sus conjeturas quedaron sin resolver. Como ya sabemos, Fermat no era muy dado a publicar las demostraciones de sus resultados, por lo que debían ser demostrados por otros para confirmar su validez o falsedad. El caso más famoso, por lo que se tardó en confirmar y por la gran cantidad de matemáticos que se dedicaron a ello, es el denominado último teorema de Fermat, demostrado finalmente por Andrew Wiles en 1995, pero ni mucho menos fue el único.

La afirmación de Fermat sobre la primalidad de todos los números enteros positivos F_n=2^{2^n}+1, llamados números de Fermat, fue otra de sus más famosas conjeturas, refutada finalmente por Euler en 1732 al encontrar la factorización de F_5:

F_5=2^{2^5}+1=4294967297=641 \cdot 6700417

De hecho no se ha vuelto a encontrar ningún número de Fermat que sea primo.

Y el llamado pequeño teorema de Fermat constituye otro caso del mismo tipo que los anteriores. Dicho teorema afirma lo siguiente:

Si p es un número primo y a es un número natural que no es divisible por p, entonces a^{p-1} \equiv 1 \pmod{p}

Euler demostró este resultado y dio además la demostración de una generalización del mismo. En esta historia la conocida como función \varphi de Euler ejerce un papel de suma importancia.
(Leer el resto del post)

Cómo generar conjuntos CuCu

Introducción

A los matemáticos nos encanta poner nombre a las cosas, y cuanto más descriptivo sea el nombre mucho mejor. Así, los puntos frontera de un conjunto son los que gráficamente situaríamos como frontera geográfica de dicho conjunto o una sucesión monótona es una sucesión en la que nunca pasa nada distinto, es decir, una sucesión en la que la tendencia no cambia, es siempre creciente o siempre decreciente, pero no hay cambios.

Los conjuntos que os voy a presentar hoy no tienen nombre (al menos yo no conozco ningún nombre para ellos). Por eso los he bautizado a partir de la propiedad que tienen. Son los conjuntos CuCu.

¿Qué es un conjunto CuCu?

Lo primero que voy a hacer es explicar qué es para mí un conjunto CuCu.

Un conjunto CuCu es un conjunto de números enteros positivos tales que la suma de sus Cubos es igual al Cuadrado de su suma. Es decir:

Un conjunto CuCu es un conjunto de números enteros positivos \{ a_1, \ldots a_k \} que cumplen que:

a_1^3+ \ldots + a_k^3=(a_1+ \ldots + a_k)^2

Un ejemplo muy interesante de conjunto CuCu es el conjunto \{1, 2, \ldots , n \}, para cualquier n \in \mathbb{N}. Que este conjunto de números sea un conjunto CuCu significa lo siguiente:

1^3+2^3+ \ldots + n^3=(1+2+ \ldots +n)^2

Vamos a demostrar este resultado por inducción:

Demostración:

El resultado es evidente para n=1:

1^3=1^2

Supongamos ahora que es cierto para n, es decir, que

(1+2+ \ldots +n)^2=1^3+2^3+ \ldots + n^3

y demostremos que la igualdad es cierta para n+1. Para ello partiremos de la parte de la igualdad relativa al cuadrado y utilizaremos el caso n (esto es, la hipótesis de inducción) para llegar al objetivo buscado.

Partimos entonces de esta expresión:

(1+2+ \ldots +n+(n+1))^2=

Tomamos como primer término 1+2+\ldots +n y como segundo término n+1 y desarrollamos el cuadrado de la suma:

=(1+2+ \ldots +n)^2+(n+1)^2+2(1+2+ \ldots+n)(n+1)=

Ahora utilizamos la hipótesis de inducción en la primera suma y que 1+2+\ldots+n=\cfrac{n(n+1)}{2} en la segunda:

=1^3+2^3+ \ldots +n^3+(n+1)^2+2 \cdot \cfrac{n(n+1)}{2} \cdot (n+1)=

Operando ahora el último sumando obtenemos n(n+1)^2 y agrupándolo con el segundo sumando obtenemos (n+1)^3, llegando entonces a la igualdad buscada. \Box

¿Cómo generar conjuntos CuCu?

Pero el conjunto de los primeros enteros positivos no es el único que cumple esta propiedad. De hecho existe un procedimiento para generar conjuntos de números que cumplen que la suma de sus cubos es igual al cuadrado de su suma, es decir, conjuntos CuCu.

Joseph Liouville

Joseph Liouville

Dicho procedimiento se lo debemos a Joseph Liouville y consiste en lo siguiente:

  1. Tomamos un número entero positivo cualquiera y calculamos los divisores de dicho número (el 1 y el propio número también cuentan).
  2. De cada divisor calculado antes contamos cuántos divisores tiene.
  3. Los números que designan las cantidades de divisores de cada divisor del número inicial son un conjunto CuCu.

Vamos a ver un ejemplo sobre la aplicación de este procedimiento:

Número 20

  1. Los divisores de 20 son 1,2,4,5,10 y 20.
  2. Ahora:
    - El 1 tiene 1 divisor (el 1 solamente).
    - El 2 tiene 2 divisores (el 1 y el 2).
    - El 4 tiene 3 divisores (el 1, el 2 y el 4).
    - El 5 tiene 2 divisores (el 1 y el 5).
    - El 10 tiene 4 divisores (el 1, el 2, el 5 y el 10).
    - El 20 tiene 6 divisores (el 1, el 2, el 4, el 5, el 10 y el 20).
  3. Entonces el conjunto \{1,2,3,2,4,6 \} es un conjunto CuCu:

    1^3+2^3+3^3+2^3+4^3+6^3=(1+2+3+2+4+6)^2

    Efectivamente, ambos miembros de la igualdad dan como resultado 324.

Evidentemente este procedimiento tiene su demostración, pero en vez de reproducirla aquí prefiero que visitéis este enlace en el que el gran Ignacio Larrosa nos la cuenta.

Factorización de un primo de la forma 4k+1 en el anillo de los enteros gaussianos

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


Introducción

Un número primo de la forma 4k+1 es suma de los cuadrados de dos números enteros. Además la representación p=x^2 + y^2 es única si 0 < x < y.

Como x^2 + y^2 = (x+iy)(x-iy), la representación anterior da una factorización de un primo natural p = 4k+1 en el anillo de los enteros gaussianos. Además los factores (x+iy) y (x-iy) son primos en ese anillo.

Este post describe cómo obtener los enteros x,y que son solución de p=x^2 + y^2.

Describiendo el algoritmo

Podemos probar con un programa valores sucesivos de x hasta que encontremos la solución de x^2+y^2=p, y eso puede funcionar para primos pequeños como 100123456789 y 100987654321, pero no sirve para primos algo más grandes como el primo gemelo titánico más pequeño o el primo más pequeño de 2000 dígitos decimales.

La demostración de Zagier de que un primo de la forma 4k+1 es suma de dos cuadrados tampoco da un método práctico para encontrar la solución, ni las de Euler, Lagrange o Dedekind.

Tampoco la fórmula explícita de Gauss

x \equiv \dfrac{(2k)!}{2(k!)^2} \pmod{p}, \quad y \equiv (2k)!x \pmod{p}

es útil para calcular los valores de x e y.

Sin embargo existe un algoritmo muy simple para obtener la solución. Podemos describirlo de la siguiente forma:

Obtenemos un r < p tal que r = \pm \sqrt{-1} \pmod{p}, es decir, r^2 \equiv -1 \pmod{p}.

A continuación aplicamos el algoritmo de Euclides a \dfrac{p}{r}. El primer resto que encontramos menor que \sqrt{\dfrac{p}{2}} es el valor de x y el resto anterior es el valor de y.

El algoritmo se deriva de las demostraciones de Serret, Hermite y H.J. Smith, las primeras publicadas en el “Diario de Liouville” en 1848 y la última en el “Diario de Crelle” en 1855.

Calculadora de las componentes de los factores

Podéis probar el algoritmo introduciendo un primo en la casilla de abajo. Para encontrar primos de algunos centenares de dígitos, podéis copiar y pegar en la casilla de abajo primos cuyas 2 últimas cifras sean de la forma 4k+1 desde las páginas de “Prime Curios!”.

                                                   

  Paso  Resultado  Duración
1. Validación de entrada   
2. Busca no-residuo   
3. Calcula raíz de -1   
4. Alg.Euclides sobre p/r   
5. Comprobación  
 x =
 y =

Descripción de la calculadora

  • El paso 1 sólo verifica que el número introducido sea de la forma 4k+1.

    Los dos siguientes pasos sirven para obtener r = \sqrt{-1} \pmod{p}, y están basados en los resultados de la teoría elemental de residuos cuadráticos.

  • En el paso 2 se busca un no-residuo cuadrático t (es decir, un número que no sea un cuadrado \pmod{p}). Como la mitad de los números menores que p son no-residuos, y es rápido determinar si un número es o no un residuo cuadrático (calculando el símbolo de Jacobi), probando con números al azar podemos obtener rápidamente un no-residuo cuadrático.

    Sin embargo no está demostrado (todavía) que exista algoritmo determinista en tiempo polinomial para obtener un no-residuo cuadrático.

    La implementación devuelve el menor no-residuo, si éste es menor que 2000.

  • Una vez que tenemos un no-residuo t, en el paso 3 se obtiene r = t^{(p-1)/4} \pmod{p}.

    Por el criterio de Euler para residuos cuadráticos, r= \pm \sqrt{-1} \pmod{p}.

  • Que el paso 4 nos da la solución se justifica por el teorema de Serret:

    Si r^2 \equiv -1 \pmod{p}, \ r < p, la lista de cocientes parciales del desarrollo en fracción continua de \dfrac{p}{r} es simétrica (omando la lista de longitud par, lo que siempre es posible porque {}[a_0, \ldots, a_n] = [a_0, \ldots, a_n-1, 1]).

    A partir de los resultados mencionados en el post sobre fracciones continuas finitas, y con la notación usada alli, resulta que p = N[a_0,\ldots,a_h,a_h,\ldots ,a_0] = N[a_0,\ldots,a_h]^2 + N[a_0,\ldots,a_{h-1}]^2 .

    Por ser simétrica la fracción continua, los restos que se obtienen al aplicar el algoritmo de Euclides a \dfrac{p}{r} son los numeradores de los convergentes parciales (en orden inverso) y por tanto no hace falta calcular los numeradores de dichos convergentes parciales. Basta con aplicar el algoritmo de Euclides a \dfrac{p}{r} hasta que obtengamos un resto menor que \sqrt{\dfrac{p}{2}} .

  • Por último, en el paso 5 se comprueba si los valores obtenidos cumplen x^2 + y^2=p. Si no se cumple la igualdad, se concluye que el número p introducido no es primo (y los valores de t,r no serán, en general, correctos).

El teorema de Serret se demuestra fácilmente usando la relación entre numeradores y denominadores de los convergentes parciales consecutivos y las reglas de formación de esos numeradores y denominadores. De ese teorema se obtiene una demostración de que un primo de la forma 4k+1 es suma de dos cuadrados, que pertenece al grupo de demostraciones que parten de que, para un primo de esa forma, -1 es un cuadrado \pmod{p}

En cambio la demostración de H.J. Smith que exponemos a continuación no hace uso de este hecho.

La demostración de H.J. Smith

Usamos la notación {}[ a_0, a_1, \ldots, a_n ] para representar la fracción continua finita cuyos cocientes parciales son a_0,a_1, \ldots ,a_n. Designamos con N[ a_0, a_1, \ldots, a_n ] el numerador de la fracción {}[ a_0, a_1, \ldots, a_n ] .

Como {}[a_0, a_1, \ldots, a_{n-1}, 1 ] = [a_0, a_1, \ldots, a_{n-1} + 1 ], asumimos que el último cociente es siempre mayor que 1.

En el post sobre fracciones continuas vimos que se cumple

  • N[a_0, a_1, \ldots, a_n ] =  N[a_n, a_{n-1}, \ldots, a_0 ] ,
  • N[a_0,\ldots,a_k,\ldots,a_n] =  N[a_0,\ldots,a_k] N[a_{k+1},\ldots,a_n] +  N[a_0,\ldots,a_{k-1}]  N[a_{k+2},\ldots,a_n]

Estas identidades implican:

(1)   N[a_0,\ldots,a_h,a_h,\ldots ,a_0] = N[a_0,\ldots,a_h]^2 + N[a_0,\ldots,a_{h-1}]^2 .
(2)   N[a_0,\ldots,a_h,a_{h+1},a_h,\ldots ,a_0] = N[a_0,\ldots,a_{h}] (  N[a_0,\ldots,a_{h+1}] + N[a_0,\ldots,a_{h-1}] )  .

De esta última igualdad se concluye que si a_0 es mayor que 1 (y hay más de un cociente), N[a_0,\ldots,a_h,a_{h+1},a_h,\ldots ,a_0] no es primo.

Para un primo de la forma 4k + 1, sea S el conjunto de las fracciones \dfrac{p}{i}, \ \  2 \le i \le \dfrac{p-1}{2} , desarrolladas en fracción continua.

En el desarrollo en fracción continua de \dfrac{p}{i} = [a_0, a_1, \ldots, a_n ] se tiene que a_0 \ge 2 , porque i \le \dfrac{p-1}{2} , y a_n \ge 2 porque asumimos que el último cociente es mayor que 1.

La función f([a_0, \ldots, a_n ]) = [a_n, \ldots, a_0] asocia a cada elemento de S otro elemento de S, porque el numerador de una fracción continua no se altera si se invierte el orden de los cocientes y el denominador es un número menor que \dfrac {p}{2}, porque a_n \ge 2.

La función f es entonces una involución de S.

Si p=4k+1, el número de elementos de S es 2k-1, un número impar, y entonces f tiene por lo menos un punto fijo, es decir, existe un r, \  2 \le r \le \dfrac{p-1}{2} que da una fracción continua simétrica \dfrac{p}{r} = [a_0, \ldots, a_h, a_h, \ldots, a_0] (por la observación (2) anterior, el número de cocientes ha de ser par porque p es primo).

Entonces p es suma de 2 cuadrados por la observación (1) anterior.

Sea \dfrac{p}{r} = [a_0, \ldots, a_h, a_h, \ldots, a_0 ] = \dfrac{N[a_0, \ldots, a_h , a_h, \ldots, a_0]}{D[a_0, \ldots, a_h , a_h, \ldots, a_0]}.

Como

D[a_0,a_1,\ldots a_n] =   N[a_1,\ldots a_n], \ \ r=N[a_1,\ldots a_h, a_h, \ldots, a_0]

y como

 N[a_0 \ldots,a_n] N[a_1, \ldots,a_{n-1}] - N[a_0 \ldots,a_{n-1}] N[a_1, \ldots,a_n] = (-1)^{n-1}

tenemos que

 p N[a_1,\ldots,a_h,a_h,\ldots, a_1] - r^2 = 1

y por tanto

r^2 \equiv -1 \pmod{p}

.

Los curiosos enteros gaussianos

Introducción

Un joven Gauss

Un joven Gauss

El conjunto \mathbb{Z}=\{ \ldots -3,-2,-1,0,1,2,3 \ldots \} de los números enteros es un conjunto numérico bien conocido por todos nosotros. Y, aunque seguro que en menor medida, también lo es el conjunto \mathbb{C}=\{ a+bi; \; a, b \in \mathbb{R} \} de los números complejos, conjunto numérico muy interesante y muy útil en gran cantidad de problemas relacionados con muchas ramas de las matemáticas.

¿Qué ocurriría sin mezclamos las dos definiciones de estos conjuntos? Me explico:

¿Tendrá alguna utilidad considerar el conjunto de los números complejos cuyas partes real e imaginaria son números enteros?

No habría sido extraño que fuera algo así lo que pensó Gauss al introducir este conjunto en 1832 (aunque en realidad su motivación fue el estudio sobre sumas de cuadrados). Y la verdad es que acertó (como muchas otras veces). Encontró un conjunto realmente especial. Vamos a hablar un poco sobre él y sobre sus interesantes y curiosas propiedades.
(Leer el resto del post)

Anterior