Lo fascinante de la teoría de números

Números cíclicos

Posted in ¡Qué curioso!, MegaPost, Números primos, Teoría Analítica de números by ZetaSelberg on 18 octubre, 2013

Puedes ver esta entrada en la nueva dirección Números cíclicos



 

Hace varias semanas vimos como el número 142857, cumple una curiosa propiedad

Al multiplicarlo por algún número entre uno y seis, se permutan sus números.

Y no es el único número que hace esto, otro ejemplo es el número

052631578947368421.

¿Crees que no? Ajá, pues mira.

052631578947368421\cdot 2=105263157894736842

052631578947368421\cdot 3=157894736842105263

052631578947368421\cdot 4=210526315789473684

052631578947368421\cdot 5=263157894736842105

052631578947368421\cdot 6=315789473684210526

\cdot

\cdot

\cdot

Y ejemplos los hay por montones.

Estos números son llamados números cíclicos. Los números cíclicos son números tales que, al multiplicarlos por algún valor (a decir verdad, no cualquier valor) el número resultante se compone de los mismos números iniciales. De manera más precisa

Definición: Un número m, que se compone de k-1 dígitos, se dice número cíclico si al multiplicarlo por algún número r, tal que 1\leq r\leq k-1, el número resultante es una permutación del número original. Es decir, el resultado se compone de los mismos dígitos iniciales, solo se cambia el orden.

En el caso de el número 052631578947368421: la cantidad de dígitos que tiene es 18, tomen cualquier valor entre uno y dieciocho… Al multiplicarlo por el número 052631578947368421, de seguro te dará un número que se compone de esos mismo dígitos.

Super chevere estos números, pero ahora lo que nos interesa es saber como obtener números cíclicos. A decir verdad, no se saben si existen infinitos número cíclicos, es un problema abierto. Aún así, hemos logrado ciertos resultados interesantes. Por ejemplo, conocemos un criterio por el  cual un número primo puede generar un número cíclico. De esta forma

Teorema: Sea p un número primo mayor a cinco. Si la longitud del periodo de 1/p es de p-1, entonces el periodo de dicha fracción es un número cíclico. En este caso decimos que p genera un número cíclico.

Es esta la razón por la cual sé que 052631578947368421 es un número cíclico sin haber verificado todos los productos, pues

\displaystyle\frac{1}{19}=0.\overline{052631578947368421},

dado que la longitud del periodo es 18(=19-1), entonces será cíclico. Note que no todo número primo cumple las condiciones dadas en el teorema. Por ejemplo, para p=11 obtenemos

\displaystyle\frac{1}{11}=0.\overline{09}.

Al tener periodo de longitud dos, no cumple las condiciones requeridas por el teorema.

Veamos esta situación, supongamos que el número primo p me genera un número cíclico. Entonces, escribamos

\displaystyle\frac{1}{p}=0.\overline{a_1 a_2\cdots a_{p-2}a_{p-1}}.

Multiplicando por 10^{p-1}

\displaystyle\frac{10^{p-1}}{p}=a_1 a_2\cdots a_{p-2}a_{p-1}.\overline{a_1 a_2\cdots a_{p-2}a_{p-1}},

\displaystyle\frac{10^{p-1}}{p}-\frac{1}{p}=a_1 a_2\cdots a_{p-2}a_{p-1}.

Es decir: si p genera un número cíclico, podemos obtener el número cíclico en cuestión, por medio de la fórmula

\displaystyle\frac{10^{p-1}-1}{p}.

Observe que si multiplicamos por p obtenemos un número que se compone de solo nueves. Esto se relaciona con algo que hemos tratado ya: el teorema de Midy.

Hasta este punto, decimos que sabemos un criterio por el cual podemos buscar números cíclicos: ir probando primo por primo buscando a ver para qué valores el periodo de 1/p es de longitud p-1.

Pero hay algo más allá, hay un criterio que nos caracteriza totalmente los números primos que generan cíclicos. Aquí va

Teorema: Sea p>5 un número primo. p genera un número cíclico si y solo si diez es una raíz primitiva módulo p. Es decir, si y solo sí, para todo valor 1\leq a<p, existe un número natural r tal que

10^r=a\bmod p.

Es una caracterización bastante interesante, aún así, está muy relacionada con una conjetura, la conjetura de Artin. Tal conjetura dice qué, dado un valor n que no es cuadrado perfecto, existen infinitos primos p para los cuales n es raíz primitiva módulo p.


Llaves


Ahora bien, haremos este calculo: dado un número primo p que genera un número cíclico, para cada valor 0\leq a<p-1, buscaremos un valor k_a<p tal que

10^{a}=k_a\bmod p.

Entonces, para cada uno de los p-1 valores, obtendremos un k, en total serían p-1 números. Estos números componen algo llamado “llave” ¿Por qué una llave? porque con esta llave puedo decir cual será el resultado de multiplicar el número cíclico por algún otro número.

¿Como usamos la llave? Digamos que hemos obtenido nuestros números k_a para cada valor de a, entonces formamos el número

<k_1 k_2 k_3\cdots k_{p-2} k_{p-1}>

Ahora, supongamos que el cíclico generado por 1/p es a_1 a_2 a_3 \cdots a_{p-2}a_{p-1}, y queremos saber cuanto da r(a_1 a_2 a_3 \cdots a_{p-2}a_{p-1}), entonces, alienamos ambos números

a_1 a_2 a_3 \cdots a_{p-2}a_{p-1}

<k_1 k_2 k_3\cdots k_{p-2} k_{p-1}>

En la llave, buscamos el número r, digamos que está en la posición i

a_1 a_2 a_3 \cdots a_{i-1}a_i\cdots a_{p-2}a_{p-1}

<k_1 k_2 k_3\cdots k_{i-1}k_i\cdots k_{p-2} k_{p-1}>

Tomemos los números a_1 a_2 a_3\cdots a_{i-1} y ubiquemos esa cadena de números al final esto es

a_i\cdots a_{p-2}a_{p-1}a_1 a_2 a_3 \cdots a_{i-1}

Entonces ese número que obtuvimos, es igual a r(a_1 a_2 a_3 \cdots a_{p-2}a_{p-1}). Hagamos un ejemplo, que esto anda muy abstracto :?.


Ejemplo con p=7


El número primo siete genera el número cíclico 142857. Calculemos cual es la llave,

10^0\equiv 1\bmod 7 entonces k_1=1,

10^1\equiv 3\bmod 7 entonces k_2=3,

10^2\equiv 2\bmod 7 entonces k_3=2,

10^3\equiv 6\bmod 7 entonces k_4=6,

10^4\equiv 4\bmod 7 entonces k_5=4,

10^5\equiv 5\bmod 7 entonces k_6=5.

De modo que la llave es

<132645>.

Calculemos cuanto da 4(142857), entonces

142857

<132645>.

Buscamos el número cuatro en la llave

142857

<1326\boxed{4}5>.

El número que está justo arriba del cuatro es corresponde al cinco,

1428\boxed{5}7

<1326\boxed{4}5>.

Los números que están antes del cinco son 1428

\boxed{1428}57

<1326\boxed{4}5>.

Tomamos estos números y los colocamos de último, obteniendo entonces

571428.

¡Listo! Esto es la multiplicación de 142857 por 4.


El blog Melosumido, tiene una una entrada en la cual se habla acerca de los números cíclicos. Allí se muestra una manera gráfica bastante práctica para hacer este proceso. La idea consiste en ubicar ambos ambos números, el cíclico y la llave, en dos círculos… de esta forma

cic1

El círculo exterior contiene el número cíclico original, empezando desde la línea verde en dirección a las manecillas del reloj. De igual forma, el círculo interior contiene la llave, escrito desde la línea verde en dirección a las manecillas del reloj. Si queremos hallar el producto de 142857 por 6, buscamos el seis en el círculo interior

cic2

A partir de allí, damos una vuelta en dirección a las manecillas del reloj, uniendo cada número que vamos recorriendo

cic31

De modo que

142857\times 6=857142.

Acá hay otro ejemplo, en el cual tomamos p=19. Con este número primo obtenemos el número cíclico que se encuentra al inicio de la entrada.

cic4


Una pregunta interesante es esta: al calcular la llave, los números que componen la llave deber ir desde el uno hasta p-1, de otra forma, si alguno de ellos no está, al querer multiplicar el número cíclico por dicho número no podríamos usar la llave, ni la “ruedita” que tenemos. Entonces necesitamos asegurar el hecho de que todos los números desde uno hasta p-1 están en la llave.

Lema: La llave se compone de p-1 números, y contiene todos los números desde uno hasta p-1.


Demostración. Es claro que la cantidad de números que contiene la llave es de p-1 (dado que se están haciendo p-1 cálculos), además, es claro que todos los números son menores a p (porque estamos tomando módulo p). Como p es un número primo mayor a cinco, este no divide a diez, de modo que al calcular el módulo ninguno dará cero. Es decir, los todos los números de la llave son mayores o iguales a uno y menores o iguales a p-1. Si demostramos que todos son distintos, habríamos acabado la demostración, puesto que la única opción es que sean todos los números desde uno a p-1. Supongamos que para dos valores distintos r y s (0\leq r,s\leq p-2), el módulo dio lo mismo, es decir

10^r\equiv a\mod p,

10^s\equiv a\mod p.

Entonces,

10^r-10^s\equiv 0\mod p.

Esto quiere decir que p|(10^r-10^s). Sin perdida de generalidad, supongamos que r es el número mayor, entonces

p|10^s(10^{r-s}-1).

Como p no divide a diez, entonces no divide a 10^s, por lo tanto

p|10^{r-s}-1.

Por otro lado, en la demostración del teorema de Midy, el teorema 3, nos dice que la longitud del periodo es el mínimo número l tal que

p|10^{l}-1.

Por hipótesis, la longitud del periodo de 1/p entonces p-1=l. De modo que debe darse que r-s\geq p-1, pero tanto r como s, ambos eran menores o iguales a p-2

p-2\geq r-s\geq p-1.

Esto es una contradicción.


Otra propiedad interesante acerca de esta llave es que nos permite cambiar de base fácilmente. A qué me refiero con esto: 142857 es el periodo de la fracción 1/p en base diez, si quiero conocer el periodo en base 17, tomo este periodo y le sumo la llave

142857+132645=274E9C_{17},

y en general

Lema: Supongamos que 1/n genera un número periódico en base b, donde \gcd(n,b)=1, es decir

\displaystyle\left(\frac{1}{p}\right)_{b}=0.\overline{P}.

Entonces, para cualquier número t

\displaystyle\left(\frac{1}{p}\right)_{b+mt}=0.\overline{P^\prime},

donde

P^\prime=P+tK,

y K es la llave, es decir, los números que se obtienen de

b^0\equiv k_1 \mod n

b^1\equiv k_1 \mod n

\cdot

\cdot

\cdot

b^{l-2}\equiv k_1 \mod n,

donde l es la longitud del periodo P.


Números cíclicos en otras bases numéricas


Como es de esperarse, se puede hablar de números cíclicos en otras bases. De hecho, el teorema 1 se puede generalizar, obteniendo el siguiente

Teorema: Sea p>5 un número primo. p genera un número cíclico en base b si y solo si b es una raíz primitiva módulo p. Es decir, si y solo sí, para todo valor 1\leq a<p, existe un número natural r tal que

b^r=a\bmod p.

Y las cosas siguen de manera similar a como sucede en base diez, existe una llave, que se calcula de la misma manera a como se mostró en el anterior lema.

Del teorema anterior podemos decir que, dado un número primo p existen infinitas bases b para las cuales 1/p es cíclico en dicha base. Sin embargo, desconocemos si dada una base b, existen infinitos números primo p que generen un número cíclico. Además, como habíamos dicho, esto va relacionado con la conjetura de Artin. Para nuestro consuelo está el caso particular en el cual b es un cuadrado perfecto. En tal caso podemos decir que no existen números primos p que generen números cíclicos, pues un cuadrado perfecto no puede ser raíz primitiva cuadrático.

Este teorema, el cual caracteriza los primos que generan números cíclicos, transporta nuestro problema de ¿hay infinitos números cícilicos? a ¿es cierta la conjetura de Artin? Se ha logrado cierto progreso en dicha conjetura, por ejemplo, se ha probado que asumiendo la hipótesis genelarizada de Riemann la conjetura es cierta. Tal resultado fue demostrado por Hooley en 1967. Años mas tarde R. Gupta y M. Ram Murty lograron un avance bastante significativo:

Teorema (R. Gupta y M. Ram Murty): Sean qrs números primos distintos, considere el conjunto

S:=\{qs^2,q^3r^2,q^2r,r^3s^2,q^2s^3,qr^3,q^3rs^2,rs^3,q^2r^3,q^3s,qr^2s^3,qrs\}.

Entonces, para algún a\in S, existe un \delta>0 de modo que existen al menos

\displaystyle\frac{\delta x}{\log^2 x},

números primos p, con p\leq x, donde a es residuo cuadrático módulo p.

La demostración usa algo que personalmente me encanta: los métodos de cribado. Pero de eso hablaremos otro día.


Referencias

  • On Cyclic numbers and an extension of Midy’s theoremJuan B. Gil y Michael D. Weiner, arXiv:math/0605347 [math.NT].
  • A remark on Artin’s conjecture, R. Gupta y M. Ram Murty, Invent Math vol. 78 (1), (1984) p. 127–130.
  • Todas las imágenes fueron creadas usando Geogebra.

Actualización

Cuando hice la “ruedita” en la cual ubiqué la llave y el número cíclico, algo que quedó sonando, alguna propiedad extra que deba cumplir esta gráfica. Aún así no logré nada, pero mi hermano me mostró la luz.

Observemos esto, cada sección circular de la circunferencia exterior, tiene una región que la contrapone, es decir, en esta imagen

cic1

La región que tiene el número uno en la parte exterior (el número cícilo) y uno en la parte interior (la llave) tiene una región que la contrapone, que es la región que contiene los números seis y ocho. Entonces, si sumamos los números de cada región y la región que la contrapone, obtenemos siempre 16

1+1+6+8=16

4+3+4+5=16

2+2+5+7=16

Pasa algo bastante similar en la segunda “ruedita”

cic4

Al sumar cada región con la que la contrapone obtenemos siempre 28.

0+1+18+9=28

5+10+9+4=28

2+5+14+7=28

6+12+7+3=28

3+6+13+6=28

1+3+16+8=28

5+11+4+8=28

7+15+2+1=28

8+17+2+1=28

De hecho, si giramos el círculo interior también se conserva la suma. En la siguiente construcción en Geogebra, se puede hacer girar el círculo interior. Si hacemos el ejercicio de girarlo e ir verificando que da cada suma, nos damos cuenta que efectivamente da 16.


Acá debería aparecer el applet de Geogebra… pero no sé por qué no aparece. Mientras arreglo este problema, pero WordPress.com tiene bloqueada esta opción. Dejaré este mensaje como muestra de mi frustración :mad:.

Enlace a GeogebraTube con la construcción

cons


Pero esto no es un resultado del otro mundo. Vamos a explicar el por qué sucede esto.

Lo primero a observar es qué, por el teorema de Midy, si sólo consideramos los números exteriores, la suma siempre dará nueve. Pues es justamente eso lo que nos asegura el teorema de Midy: tales números son el periodo de la fracción 1/p donde la longitud es p-1 un número par.

Si nos fijamos en el círculo interior, el que contiene la llave, nos damos cuenta que al sumar cada región con la región que la contrapone, obtenemos siempre 7. ¡Ahí está la clave! Los números exteriores siempre suma 9, los números interiores siempre suman 7, de modo que no importa cuanto lo gires, siempre la suma será igual a 9+7=16.

Como dije antes, lo de los números exteriores está asegurado por el teorema de Midy, vamos a probar que para la llave, esa suma siempre da p.

Lema: La suma de cada región con la región que la contrapone, en la llave, da como resultado p


Demostración. Si el número que está en la región es k_i, la i-ésima posición donde 0\leq i\leq p-2, entonces, por definición

10^i\equiv k_i \bmod p

El número que se encuentra en la región que la contrapone es

k_{\frac{p-1}{2}+i}

Y este número es el único que cumple la congruencia

10^{\frac{p-1}{2}+i}\equiv k_{\frac{p-1}{2}+i} \bmod p

Si probamos que

10^{\frac{p-1}{2}+i}\equiv -k_{\frac{p-1}{2}+i} \bmod p

Debería pasar que

k_{\frac{p-1}{2}+i}=p-k_{\frac{p-1}{2}+i}

Lo cual implica que

k_{\frac{p-1}{2}+i}+k_{i}=p.

Primero vamos a probar que 10^{\frac{p-1}{2}}\equiv -1\bmod p. Por el pequeño teorema de Fermat,

10^{p-1}\equiv 1\bmod p

De modo que p|(10^{p-1}-1), equivalente a decir p|(10^{\frac{p-1}{2}}-1)(10^{\frac{p-1}{2}}+1). Por el teorema 3 que vimos en la demostración del teorema de Midy, sabemos que p-1 es el mínimo l que hace que

p|10^l-1

De modo que p no divide a (10^{\frac{p-1}{2}}-1), entonces debe dividir a (10^{\frac{p-1}{2}}+1), esto quiere decir que

10^{\frac{p-1}{2}}\equiv -1 \bmod p

Ahora sí… Dado que

10^i\equiv k_i \bmod p

Multiplicando por 10^{\frac{p-1}{2}} a ambos lados obtenemos

10^{\frac{p-1}{2}+i}\equiv 10^{\frac{p-1}{2}}k_{i} \bmod p

Pero habíamos probado que

10^{\frac{p-1}{2}}\equiv -1 \bmod p

Entonces

10^{\frac{p-1}{2}+i}\equiv -k_{i} \bmod p


Este teorema puede escribirse de esta forma, la cual se parece al teorema de Midy

Lema: Sea p un número primo mayor a cinco, suponga que el periodo de 1/p es de longitud p-1. Entonces, la llave asociada a p tiene longitud p-1 y si dividimos la llave en dos bloques, al sumarlos se obtiene un número cuyos dígitos son todos p.

Anuncios

Una respuesta

Subscribe to comments with RSS.


Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: