Volvemos a visitar al mayor divisor impar

Participamos con esta entrada en el Carnaval de Matemáticas 3.131592653 cuyo anfitrión es el blog Que no te aburran las M@tes.

En una entrada ya algo antigua

 (http://hojaynumeros.blogspot.com.es/2009/03/la-hoja-de-calculo-ayuda-razonar.html)

resolvimos una cuestión muy elegante sobre el mayor divisor impar de un número (le llamaremos MDI).

Al revisar ahora esta cuestión nos hemos encontrado con que desde entonces se han desarrollado en este blog muchos estudios que nos podrían ayudar a estudiar con más profundidad esta función. Algunos de los temas que trataremos los hemos encontrado en http://oeis.org/A000265, pero sin desarrollar.

Definición y cálculo

Llamaremos mayor divisor impar (MDI) de un número natural N al mayor número impar (eventualmente igual a 1) que es divisor de N

Es evidente que si N es impar, MDI(N)=N y que si es potencia de 2, MDI(N)=1

Esto nos da una idea muy simple para calcularlo en un caso concreto: dividimos entre 2 todas las veces posibles y al final llegaremos al MDI:

144/2=72; 72/2=36; 36/2=18; 18/2=9, que será el MDI(144)

Visto de otra forma, hemos eliminado la mayor potencia de 2 posible. El exponente correspondiente, en este caso 4, recibe el nombre de valuación de N respecto a 2, V₂(N) (definición tomada de los números p-ádicos).

Podemos descomponer N como N=MDI(N)* V₂(N)

Esto nos lleva a códigos muy sintéticos para calcularlo:

En el Basic de las hojas:

Public Function mdi(n)  'mayor divisor impar
Dim s
s = n
While s/2=int(s/2): s = s / 2: Wend ‘ Divide entre 2 mientras se pueda.
mdi = s
End Function

No requiere explicación. Basta leerlo.

En PARI, como ya tiene implementada la función VALUATION, el código es aún más simple:

mdi(n)= {m=n / 2^valuation(n, 2);return(m)}

Existen otras formas elegantes de cálculo, pero más lentas:

Aquí hay un exceso: no es necesario llegar a 2^N. Es claro que el denominador es la valuación de N respecto a 2.Intenta razonarlo.

La sucesión de los mayores divisores impares la tienes en http://oeis.org/A000265:

1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 11, 3, 13, 7, 15, 1, 17, 9, 19, 5,21, 11, 23, 3, 25, 13, 27, 7, 29, 15, 31, 1, 33, 17, 35, 9, 37, 19, 39,…

Razona una propiedad muy sencilla y compruébala en la lista:

MDI(N)=MDI(2N)

Basándonos en esta propiedad podemos calcular MDI mediante recursividad, pues definiremos MDI(N) como el mismo N si es impar y MDI(N/2) si es par.

Es una solución muy elegante. Podemos usar la recursividad en las hojas de cálculo, ya explicada en http://hojaynumeros.blogspot.com.es/2012/03/funciones-recursivas-en-las-hojas-de.html:

Public Function mdirecu(n)
Dim d
If n = 2 * Int(n / 2) Then d = mdirecu(n / 2) Else d = n
mdirecu = d
End Function

Propiedades

(1) Es multiplicativa

En efecto, si m y n son coprimos, se cumple que MDI(m*n)=MDI(m)*MDI(n)

Casi podríamos dejarlo como ejercicio: Si m y n son coprimos tendrán diferentes factores primos. Es más, si m es par, n será impar. Hallarles el MDI equivale a eliminarle todas las potencias de 2 al que sea par, pero los demás factores no cambiarán y serán distintos en ambos números, luego al multiplicarlos se multiplicarán también sus MDI.

Como todas las multiplicativas (ver http://hojamat.es/publicaciones/multifun.pdf) para definir MDI basta hacerlo en el caso N=p^k, siendo p un factor primo de N. En este caso es trivial: si p=2, MDI(2^k)=1 y en caso contrario, MDI(p^k)= p^k

(2) El MDI representa la pauta de unos en su representación binaria

Ya nos referimos a esta propiedad en la anterior entrada: si N=MDI(N)* V₂(N), el paso de MDI(N) a N consistirá en añadir ceros a la derecha, luego la pauta de unos se conserva. Lo vemos con un ejemplo:

N=2664=101001101000(2  y MDI(2664)=333=101001101(2

Coinciden las pautas de unos

(3) Los conjuntos {MDI(N+1), MDI(N+2),…MDI(2N)} y {1,3, 5, 7…(n elementos)…} son idénticos.

También nos referimos a ella en su momento.

1.- Los elementos del primer conjunto son todos distintos, pues si dos fueran iguales, MDI(K)=MDI(J), uno de los números, por ejemplo K debería cumplir K=J*2^r y entonces, si J pertenece al rango N+1,…2N, K sería mayor que 2N y no pertenecería a ese rango.

2.- Todos los N primeros números impares deben pertenecer al segundo conjunto. Lo que es seguro es que pertenecen al intervalo 1..2N. Si pertenecen al intervalo N+1..2N ya está demostrado. Si no, M£N, y entonces existe un múltiplo suyo del tipo M*2^h que pertenece al rango N+1..2N. Supongamos que no, que existen dos exponentes consecutivos tales que M*2^h £ N < 2N < M*2^h+1 (h eventualmente igual a la unidad). Dividiendo resultaría M*2^h+1/ M*2^h > 2N/N, es decir 2>2, luego esta situación es imposible. Debe existir un exponente tal que M*2^r pertenezca a N+1..2N y por tanto su MDI estará en el segundo conjunto.

(3.1) Consecuencia: MDI(N+1)+MDI(N+2)+,…+MDI(2N) = N², por ser suma de los primeros impares.

(3.2) Otra consecuencia: Si llamamos U(n) a la suma de los MDI de los n primeros números naturales, se obtendrá que

U(2n) = n²+U(n)

(lo tienes en http://arxiv.org/pdf/1103.2295v1.pdf)

(4) La suma de los 2^N primeros términos de la sucesión de MDI equivale a (4^N+2)/3

Es consecuencia de la propiedad anterior. Lo vemos por inducción (recorre la sucesión presentada más arriba) 1+1=(4¹+2)/3=2;  1+1+3+1 = (4²+2)/3 = 6, 1+1+3+1+5+3+7+1 = (4³+2)/3=22,… luego podemos suponer cierta la igualdad para N. Sea

MDI(1)+MDI(2)+…+MDI(2^N) = (4^N+2)/3

Para 2^N+1, según la propiedad anterior, la suma sería: MDI(1)+MDI(2)+…+MDI(2^N+1) = (4^N+2)/3)+4^N = (4*4^N+2)/3 = (4^N+1+2)/3 y queda demostrado.

Y dejamos para el final la propiedad más elegante:

(5) Si sumamos los valores que toma la función j(N) (indicatriz de Euler) para todos los divisores impares de N, el resultado es el mayor divisor impar.

Es sabido que esa suma extendida a todos los divisores de N da como resultado N
(ver http://es.wikipedia.org/wiki/Funci%C3%B3n_%CF%86_de_Euler)

Por ejemplo, para el número 576, en la siguiente tabla tienes la comprobación de esta propiedad, los valores de la indicatriz también suman 576.

Como la función j es multiplicativa, la suma de la parte derecha se puede dividir en dos factores, uno para todos los divisores que son potencia de 2 y otro con los impares. Así, los 21 sumandos se pueden expresar así:
S = (j(1)+ j(3)+ j(9))*(j(1)+ j(2)+ j(4)+ j(8)+ j(16)+ j(32)+ j(64)) = 9*64 = 576

Vemos que la suma de la primera parte es 9, el MDI(576), como habíamos afirmado.

Esta descomposición se puede efectuar en cualquier número: por una parte incluimos las potencias de 2 y por la otra los coprimos con dos. La segunda suma dará la máxima potencia de 2 que divide a N y la primera tendrá como resultado MDI(N).

Extensión

Al igual que hemos definido el mayor divisor impar podíamos haberlo hecho con el mayor divisor no múltiplo de 5 (lo podemos representar como MD_5) que está estudiado en http://oeis.org/A132739, o no múltiplo de 10 (http://oeis.org/A132740) Puedes trasladar todo lo que se ha expuesto al caso en el que en lugar de 2 se use otro número.

También puedes pensar si siempre se cumplirá que MD_K(MD_L(N)) = MD_L(MD_K(N))

Mayor divisor propio con la misma suma de cifras

A partir de una cuestión simple (que no sencilla) desarrollaremos varias técnicas y conceptos, ejercicio que nos agrada mucho en este blog.

¿Qué números poseen la misma suma de cifras que su mayor divisor propio?

Uno de ellos es el 12673 que se descompone como 12673=19*23*29, luego su mayor divisor propio es 23*29=667 y, en efecto la suma de las cifras de 12673 es 19 y la de 667 también es 19.

No hay que irse tan lejos: el mayor divisor de 18 es 9 y también se cumple esta propiedad. Puede que hayas pensado que la cumplen todos los múltiplos de 9 y no es así, porque 45 tiene como mayor divisor 15 y ahí no coinciden las sumas, y tampoco en 63. Sin embargo sí se cumple en 18, 27, 36, 54,…

Esto se complica, porque tienen la propiedad números no múltiplos de 9 y entre los que sí lo son, unos la cumplen y otros no. Reflexionemos:

Relación entre un número y su mayor divisor propio

Si B es el mayor divisor propio de A se tendrá que A/B será el menor divisor de A (mayor que 1 pues si no B no sería propio), pero por uno de los más elegantes teoremas sobre divisores, ese cociente A/B ha de ser primo. Por tanto

Si B es el mayor divisor propio de A se cumple A=Bp siendo p primo (igual o menor que B)

Condición de igualdad de sumas

Si dos números presentan la misma suma de cifras es que son congruentes módulo 9, como bien se sabe en Aritmética Modular (recuerda el criterio de divisibilidad por 9).

Por tanto tendremos, con la notación anterior, que AºB (mod 9, es decir BºBp (mod 9 y por tanto Bp-B=B(p-1) deberá ser múltiplo de 9. Ten cuidado, que esta condición es necesaria pero no suficiente.

Esto nos lleva a tres posibilidades: (a) B es múltiplo de 9 (b) B es múltiplo de 3 pero no de 9 (c) B no es múltiplo de 3

(a) Si B es múltiplo de 9, el número primo p sólo puede ser 2 o 3. Si fuera mayor no se cumpliría, porque entonces B no sería el mayor divisor, ya que el menor sería 3 y por tanto el mayor sería A/3. Esto divide a los múltiplos de 9 en dos clases:

(a1) Los números en los que un múltiplo de 9 está multiplicado por 2 o 3 (y por otros), sí pueden cumplir la igualdad de sumas. De hecho son estos:

18, 27, 36, 54, 72, 81, 90, 108, 126, 135, 144, 162, 180, 198, 216, 234, 243,…

No sé si echas de menos alguno. No estará el 288, a pesar de cumplir el contener el factor 2, pero es que sus cifras suman 18 y las de su mayor divisor 144 sólo 9.

Aquí tienes la trampa: dijimos que la condición era necesaria pero no suficiente. Por eso hemos usado la palabra “pueden ser”. Lo que sí ocurrirá es que las sumas sean congruentes módulo 9 (razónalo)

(a2) Aquellos que tienen la forma 9p con p producto de primos mayores que 3. Estos no tienen que cumplir la igualdad de sumas. Por ejemplo 873=9*97. Sus cifras suman 18. Su mayor divisor es 873/3=291 y sus cifras suman 12.

(b) Para que B(p-1) sea múltiplo de  9 también puede ocurrir que B sea múltiplo de 3 pero no de 9, luego el otro factor 3 debe pertenecer a p-1, de donde se deduce que p tiene la forma de 3k+1 con k>0, luego p será un primo mayor que 3 y entonces B no será el mayor divisor de A sino A/3. No se puede dar este caso.

(c) Si B no es múltiplo de 9, lo será p-1. Así que si A no es múltiplo de 9, tampoco lo será B y  si se cumple la igualdad de suma de cifras, ha de ser divisible entre un número primo del tipo 9k+1 con k>0. Más exigente aún: como p-1 es par, p será del tipo 18k+1

Efectivamente, a continuación presentamos los números que cumplen la propiedad que estamos exigiendo y que no son múltiplos de 9. En todos ellos figura un factor primo del tipo 18k+1. En la factorización el primer número de cada corchete es el factor primo y el segundo su exponente.

361    [19,2]
551    [19,1][29,1]
703    [19,1][37,1]
1007  [19,1][53,1]
1273  [19,1][67,1]
1691  [19,1][89,1]
1843  [19,1][97,1]
2033  [19,1][107,1]
2071  [19,1][109,1]
2183  [37,1][59,1]
2413  [19,1][127,1]
2603  [19,1][137,1]
2641  [19,1][139,1]
2701  [37,1][73,1]
2831  [19,1][149,1]
2923  [37,1][79,1]
3071  [37,1][83,1]
3173  [19,1][167,1]
3293  [37,1][89,1]
3743  [19,1][197,1]
3781  [19,1][199,1]

No creas que todos son semiprimos. Hay otros que no lo son: 18791 está en la lista y se descompone como 19*23*43.

Recuerda también que la condición no es suficiente aquí tampoco.

Hemos publicado esta lista en OEIS con la referencia https://oeis.org/A219340

El código PARI que engendra esta secuencia lo tienes a continuación, aunque en este blog la primera búsqueda se efectúa con hoja de cálculo y después se comprueba con PARI, Wmaxima o Wiris cuando es posible.

digsum(n)={local (d,p); d=0; p=n; while(p,d+=p%10;p=floor(p/10)); return(d)}

largdiv(n)=if(n==1, 1, n/factor(n)[1, 1]) \\ Charles R Greathouse IV, Jun 15 2011

{ k=0; for (n=2, 10^5,  if(digsum(n)==digsum(largdiv(n))&&n%9>0, k=k+1;write("B219340.txt",k,", ",n))); } 

Sí, esta era una cuestión menor, pero nos ha divertido estudiarla. Se puede aprender mucho con este tipo de planteamientos.

Descomposición de un número según una lista

Hoy presentamos una herramienta de hoja de cálculo que nos permitirá descomponer un número en sumandos extraidos de una lista. Ya la anunciamos en anteriores entradas y tratamos el tema en
 (http://hojaynumeros.blogspot.com.es/2010/02/frobenius-y-los-mcnuggets.html)

El concepto es el siguiente: dado un conjunto de números enteros positivos a₁, a₂, a₃,…a_n, diremos que otro entero positivo N es representable según ese conjunto si existen coeficientes enteros no negativos x₁, x₂, x₃,…x_n tales que

 N= a₁*x₁+a₂*x₂+…a_n*x_n

Si exigimos que los coeficientes sólo puedan valer 0 o 1, obtendremos la descomposición en elementos distintos. Si los dejamos libres pasaremos al caso general del problema, también llamado “de las monedas”.

Herramienta

Hemos preparado una herramienta de hoja de cálculo. La tienes en

(http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#reprenum)

 y resuelve este problema para números no demasiado grandes. Tiene dos variantes, que explicaremos por separado.

(1) Descomposición de un sólo número

Para descomponer un número según una lista, es evidente que esos son los datos necesarios que habrá que aportar a la herramienta: el número, la lista y si deseamos o no repeticiones de sumandos. Es importante que se entienda esto bien, pues si por ejemplo deseamos expresar un número como suma de primos, será responsabilidad nuestra escribir la lista de números primos correctamente y tener una idea clara de hasta dónde debe llegar, dentro de las limitaciones de la hoja que estamos usando.

Por ejemplo, deseamos expresar el número 30 de todas las formas posibles como suma de cuadrados con repetición.

Para ello habrá que decidir el número a descomponer (30), la lista de cuadrados (1,4,9,16,25). En la imagen puedes ver el planteamiento

Además hay que indicar con un SI que deseamos repetición en los sumandos, es decir, que los coeficientes puedan ser números enteros positivos, no necesariamente 0 y 1. Hay que escribir en mayúsculas y sin tilde SI o NO.

Con el botón Iniciar se comienza la búsqueda de coeficientes. A cada sumando se le asigna un tope, que es el cociente entero por exceso entre 30 y él, para evitar cálculos inútiles. A la derecha de los topes verás de forma muy animada la búsqueda de coeficientes. El hecho de que aparezcan ralentiza el proceso, pero le da más vida y aquí nos interesa más la comprensión que la velocidad.

Los resultados se expresan como combinaciones lineales, que son más compactos que la lista de sumandos. En nuestro ejemplo han aparecido 27 formas distintas de expresar el número 30 como combinación lineal del tipo

30 = 1*x₁+4*x₂+9*x₃+16*x₄+25*x₅

Estas combinaciones las puedes interpretar como sumas con elementos repetidos:

2*1+7*4 = 1+1+4+4+4+4+4+4+4 = 30

27 sumas son muchas. Si el número fuera mayor la lista también tenía que crecer. Por eso no debe extrañar que los tiempos de cálculo se acerquen a 10 o 20 minutos en números pequeños, o más si se le exige mucho. Si te cansas del cálculo, pulsa ESC si usas Excel o Ctrl+Maúscula+Q si estás con OpenOffice o LibreOffice.

La variante sin repetición, al sólo admitir 0 y 1 como coeficientes es mucho más rápida y con menos resultados. Aquí tienes todas las descomposiciones del número 50 en sumas de números primos no repetidos. Al ser extensa la lista de primos, a un ordenador, si no es muy rápido, puede costarle más de diez o quince minutos encontrarlos.

Resultan 23 formas de expresar 50 como suma de primos no repetidos. Puedes comprobarlo en la lista contenida en http://oeis.org/A000586. Intenta reproducir algún resultado más de la misma, pero si el número es mayor, deja al ordenador trabajando solo y al cabo de media hora vuelves.

(2) Elaboración de una lista

Hemos señalado que la página http://oeis.org/A000586 contiene las descomposiciones de los números enteros en sumas de primos distintos. Sus primeros valores son 1, 0, 1, 1, 0, 2, 0, 2, 1, 1, 2, 1, 2, 2, 2, 2. Eliminamos el primer 1, que corresponde al cero y no tiene sentido en nuestra tarea. Intentaremos reproducirla.

Para obtener una lista pasamos a la parte derecha de la hoja sin borrar la lista de sumandos, pero sí eliminando los primos que no vayamos a usar. Por ejemplo, se podían preparar los 20 primeros números con la lista {2, 3, 5, 7, 11, 13, 17, 19}. En esa parte derecha concretamos el inicio, final y salto de la lista. Aquí serían 1, 20 y 1 respectivamente.

Al pulsar en el botón Lista observaremos que las búsquedas no presentan a la izquierda ni los coeficiente ni los resultados parciales, para aumentar la velocidad, y sólo aparecerán los números y sus resultados.

Reproduce la búsqueda en tu equipo y compara estos resultados con los de  http://oeis.org/A000586 para comprobar su exactitud. Puedes realizar más comprobaciones, pero lo dejamos para otro día

Sumas de impares (2)

Esta entrada participa en la edición 3.1415926 del Carnaval de Matemáticas, alojado en el blog Series divergentes

-----------------------

Conjuntos de sumas de impares

Esta propuesta invita a seguir pensando en sumas de números impares consecutivos a trozos, o mejor todavía, todas las sumas posibles de impares en las que no se repita ningún sumando. Todo número distinto de 2 se puede descomponer en suma de impares distintos, pues, si es impar, la suma la compondría él mismo, y si es par bastaría escribir N=(N-1)+1, suma de dos impares distintos, salvo que N=2.

Podemos representar estas sumas de varias formas. La entrada anterior nos sugiere una forma, y es considerar gnomones situados cada uno en su número de orden dejando huecos. Por ejemplo, la descomposición 15=1+5+9 se puede representar así:

Más compacta y conocida es la de no dejar hueco alguno y adosar las representaciones de los impares para conseguir un diagrama de Ferrers-Young simétrico.

Estos diagramas ayudan a entender las particiones de un número
 (ver http://mathworld.wolfram.com/FerrersDiagram.html)

El que nos ha resultado parece una escalera, pero no ha de ser siempre así. En la siguiente imagen puedes ver el correspondiente a 32=1+3+13+15

¿De cuántas formas se puede descomponer un número en suma de impares distintos?

Si acotamos el problema, por ejemplo a sumas de números inferiores o iguales a 2K-1 tendremos la posibilidad de considerar hasta 2^K – 1 sumas diferentes, que son las formadas por los distintos subconjuntos de {1, 3, 5, … 2K-1} que son en total 2^K  y a los que hay que quitar el conjunto vacío, por lo que quedan 2^K – 1 sumas diferentes. Sin embargo, los posibles resultados de esas sumas son como mucho K², porque la suma más pequeña es 1 y la mayor 1+3+5+ … +2K-1= K².

El análisis anterior nos indica que a partir de K=5 existen más sumas posibles que resultados, luego a algunos de estos se les puede asignar dos o más sumas distintas. Esto era de esperar. Por ejemplo, 8=1+7=3+5

Hemos organizado con hoja de cálculo la búsqueda de todas las S(N) formas posibles de descomponer un número N en sumas de impares distintos. Esencialmente ha consistido en

(1) Calcular K, el orden del mayor impar que puede pertenecer a esas sumas. que para cada número N, que es ENTERO((N+1)/2)

(2) Formar un conjunto de K dígitos binarios, con valores 0,1. Sobre ellos se construyeron todas las variaciones con repetición posibles, que representaban los subconjuntos de {1, 3, 5, 7, … 2K+1}

(3) De las sumas construidas sobre esos subconjuntos se eligieron aquellas cuyo resultado fuera N para acumularlas a un contador y obtener S(N).

De esta forma hemos conseguido la sucesión de la imagen, que coincide con http://oeis.org/A000700

En ella vemos, por ejemplo, que el 16 admite cinco descomposiciones en suma de impares distintos:

16=7+9=5+11=3+13=1+15=1+3+5+7

y 17 otras cinco:

17=17=3+5+9=1+7+9=1+5+11=1+3+13

¿Ves una posible relación empírica?

Parece ser, según la tabla, que un número par y su siguiente suelen presentar el mismo número de descomposiciones, pero algunas otras veces no. Por eso hablamos de algo empírico y aproximado. Puede ser instructivo encontrar las sumas de cada uno para descubrir algunas coincidencias.

Hemos exigido que los números impares sean distintos, pero podríamos permitir repeticiones del tipo 17=1+3+3+3+7. Esto complicaría la cuestión y nos llevaría a las particiones de un número. Puedes consultar

http://hojaynumeros.blogspot.com.es/2011/02/particiones-de-un-numero.html 

y

http://hojaynumeros.blogspot.com.es/2011/02/funciones-de-particion-de-un-numero.html

En este caso usaríamos la función “partición en números impares”, que, según demostró Euler, coincide con la partición en partes distintas. (Ver http://oeis.org/A000009) En una entrada posterior comprobaremos esta propiedad.

Estas descomposiciones son casos particulares de la llamada representación de un número según una lista, que ya tratamos en otra entrada (http://hojaynumeros.blogspot.com.es/2010/02/frobenius-y-los-mcnuggets.html)

El concepto es el siguiente: dado un conjunto de números enteros positivos a₁, a₂, a₃,…a_n, diremos que otro entero positivo N es representable según ese conjunto si existen coeficientes enteros no negativos x₁, x₂, x₃,…x_n tales que N= a₁*x₁+a₂*x₂+…a_n*x_n

Si exigimos que los coeficientes sólo puedan valer 0 o 1, obtendremos la descomposición en elementos distintos, como hemos hecho en esta entrada. Si los dejamos libres pasaremos al caso general del problema, también llamado “de las monedas”.

Este problema bien merece otra entrada en la que presentemos una herramienta en hoja de cálculo para resolverlo.

Las sumas de impares (1)

Esta entrada participa en la edición 3.1415926 del Carnaval de Matemáticas, alojado en el blog Series divergentes

-----------------------------

Una entrada del curso pasado la terminamos con esta propuesta

¿Qué opinas de esta serie de igualdades?

¿Son verdaderas? ¿Se pueden prolongar indefinidamente?¿Cuál es su valor común?

Al analizarla vemos que se manejan sumas de impares consecutivos. En cada una de las fracciones se han sumado varios impares consecutivos, se han “saltado” otros y después se han comenzado a sumar los siguientes.

En los numeradores se han saltado tantos impares como se han sumado cada vez (dos). La expresión de las sumas será entonces: (1+3+…2k-1)+(6k+1+6k+3+…)

que equivale a m²+9m²-4m²=6m²

En los denominadores se va formando m²+16m²-9m²=8m²

Luego los cocientes son equivalentes a 3/4

Gráficamente en los numeradores se da esta situación (imagen 1):

En ella vemos perfectamente que la suma equivale a 6 cuadrados como el pequeño de arriba a la izquierda, es decir, 6m²

En los denominadores se da esta otra (imagen 2), en la que podemos contar 8 cuadrados, que equivalen a 8m², luego el cociente siempre será 6/8=3/4, que es la solución.

¿Ocurrirá siempre así? ¿Todas las configuraciones de este tipo representarán un múltiplo del cuadrado menor?. Lo vemos:


Sumas de impares consecutivos

Al sumar varios impares consecutivos se formaría un conjunto de gnomones adosados como el de la imagen. Su fórmula depende del gnomon inicial, que siendo k su número de orden (en la imagen 7, porque 13 es el séptimo)  viene dado por 2k-1 y el número de sumandos h. Si sumamos todos resultará 2k-1+2k+1+2k+3+…2k+2h-3 Acudimos a la suma de una progresión aritmética y daría (2k-1+2k+2h-3)*h/2=(2k+h-2)*h

En el caso de la imagen 3 el número de cuadraditos generado sería (2*7+4-2)*4=64=4h² No debes interpretar esta cantidad en el sentido geométrico, pues el cuarto cuadrado, si observas la imagen, está formado por dos mitades, una en cada brazo del gnomón.

Este último resultado es casual, porque en general no resulta un múltiplo de h². Lo puedes comprobar para k=8 y h=3, en el que (2*8+3-2)*3=51, que no es múltiplo de 9. Por tanto, no todos los gnomones adosados pueden representarse como un múltiplo del cuadrado de su anchura.

Serán descomponibles los que cumplan que 2k-2 sea múltiplo de h, pues entonces

(2k+h-2)*h=(Mh+h)*h=(M+1)*h²

Eso ocurre en este caso, en el que k=7 y h=3, con lo que 2*7-2=12 es múltiplo de 3. Calculando, el número engendrado sería (2*7+3-2)*3=45=5*3²

Lo puedes verificar en la imagen 4

Otra forma de verlo es que esta suma de impares es una diferencia de cuadrados: (k+h-1)² – (k-1)² =2kh+h²-2k-2h+2k=(2k+h-2)*h y llegamos a la misma expresión.

A la inversa, si exigimos que el resultado sea del tipo Mh², se dará (2k+h-2)*h= Mh², lo que lleva a 2k+h-2=Mh y a 2k-2=(M-1)h, es decir a la condición sugerida de que 2k-2 sea múltiplo de h.

Las sumas con las que comenzamos este análisis (imágenes 1 y 2), no sólo lo cumplen, sino que de forma más fuerte: k-1 es múltiplo de h. Si este valor es impar, ambas condiciones son equivalentes, pero si es par no lo son.

Si exigimos que k-1 sea múltiplo de h, lo que logramos es que la partición en cuadrados tenga sentido físico, que se “vean” los cuadrados, como ocurre en la imagen 4 (y en las dos primeras si te imaginas los cuadrados troceados)

¿Y qué ocurre con el número de cuadrados?

Te proponemos una demostración:

Si exigimos la condición fuerte, que k-1 sea múltiplo de h, el número será par, e impar en el caso contrario.

¿Qué hay detrás de los decimales periódicos? (2)

Con el apoyo de la teoría explicada en la anterior entrada describiremos a continuación una sencilla herramienta para hojas de cálculo que encuentra el anteperiodo y el periodo de un desarrollo decimal.

Necesitaremos las siguientes operaciones:

(1) Simplificar la fracción cuyo desarrollo decimal deseamos conocer. Esto se consigue en las hojas de cálculo dividiendo las celdas del numerador y del denominador por su MCD mediante la función M.C.D(A;B)

(2) Extraer del denominador los factores 2 y 5 tomando nota de sus exponentes (cero si no figuran) y quedándonos con el máximo, que será el número de cifras del anteperiodo

Un código posible para la extracción del 2 (igual se procede para el 5) puede ser este:

Public Function expo2(n)
Dim e, m
m = n
e = 0
While m / 2 = m \ 2
e = e + 1
m = m / 2
Wend
expo2 = e
End Function

Nos devuelve cero si el 2 no es divisor del denominador y el exponente en caso afirmativo. En la imagen puedes ver la disposición de cálculo que hemos elegido. El máximo se consigue con la función  MAX(A;B) aplicada a los dos exponentes (del 2 y del 5)

(3) Obtener la parte del denominador coprima con 10. Para ello basta dividir el denominador entre las dos potencias de 2 y 5 obtenidas.

(4) Obtener el gaussiano de 10 respecto a esa parte coprima. Podríamos usar exponenciación modular (ver http://hojaynumeros.blogspot.com.es/2012/03/de-la-multiplicacion-rusa-la.html), pero en este caso, como la generación de restos se realiza mediante mltiplicaciones por 10, hemos elegido el método directo, que no es demasiado lento en el rango de números que manejan las hojas.

(Añadimos comentarios al código)

Public Function gauss10(m)
Dim r, g, i

g = 1
r = 10 - m * (10 \ m) ‘Obtenemos el primer resto
While r <> 1 ‘Mientras no encontremos un resto igual a uno, seguimos
r = r * 10  ‘Cada resto es igual al anterior multiplicado por 10
r = r - m * (r \ m) ‘y convertido en resto módulo m
g = g + 1 ‘En cada ciclo aumenta el gaussiano
Wend
gauss10 = g
End Function

En el caso de la primera imagen el denominador era 30940, que contenía como factor 2²*5. Eliminado este, quedó reducido a 1547, y aplicando el cálculo del gaussiano resulta nada menos que un periodo de 48 cifras, fuera del alcance ordinario de una hoja de cálculo.

(5) Expresión del anteperiodo y el periodo. Cuando ambos presentan muchas cifras, como en el caso del ejemplo, es mejor expresarlas en forma de texto, y no de número. El procedimiento consiste básicamente en el mismo usado para encontrar el gaussiano, multiplicar cada resto por 10 y reducirlo a resto módulo el denominador. Sirve igual para las cifras periódicas que para las no periódicas. La diferencia ahora es que los restos los convertimos en texto y los vamos incorporando a una cadena del mismo tipo.

El procedimiento completo puede resultar aburrido y dejamos su estudio a quien descargue la herramienta e inspeccione su código. Para el resto de lectores resultará una buena forma de comprobar los cálculos manuales.

Al necesitar calcular por separado la parte entera, el anteperiodo y el periodo, hemos preferido usar un botón y una macro para mayor comodidad:

Tienes esta herramienta en la dirección

http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#periodo

¿Qué hay detrás de los decimales periódicos? (1)

Hace unos meses comentaba con un amigo el tratamiento que se podía hacer con hoja de cálculo de los decimales periódicos. Ya en una de las primeras entradas de este blog encontrábamos los decimales de este tipo

http://hojaynumeros.blogspot.com.es/2008/10/grandes-periodos.html

Lo que no nos planteamos en esa ocasión fue el cálculo del número de decimales del periodo, su longitud, mediante un cálculo directo, ni tampoco la del anteperiodo. Lo abordamos hoy mediante la ayuda de las congruencias y de los restos potenciales.

¿Qué es sacar decimales en una división o en una fracción?

Fundamentalmente se trata de multiplicar los distintos restos por 10 y hallar su nuevo resto respecto al cociente. Cuando este se repita, ya hay periodo.

Si tenemos una división entera de dividendo D, divisor d, cociente Q y resto R, sabemos que están relacionados por D=d*Q+R. Si multiplicamos R por 10 y volvemos a dividir entre Q (sacar el primer decimal) obtendremos R*10=d*q₁+r₁, donde q₁ es el primer decimal y r₁ el siguiente resto. Si unimos ambas relaciones se obtendrá

 D*10=(10*Q+q₁)*d+r₁

El paréntesis representa el nuevo cociente con un decimal, pero sin coma, es decir, multiplicado por 10. Ya hemos sacado un decimal.

Si damos otros pasos obtendremos

D*10²=(10²*Q+10*q₁+q₂)*d+r₂
D*10³=(10³*Q+10²*q₁+10*q₂+q3)*d+r₃
…

Desarrollo decimal exacto o periódico

Sabemos desde la enseñanza secundaria que si el divisor sólo posee los factores primos 2 y 5 el proceso anterior nos lleva a un resto nulo y al fin del cálculo, lo que llamamos decimal exacto. Si existen otros factores aparecerá un anteperiodo si entre ellos figuran el 2 o el 5 y finalmente, el decimal se conviertirá en periódico con un periodo inferior o igual a d-1.

¿Qué hay detrás de estos hechos?: los restos potenciales del 10 respecto al divisor.

Los repasamos.

Restos potenciales

Imaginemos las congruencias definidas respecto a un módulo m

(http://hojamat.es/sindecimales/congruencias/teoria/teorcong.pdf)

y sea n un número natural. Llamaremos Restos potenciales de n respecto a m a los
restos producidos por las distintas potencias naturales de n respecto al módulo m.

Por ejemplo, los restos potenciales de 5 respecto al módulo 3 son:

De 5⁰ el resto es 1, de 5¹ el resto es 2, de 5² el 1, de 5³ el 2, etc. y así siguen de forma periódica.

Se puede ver muy fácilmente que si se tiene un resto potencial de n respecto a m, para conseguir el siguiente basta multiplicar el actual de nuevo por n y hallarle el resto respecto a m. No hay que hallar la potencia completa.

El conjunto de restos potenciales sigue unas pautas muy sencillas:

1. Si m sólo contiene los factores primos de n, se llegará a cierta potencia de n que será múltiplo de m y por tanto, a partir de ella, todos los restos potenciales serán nulos.

Sería el caso, por ejemplo, de los restos potenciales de 60 respecto al 18, cuyos factores primos 2 y 3 lo son también de 60. La potencia k que consiga que 60^k sea múltiplo de 18 producirá un resto cero y al seguir multiplicando por 60 también serán nulos los restos que aparezcan.

60⁰º1(mod 18

60¹º6 (mod 18

60²º0 (mod 18

60³º0 (mod 18

60⁴º0 (mod 18

…..

Ya todos serían nulos. Hemos tenido que llegar a 60² para absorber el 3² que figura en el desarrollo de 18=2*3²

(Este desarrollo y los siguientes los puedes comprobar con la herramienta “Restos potenciales” que puedes descargar desde

http://hojamat.es/sindecimales/congruencias/inicongruencias.htm)

En general, habrá que llegar a la potencia que viene determinada por el mayor de los cocientes (por exceso si no son enteros) entre los exponentes de los factores primos de m y sus homólogos en n.

En efecto, si n=p^aq^br^c    y m=p^a’q^b’r^c’ supongamos que elevamos n a un exponente k y que con eso conseguimos que n^k sea múltiplo de m. Esto nos llevaría a que
n^k=( p^aq^br^c)^k = p^akq^bkr^ck sea múltiplo de m= p^a’q^b’r^c’, que a su vez implica que ak³a’, bk³b’ y ck³c’, lo que supone que k sea mayor o igual que los cocientes a/a’, b/b’ y c/c’, tal como hemos afirmado: el mínimo valor de k es el mayor cociente tomado por exceso entre los exponentes en n y sus homólogos en m.

2. Si m es primo con n, los restos son periódicos de periodo el índice o gaussiano de n respecto a m. El resto 1 se producirá en los múltiplos de ese gaussiano.

Si recorremos los restos potenciales de n respecto a m, si ambos son primos entre sí, por el teorema de Euler se cumplirá que

n^j(m)º1 (mod m

Se representa mediante j(m) la indicatriz de Euler
(ver http://hojaynumeros.blogspot.com.es/2012/07/la-herencia-de-euclides-5-la-funcion.html)

Así que a partir de una de las potencias aparece el resto 1 y al seguir multiplicando por n irán apareciendo los demás de forma periódica.

Otra forma de verlo es que en este caso n es inversible en Z_m, no divisor de cero, por lo que sus potencias producirán todas restos no nulos (ver http://hojaynumeros.blogspot.com.es/2012/06/la-herencia-de-euclides-3-el-anillo-zm.html) y esto nos llevará a que se repita alguno, porque su máximo número es m-1.

Sean dos potencias de n que producen el mismo resto: n^rºn^r+h (mod m. En ese caso se cumplirá que n^r+h-n^r=n^r(n^h-1) será múltiplo de m. Pero este es primo con n, luego no puede dividir a n^r y lo hará a n^h-1. Esto quiere decir que n^hº1 (mod m y podemos afirmar que:

En general, no hay que llegar hasta el exponente j(m) para conseguir un resto igual a 1. Llamaremos gaussiano, orden o índice de n respecto a m al menor exponente k al que hay que elevar n para producir resto 1 respecto al módulo m.

Por tanto, cuando n y m son primos entre sí, los restos potenciales forman una sucesión periódica a partir del primero con periodo igual al gaussiano de n respecto a m.


3. Por último, si m posee los mismos factores primos de n y alguno más, la sucesión comenzará con unos restos no periódicos, tantos como el mayor cociente entre los factores comunes de uno y otro (ver primer caso),  a los que seguirán otros periódicos.

Si m contiene factores comunes con n y otros no comunes, lo podemos descomponer así: m=m₁*m₂, donde m₁ contiene los comunes y m₂ los no comunes. Si volvemos a repetir el análisis anterior sobre potencias cuyos restos se repiten, llegaremos a esto:
n^r(n^h-1) será múltiplo de m=m₁*m₂ con la suposición de que n^r produce el primer resto que se repite.
Pero m₂ es primo con n^r, luego dividirá a n^h-1. Con un razonamiento similar al del caso 1, llegaremos a que el menor valor de h es el gaussiano de n respecto a m₂.

De igual forma, si m₁ sólo contiene factores primos comunes con n, no podrá dividir a n^h-1, luego lo hará a n^r.   Hemos indicado que n^r produce el primer resto que se repite, luego todos los anteriores no pertenecerán a la parte periódica, y formarán el anteperiodo, ya que la condición de que m₁ divida a n^r garantiza que r es mayor que 0. Para que n^r sea múltiplo de m₁ sólo tendremos que usar el criterio del mayor cociente de factores comunes, como en el primer caso.

Aplicación a los decimales periódicos

Todo lo que hemos aprendido se aplica a la generación de decimales. Aquí n=10, luego los factores comunes sólo serán el 2 y el 5. El divisor d equivale a la m que hemos usado en los razonamientos.

Antes de generarlos, la fracción D/d se habrá convertido en irreducible, luego D y d son primos entre sí. Esto es muy importante, porque según una conocida propiedad de la aritmética modular, si la sucesión 10, 10², 10³, 10⁴,…la multiplicamos por D, coprimo con el módulo d, la sucesión resultante D*10, D*10², D*10³, D*10⁴,…forma un sistema de restos con las mismas propiedades, salvo quizás los valores de los mismos.

Resumiendo:

Si d sólo contiene los factores 2 y 5, el proceso de generación de decimales  termina con un r_k=0 (cuando la potencia de 10 del primer miembro contenga 2 y 5 con exponentes mayores o iguales a los de d) y se obtendrá un desarrollo decimal exacto.

Si el divisor d no contiene como factores ni el 2 ni el 5 se producirá un decimal periódico puro en la que todos los restos se repetirán a partir del primero, con periodo igual al gaussiano de 10 respecto al divisor d

Si d contiene además del 2 o 5 otros factores, el desarrollo comenzará con k decimales no periódicos (el anteperiodo), siendo k el mayor exponente tomado entre los del 2 y el 5 que figuran en la factorización prima de d, seguidos de un periodo con tantas cifras como indique el gaussiano de 10 respecto a la parte de d que no contiene 2 ni 5. Se formaría un decimal periódico mixto

En la siguiente entrada describiremos una sencilla herramienta para hojas de cálculo que encuentra el anteperiodo y el periodo de un desarrollo decimal.

La herencia de Euclides (5) La función indicatriz de Euler

Esta es la última entrada del curso 2011-12. Felices vacaciones para quienes las tengan. A los amigos del hemisferio Sur les deseamos paciencia. En Septiembre volvemos.

Terminamos esta serie sobre las aplicaciones encadenadas del algoritmo extendido de Euclides con la presentación de la función j(n) (indicatriz o indicador de Euler) como el cardinal del conjunto de elementos inversibles en Z_n

Sólo nos interesará por ahora este aspecto de la función j(n)

Todas las propiedades de j(n) las tienes en multitud de libros y páginas web. Entre ellas puedes consultar

http://gaussianos.com/la-funcion-phi-de-euler-otra-genialidad-del-maestro/
http://hojamat.es/sindecimales/divisibilidad/teoria/teordivi.pdf
http://hojamat.es/parra/funesp.pdf
http://mathworld.wolfram.com/TotientFunction.html

Aquí sólo destacaremos que j(n) es el cardinal del grupo de inversibles Z*_n, (ver nuestra anterior entrada) es decir, el conjunto de números menores que n y primos con él, contando el 1. Esta definición nos desemboca inmediatamente en su carácter multiplicativo.

En efecto, en la entrada anterior explicábamos que el Teorema Chino de los Restos  nos garantizaba que existía un isomorfismo entre el anillo Z_m×Z_n y el anillo Z_mn cuando m y n son coprimos. También vimos que este isomorfismo se podía restringir a los grupos de inversibles, es decir, que el grupo Z*_m×Z*_n es isomorfo a Z*_mn.

Pues ya lo puedes tener claro…el cardinal del primero es j(m). j(n) y el cardinal del segundo j(m.n), luego…

¡Ya hemos llegado a donde queríamos después de más de un mes!

La función indicatriz de Euler es multiplicativa, porque si m y n son coprimos, se cumple que


j(m). j(n) = j(m.n)

No estaría mal que buscaras otra demostración de esta importante propiedad.

En la hoja euclides.xlsm  o en la euclides.ods (http://hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm),
en el apartado del isomorfismo, puedes comprobar esta propiedad en casos concretos.

Es curioso que sea multiplicativa una función que cuenta “huecos” (los que no tienen factores comunes con n), que proceden de un cribado, pero si los cuentas como los elementos inversibles de un anillo, los que sobran son los otros, los divisores de cero.

Si has leído las páginas recomendadas o si nos sigues con atención no tendrás problemas en entender que

Si p es primo, j(p)=p-1

¡Pues claro! ¿Qué número va a tener divisores con p, salvo él mismo?

Si n=p^k con p primo(es decir, es un número primario), j(n)=p^k(1-1/p)

Aquí nos detenemos algo más: Los números menores que p^k que tienen divisores comunes con él sólo pueden ser p, p², p³,…p^k, es decir, son en total p^k-1 números, luego

j(n)=p^k - p^k-1 = p^k(1-1/p)

¿Y si n no es primo ni primario?

En ese caso viene en nuestra ayuda la propiedad multiplicativa:

Si N=p^aq^br^cs^d, siendo p,q,r,s divisores primos de N, entonces se tendrá j(N)=N(1-1/p) (1-1/q) (1-1/r) (1-1/s)

Lo ponemos en limpio:

Implementación de la función en hoja de cálculo

Podemos definir la función de dos formas, por su definición o mediante la fórmula anterior. En el primer caso nos resultará un código sencillo y fácil de entender, pero que se vuelve insoportablemente largo para números grandes. Sería este:

Mediante su definición


Definimos en primer lugar el MCD mediante el algoritmo de Euclides

Public Function mcd(a1, b1)
Dim a, b, r


r = 1
a = a1
b = b1
If b = 0 Then b = 1
If a = 0 Then a = 1
While r <> 0
r = a - b * Int(a / b)
If r <> 0 Then a = b: b = r
Wend
mcd = b
End Function

Después vamos contando los números menores que N coprimos con él

Public Function euler(a)
Dim  n, eu, s


If a = 0 Then a = 1
n = 1: s = 0
If a = 1 Then
s = 0
Else
While n < a
If mcd(a, n) = 1 Then s = s + 1
n = n + 1
Wend
End If
euler = s
End Function

Esta función no va mal para números pequeños, pero es más rápida en general esta otra:

Public Function euler(n)
Dim f, a, e
Dim recoge As Boolean


a = n ‘se copia porque se va a alterar su valor en el algoritmo
f = 3 ‘variable de búsqueda de factores primos
e = n ‘valor inicial de la indicatriz
If n / 2 = Int(n / 2) Then e = e / 2 ‘si es par, la indicatriz se divide entre 2
While f <= a ‘se van buscando los factores primos
If esprimo(f) Then
recoge = True
While esmultiplo(a, f)
a = a / f ‘se divide para ahorrar tiempo (algoritmo voraz)
If recoge Then e = e * (f - 1) / f: recoge = False ’sólo se recoge el factor una vez
Wend
End If
f = f + 2 ‘recorre los impares
Wend
euler = e
End Function

El código está basado en la fórmula que hemos obtenido: por cada factor primo p se multiplica por p-1 y se divide entre p.

Hemos efectuado pruebas, y para números del orden de 10⁵ el tiempo de cálculo se reduce en más de una quinta parte respecto a la primera versión de la función. Así que adoptaremos esta.

También la tenemos implementada en el Buscador de Naturales con el nombre de EULER(N), pero por ahora en la versión lenta.

Te proponemos una búsqueda: Elige un número cualquiera y busca todos sus divisores con el Buscador (http://hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm) y evalúa j(N) en cada uno de ellos. Observa la suma: ¿qué obtienes?

Hemos buscado los divisores de 1228, le hemos sumado los valores de la indicatriz y hemos obtenido como suma en el Evaluador otra vez el número 1228

La explicación, si tenemos ánimos, se queda para el curso que viene. 

La herencia de Euclides (4) El teorema chino de los restos

Este teorema lo conocemos todos, pero quizás no hayamos pensado que es la garantía de algún isomorfismo de anillos. Lo iremos viendo.

Se enuncia así:

Si M₁, M₂, M₃…M_n son números enteros primos entre sí dos a dos y B₁, B₂, B₃,…B_n, otros números enteros cualesquiera, existe otro número natural N único que cumple NºB_i (mod M_i) para todo i entre 1 y n.
NºB₁(mod M₁)
NºB₂ (mod M₂)
NºB₃ (mod M₃)
…
NºB_n (mod M_n)

Todas las demás soluciones del sistema son congruentes con N respecto a un módulo H igual al producto de los módulos.

La demostración la puedes consultar en cualquier manual. A nosotros nos va interesar especialmente la unicidad de la solución respecto al módulo H. Su fundamento está en que si dos números son congruentes respecto a módulos primos entre sí, también serán congruentes respecto al producto de los módulos. Así, en este caso, si N₁ y N₂ fueran dos soluciones distintas, serían congruentes respecto a todos los módulos M₁, M₂, M₃…M_n  y por tanto congruentes respecto a H, que es lo que garantiza su unicidad.

La resolución más popular de este sistema de ecuaciones es la que ideó Gauss:

Algoritmo de Gauss

Para calcular el número N se sigue el proceso:

 Llamemos H al producto de todos los módulos M_i y sea M’_i = H/M_i.

 Se buscan unas m_i tales que m_i.M’_iº1 (mod M_i) es decir, sus inversos,  y entonces la solución será:

 donde hemos llamado E_i al producto M_i*m_i

 Se puede demostrar que las demás soluciones son congruentes con N módulo H

Ejemplo

Encontrar un número n tal que al dividirlo entre 10 nos dé de resto 7, y al dividirlo entre 9 obtengamos un resto de 3.

H=9.10 = 90 ; M’₁=9 ; M’₂=10 ; m₁=9 (porque 9*9=81º1 (mod 10) ); m₂=1 (porque 1*10=10º1 (mod 9) ). Así tenemos que E₁=9*9=81 y E₂=10*1=10 y por último:

N=81.7+10.3= 597.  Lo reducimos a módulo 90 y queda 57. En efecto, 57º7 (mod 10) y 57º3 (mod 9)

Para encontrar las demás soluciones bastará con ir sumando H=90: 57, 147, 237, 327,…

Estos coeficientes E_i tienen la ventaja de que sólo dependen de los módulos, por lo que se pueden tener almacenados si se van a usar varias veces. Por ejemplo, si el resto deseado para módulo 10 hubiese sido el 2 y para módulo 9 el 6, la solución hubiera sido N=81.2+10.6=162+60=222º42 (mod 90) y se cumple que el resto de 42 respecto a 10 es 2 y respecto a 9 es 6, como deseábamos.

Ya te habrás imaginado que vendría la hoja de cálculo en nuestro auxilio para librarnos de algunos cálculos si el número de ecuaciones aumenta. En la imagen tienes el desarrollo del ejemplo anterior:

En la región superior escribimos los módulos M_i, los valores de B_i y el número de ecuaciones. En el central se calcula H, las H_i y sus inversos (mediante el algoritmo de Euclides interno que estamos usando en esta serie). Por último, se efectúa la suma de los productos triples y se reduce a módulo H, se escriben varias soluciones y se comprueba la primera.

El caso de dos ecuaciones

Si la solución de este problema es única, podríamos definir una función y(a,b,m,n) tal que a cada par de enteros a y b y dos módulos m y n primos entre sí les asignara la solución N tal que Nºa (mod m)  y  Nºb (mod n). Si los módulos no fueran primos entre sí le podríamos asignar el valor de alarma, por ejemplo el cero.

Por otra parte, para todo entero N existen dos enteros únicos a y b tales que Nºa (mod m)  y  Nºb (mod n). Por tanto, tenemos delante una correspondencia biunívoca entre el conjunto Z_m×Z_n y el conjunto Z_mn (Recuerda que m y n han de ser coprimos).

Esta biyección la hemos representado en la hoja de cálculo que nos sirve de herramienta en esta serie. En una hoja dedicada a la misma puedes consultar las distintas correspondencias. En la imagen tienes la existente entre Z₈×Z₉ y el conjunto Z₇₂.

Pero esta correspondencia es más fuerte, porque constituye un isomomorfismo de anillos para la suma y el producto. En efecto, sabemos que para cada resto N de Z_mn, según el teorema chino, corresponde un resto p en Z_m y otro q en Z_n y que esa correspondencia es biunívoca. Supongamos otro N’ que se corresponda con p’ y q’ respectivamente. Así, si N’ºp’ (mod m) y N’ºq' (mod n), podemos sumar y multiplicar miembro a miembro ambas congruencias y quedará: N+N’ºp+p’ (mod m) y de igual forma N+N’ºq+q’ (mod n). Por tanto, a la suma (p,q)+(p’+q’) en Z_m×Z_n le corresponde la suma N+N’ en Z_mn. Esto nos demuestra que la correspondencia es un homomorfismo para la suma. Igual razonaríamos para el producto.

Por tanto, nuestra función y quedará como un isomorfismo entre anillo Z_m×Z_n y el anillo Z_mm


y(a+a’, b+b’)= y(a, b)+ y(a’, b’)   y  y(a*a’, b*b’)= y(a, b)* y(a’, b’)

Compruébalo en la tabla de más arriba m=8 y n=9:y(4,7)=52, :y(2,4)=58 y si sumamos modularmente, y(6,2)=38, que es congruente con 52+58=110, módulo 72. Si multiplicamos modularmente ocurre lo mismo: y(0,1)=64 y 52*58=3016º64 (mod 72)

Correspondencia entre inversibles

Si el resto p es inversible en Z_m, será porque no tiene factores primos comunes con m. De igual forma, si q es inversible en Z_n, no compartirá factores con n. Si aplicamos la función y(p,q)=N (si suponemos que m y n son coprimos), este resultado N será coprimo con m y con n, pues en caso contrario produciría divisores de cero tanto en Z_m como en Z_n. Por tanto, N es inversible en Z_mn

La correspondencia y(p,q)=N convierte inversibles en inversibles.

Volvemos a la tabla ejemplo: 5 es inversible en Z₈, 4 es inversible en Z₉. Les aplicamos la función y y según la tabla queda y(5,3)=13, que es inversible módulo 72.

La consecuencia de esto queda para otra entrada,

La herencia de Euclides (3) El anillo Zm

Recordábamos en la entrada anterior la formación del anillo Z_m mediante clases de restos hasta formar el conjunto {0, 1, 2, … m-1}. Repasa estas páginas si lo deseas:

http://es.wikipedia.org/wiki/Aritm%C3%A9tica_modular
http://hojamat.es/sindecimales/congruencias/teoria/teorcong.htm
http://mathworld.wolfram.com/ModularArithmetic.html

A este conjunto Z_m se le puede dotar de la suma y el producto módulo m que lo convierten en un anillo conmutativo con unidad, que es el resto 1. Esto lo tienes en

http://personales.unican.es/ruizvc/algebra/anillos1.pdf
http://en.wikipedia.org/wiki/Ring_(mathematics)
http://hojamat.es/sindecimales/congruencias/teoria/teorcong.htm#residuales

En realidad, bastaría afirmar que Z_m es el anillo cíclico de m elementos. Busca en la Red ese concepto, que es muy sencillo. Por esta estructura cíclica se pensó en llamarles anillos por primera vez.

En los anillos con unidad son importantes los elementos inversibles. De ellos trataremos aquí.

Un elemento A de Z_m es inversible si existe otro elemento X de Z_m tal que A*Xº1 (mod m) Según vimos en la entrada anterior, esta ecuación tiene solución única siempre que A sea primo con el modulo m. Luego los restos primos con m son inversibles.

Por el contrario, si A y m tienen un divisor común, para que la ecuación tuviese solución debería ser divisor también de 1, lo que es imposible. Si el elemento A tiene divisores comunes con m, entonces A no es inversible.

Llamamos divisor de cero en un anillo a aquel elemento A que multiplicado por cierto elemento no nulo C del anillo, da un producto nulo: A*Cº0. En este caso en el que A tiene factores comunes con m, es un divisor de cero, porque si D=MCD(A,m), tendremos que A=A’*D y m=m’*D. Multiplicando A por m’ (que es no nulo) resulta Am’=A’D*m/D=A’m, que es congruente con cero, luego A*m’º0 (mod m) y por tanto divisor de cero.

Los divisores de cero no son inversibles, porque si A fuera inversible y divisor de cero, se daría una igualdad del tipo A*Cº0 con C distinto de cero, pero multiplicando por el inverso resultaría:
A^-1*A*C=C=A^-1*0 lo que daría C=0 en contra de lo supuesto.

Así que:

 Si el elemento A es primo con el módulo m, entonces es inversible, es decir, que existe algún otro elemento B tal que A*B=B*Aº1. En entradas anteriores vimos cómo encontrarlo mediante el algoritmo extendido de Euclides.

 Si el elemento A no es primo con m, es un divisor de cero, y por tanto no inversible.

Grupo de inversibles

El producto de dos inversibles A y B también lo es, y su inverso es B^-1*A^-1, ya que

 (B^-1*A^-1)*A*BºB^-1*(A^-1*A)*BºB^-1*1*Bº1

Como el 1 es inversible trivialmente y el inverso también, tenemos que los inversibles forman grupo abeliano, llamado grupo de las unidades Z*_m


Como es conocido, la función indicatriz de Euler cuenta los números menores que m y primos con él, por tanto, el cardinal del grupo Z*_m coincide con la indicatriz o función j(x) de Euler.

Si m es primo, todos los elementos son inversibles y Z_m se convierte en un cuerpo, pero yo creo que eso ya lo sabías.

La hoja que estamos usando en esta serie de entradas también nos da el grupo Z*_m de unidades de Z_m. Nos seguimos basando en el algoritmo de Euclides extendido.

Para cada elemento de Z_m se va llamando a la rutina euclides(X,m) (de ahí la ventaja de tenerla implementada como una rutina en Basic), mediante la cual se encuentra el MCD(X,m). Si es igual a 1, se escribe el inverso junto al elemento. En la imagen puedes ver el desarrollo para m=12, y nos da como elementos inversibles 1, 5, 7 y 11.

Contando los inversibles se encuentra la indicatriz de Euler, a la que volveremos próximamente.

Finalmente, a la derecha del esquema se construye el grupo multiplicativo de unidades. Observa que, como era de esperar, todos los productos pertenecen al conjunto {1, 5, 7, 11}

Con esta hoja es fácil comprender el teorema de Euler. Observa, por ejemplo, la fila que corresponde al valor 7:{7, 11, 1, 5} Esto quiere decir que 7*1º7, 7*5º11, 7*7º1 y 7*11º5. Imagina que multiplicamos las cuatro congruencias miembro a miembro:

7*1*7*5*7*7*7*11º7*11*1*5   Simplificamos entre 7*11*1*5  (porque son inversibles, si no, no se podría) y queda

7*7*7*7 º1, es decir 7⁴º1. Pero 4 es la función de Euler de 12 y de ahí la comprobación del teorema:

7 ^j(12) º1 (mod 12)

Esto no es una demostración, pero si repites lo mismo con valores generales p y m con p inversible, es fácil demostrar que p ^j(m) º1 (mod m)

Orden de un elemento

Dado un elemento inversible a, llamaremos orden de ese elemento al mínimo número entero tal que a^rº1.

Según el teorema citado, ese valor existe y puede ser j(m). Si es menor, ha de ser un divisor suyo. En efecto, supongamos que j(m) no fuera múltiplo del orden r. Entonces efectuando la división entera entre ambos quedaría j(m)=qr+s, con s<r. Aplicamos esa potencia al elemento a y obtendríamos
1ºa^j(m) ºa^qr+sºa^qr*a^sº a^s , luego a^sº1 en contra del carácter mínimo de r.

Así que el orden ha de ser un divisor de la función j(m)

Hemos incorporado a la hoja el cálculo del orden de los elementos inversibles, pero sería un buen ejercicio que los comprobaras usando la tabla de multiplicar. En la imagen puedes consultar el orden de los elementos en el caso de m=10. Observa que los cuatro son divisores de la indicatriz j(10)=4