PDF de programación - Cuestiones modulares

Cuestiones modulares



Edición 2016

Colección Hojamat.es

© Antonio Roldán Martínez

http://www.hojamat.es



1





PRESENT ACIÓN



Los temas de Aritmética Modular son muy poco conocidos para
personas con cultura matemática de tipo medio. Sin embargo, su
aparente simplicidad y la elegancia de sus desarrollos los convierten
en un pequeño tesoro.



Otra característica es que aparecen por sorpresa en otros
planteamientos que se diría ajenos a estas cuestiones. Son pocos
conceptos pero muy potentes.



Como advertiremos en todos los documentos de esta colección, el
material presentado no contiene desarrollos sistemáticos, ni pretende
ser un manual teórico. En cada tema se incluirán cuestiones curiosas o
relacionadas con las hojas de cálculo, con la única pretensión de
explicar algunos conceptos de forma amena.



A partir de la edición 2016 se han incorporado los temas de orden de
un lemento, raíces primitivas y e índices modulares, con lo que ha
quedado un documento bastante completo.



2







T AB L A D E C O N T E N I D O


Presentación ..................................................................................................2

La exponenciación modular ........................................................................4

¿Qué hay detrás de los decimales periódicos?..........................................7

El algoritmo extendido de Euclides ......................................................... 15

La ecuación Ax=B (mod m) ..................................................................... 19

El anillo Zm ............................................................................................... 22

El teorema chino de los restos ................................................................ 27

La función indicatriz de Euler (n) ........................................................... 31

Restos cuadráticos .................................................................................... 36

Introducción ............................................................................................. 36

Criterio de Euler ....................................................................................... 39

Propiedades de los restos cuadráticos .................................................... 43

Grupos de potencias en Zn ....................................................................... 46

Índice o gaussiano de un resto en Zn ..................................................... 46

Subgrupos cíclicos en Zm* ...................................................................... 55

Raíces primitivas ..................................................................................... 60

Índices modulares .................................................................................... 65



3







L A E XP O N E N C I A CI Ó N M O D U L A R


En algunos problemas, como en el criterio de primalidad de Fermat,
debemos elevar un elemento de Zm a un exponente alto. Son
frecuentes los problemas del tipo “¿en qué cifra termina 263721?” o “¿es
cierta la congruencia 2341251 (mod 23)?”

lo que se acude a

Si el exponente es grande pueden desembocar en cálculos muy
complicados, por
la exponenciación por
duplicación. Estas técnicas que se basan en duplicar son muy
antiguas. Ya conocemos el método usado en Egipto
http://hojamat.es/parra/mat_antig.pdf)
multiplicación a la rusa.

posteriormente

y

(ver

la

llamada

Tenemos implementada, como una curiosidad, esta suma para hojas
de cálculo

(ver

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

y

también tienes una exposición teórica en

http://tiopetrus.blogia.com/2005/042501-multiplicacion-a-la-rusa-1-.php

Aquí nos va a interesar la parte común de los algoritmos de
duplicación.

Recordemos el algoritmo de la multiplicación rusa:



Si multiplicamos, por ejemplo, 87 por 456, vamos dividiendo 87 entre
dos de forma entera, sin decimales, hasta llegar al 0. Simultáneamente
duplicamos el otro factor 456 cada vez que dividamos el otro. Después

4





sumamos los múltiplos de este número que se correspondan con los
cocientes impares del otro, en el ejemplo

456+912+1824+7296+29184=39672

que coincide con el producto de 87*456.

Esto funciona porque los cocientes impares producen un 1 en la
representación binaria de 87 y los pares un cero, por lo que tiene
sentido sumar sólo los primeros, y como estamos duplicando en cada
proceso, lo que hemos conseguido es lo siguiente:

87*456=(1+2+4+16+64)*456=456+912+1824+7296+29184=39672

En forma de algoritmo podría expresarse así:

Public Function rusa(a,b)
Dim s

s = 0 ‘Se inicia la suma a cero
While a > 0 ‘Mientras a no llegue a cero, se divide entre 2
If (a / 2) <> Int(a / 2) Then s = s + b ‘Si es impar se suma
b = 2 * b ‘Se duplica b
a = Int(a / 2) ‘ Se divide a
Wend
rusa = s ‘ La función recoge el valor de s
End Function

Si copias este listado, lo puedes trasladar al módulo Basic de una hoja
de cálculo para comprobarlo. Los parámetros a y b son los factores.

Podíamos intentar un proceso similar con la potenciación. Por ejemplo,
para calcular 713 podríamos proceder así:



En lugar de duplicar, elevamos al cuadrado, y al final multiplicamos en
vez de sumar.

5



1377649324012401157648015764801968890104077^13=96889010407

Para el conjunto Z la potenciación desemboca pronto en números
grandes, pero no así en Zm, pues los resultados siempre tendrán como
cota m y este método puede ser muy útil. Incluso se puede intentar
mentalmente. Por ejemplo, calcular 763 (mod 5): 72 (mod 5); 724
(mod 5); 741 (mod 5); 781 (mod 5) y ya todos valen 1, luego

763=732+16+8+4+2+12*4*1*1*1*183, luego 7633 (mod 5)

El algoritmo de la multiplicación rusa se puede adaptar fácilmente a
esta exponenciación

Public Function expo(a, e, m) ‘Los parámetros son base, exponente y
módulo
Dim p

p = 1 ‘inicia el producto final
While e > 0
If (e / 2) <> Int(e / 2) Then p = p * a: p = p - m * Int(p / m) ‘si es impar
multiplica y reduce a resto módulo m
a = a ^ 2: a = a - Int(a / m) * m ‘se eleva al cuadrado reduciendo a
módulo m
e = Int(e / 2) ‘se divide el exponente
Wend
expo = p
End Function


la exponenciación modular o binaria, que

Esta sería
resulta
imprescindible en cálculos con grandes números, porque sólo utiliza un
número de multiplicaciones del orden del logaritmo de n, y no de n
como el algoritmo clásico.

No resisto incluir la versión recursiva que aparece en Wikipedia (para
Z)

Si has leído nuestra entrada



6



http://hojaynumeros.blogspot.com.es/2012/03/funciones-recursivas-en-las-hojas-
de.html

sabrás que, con limitaciones, el Basic de las hojas admite recursividad.
En efecto, hemos probado esta definición para módulo m y funciona:

Public Function expo2(a, e, m)
Dim ep

If e = 1 Then
ep = a ‘Definición de parada de la recursión
ElseIf e = Int(e / 2) * 2 Then ‘Caso par
ep = (expo2(a, e / 2, m)) ^ 2: ep = ep - m * Int(ep / m) ‘Elevación al
cuadrado
Else
ep = a * expo2(a, e - 1, m): ep = ep - m * Int(ep / m) ‘Caso impar
End If
expo2 = ep
End Function


¿ Q U É H A Y D E T R ÁS D E
P E R I Ó D I C O S ?


L O S D E C I M A L E S

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. Al reiterar el proceso,
cuando este se repita, ya hay periodo. Lo desarrollamos.

7





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*q1+r1, donde q1 es el primer decimal y r1
el siguiente resto. Si unimos ambas relaciones se obtendrá

D*10=(10*Q+q1)*d+r1

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*102=(102*Q+10*q1+q2)*d+r2

D*103=(103*Q+102*q1+10*q2+q3)*d+r3

Y así seguiríamos hasta un resto cero o una repetición de valores que
diera lugar a un periodo.

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 convertirá en periódico con un periodo inferior
o igual a d-1.

¿Qué hay detrás de estos hechos? Pues 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/congr