Álgebra y matemática discreta sesión de teoría 4

Algebra y Matematica Discreta Sesion de Teorıa 4

Algebra y Matematica Discreta

Sesion de Teorıa 4

(c) 2013 Leandro Marın, Francisco J. Vera, Gema M. Dıaz

23 Sep 2013 - 29 Sep 2013


Aritmetica

Unidades de Zn y la Funcion ϕ

Unidades

Un elemento a de Zn diremos que es una unidad cuandopodamos encontrar b en Zn tal que ab ≡ 1(n), o lo que es lomismo, ab = 1 en Zn.


Aritmetica


Unidades


Ejemplos de elementos que siempre son unidad son 1 y n − 1porque (n − 1)2 = 1 + n(n − 2) ≡ 1(n).


Aritmetica


Unidades



El Conjunto de unidades de Zn se denotara Z⋆n.


Aritmetica


Unidades



El Conjunto de unidades de Zn se denotara Z⋆n.

El numero de elementos de este conjunto se denotara ϕ(n) yse llama funcion ϕ de Euler.


Aritmetica


Unidades de Z15

· 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

2 0 2 4 6 8 10 12 14 1 3 5 7 9 11 13

3 0 3 6 9 12 0 3 6 9 12 0 3 6 9 12

4 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11

5 0 5 10 0 5 10 0 5 10 0 5 10 0 5 10

6 0 6 12 3 9 0 6 12 3 9 0 6 12 3 9

7 0 7 14 6 13 5 12 4 11 3 10 2 9 1 8

8 0 8 1 9 2 10 3 11 4 12 5 13 6 14 7

9 0 9 3 12 6 0 9 3 12 6 0 9 3 12 6

10 0 10 5 0 10 5 0 10 5 0 10 5 0 10 5

11 0 11 7 3 14 10 6 2 13 9 5 1 12 8 4

12 0 12 9 6 3 0 12 9 6 3 0 12 9 6 3

13 0 13 11 9 7 5 3 1 14 12 10 8 6 4 2

14 0 14 13 12 11 10 9 8 7 6 5 4 3 2 1


Aritmetica


Comentarios

Del ejemplo anterior podemos extraer algunas consecuencias.


Aritmetica


Comentarios


El producto de unidades es una unidad.


Aritmetica


Comentarios



Si un elemento es una unidad, su inverso (es decir, el quemultiplicado por el nos da 1), tambien es una unidad.


Aritmetica


Comentarios



Si un elemento es una unidad, su inverso (es decir, el quemultiplicado por el nos da 1), tambien es una unidad.

En el caso anterior, si contamos las unidades vemos que salen8.


Aritmetica


El conjunto Z⋆

15

· 1 2 4 7 8 11 13 14

1 1 2 4 7 8 11 13 14

2 2 4 8 14 1 7 11 13

4 4 8 1 13 2 14 7 11

7 7 14 13 4 11 2 1 8

8 8 1 2 11 4 13 14 7

11 11 7 14 2 13 1 8 4

13 13 11 7 1 14 8 4 2

14 14 13 11 8 7 4 2 1


Aritmetica


Caracterizacion de las Unidades

Un elemento a de Zn es una unidad si y solo si a y n soncoprimos.


Aritmetica




De hecho, la ecuacion ab + nt = 1 nos proporciona el inversode a, que es b.


Aritmetica





Es decir, que de nuevo el algoritmo de Euclides extendido nosda la solucion a problema.


Aritmetica





Es decir, que de nuevo el algoritmo de Euclides extendido nosda la solucion a problema.

Este resultado nos permite calcular el valor de la funcion ϕ enel caso de que p sea primo, puesto que todos los elementosentre 1 y p − 1 son coprimos con p, eso significa queϕ(p) = p − 1 si p es primo.


Aritmetica


Formula General de ϕ

La funcion ϕ tiene interesantes propiedades. Una de ellas esque si a y b son numeros coprimos, entoncesϕ(ab) = ϕ(a)ϕ(b).


Aritmetica



La funcion ϕ tiene interesantes propiedades. Una de ellas esque si a y b son numeros coprimos, entoncesϕ(ab) = ϕ(a)ϕ(b).Eso aplicado al numero 15 nos dice queϕ(15) = ϕ(3 · 5) = ϕ(3)ϕ(5) = (3− 1)(5− 1) = 8.


Aritmetica



La funcion ϕ tiene interesantes propiedades. Una de ellas esque si a y b son numeros coprimos, entoncesϕ(ab) = ϕ(a)ϕ(b).Eso aplicado al numero 15 nos dice queϕ(15) = ϕ(3 · 5) = ϕ(3)ϕ(5) = (3− 1)(5− 1) = 8.Ese es el valor que precisamente nos salıa experimentalmente.


Aritmetica



La funcion ϕ tiene interesantes propiedades. Una de ellas esque si a y b son numeros coprimos, entoncesϕ(ab) = ϕ(a)ϕ(b).Eso aplicado al numero 15 nos dice queϕ(15) = ϕ(3 · 5) = ϕ(3)ϕ(5) = (3− 1)(5− 1) = 8.Ese es el valor que precisamente nos salıa experimentalmente.Para las potencias de los primos se tiene queϕ(pα) = pα−1(p − 1).


Aritmetica



La funcion ϕ tiene interesantes propiedades. Una de ellas esque si a y b son numeros coprimos, entoncesϕ(ab) = ϕ(a)ϕ(b).Eso aplicado al numero 15 nos dice queϕ(15) = ϕ(3 · 5) = ϕ(3)ϕ(5) = (3− 1)(5− 1) = 8.Ese es el valor que precisamente nos salıa experimentalmente.Para las potencias de los primos se tiene queϕ(pα) = pα−1(p − 1).Utilizando esto y la propiedad anterior, podemos saber ϕ paracualquier numero, porque si tomamos la factorizacion de n enprimos, tenemos que

ϕ(n) = ϕ(pα11 p

α22 · · · pαt

t ) = ϕ(pα11 )ϕ(pα2

2 ) · · ·ϕ(pαt

t )

y aquı aplicamos la formula para las potencias de primos.


Aritmetica


Divisores de Cero y Unidades

Los divisores de cero y las unidades estan muy relacionados.


Aritmetica




Se puede demostrar que un elemento no nulo es divisor decero si y solo si no es una unidad.


Aritmetica




Se puede demostrar que un elemento no nulo es divisor decero si y solo si no es una unidad.

Es decir, que los divisores de cero son todos los elementos queno estan en Z

⋆n, excepto el propio 0 que no se considera

divisor de 0.


Aritmetica

Exponenciacion Modular

Planteamiento

A veces es necesario calcular potencias de numeros enaritmetica modular con exponentes muy grandes.


Aritmetica


Planteamiento


Si tenemos que calcular be(n), una forma de hacerlo escalcular el numero entero be y luego hacer la reduccionmodulo n.


Aritmetica


Planteamiento



Esta forma es totalmente inviable si e es un numero grande,puesto que be puede ser un numero enormemente grande.


Aritmetica


Planteamiento



Esta forma es totalmente inviable si e es un numero grande,puesto que be puede ser un numero enormemente grande.

El problema se puede resolver de una forma mucho massencilla.


Aritmetica


Resolucion del Problema

Lo primero que tenemos que darnos cuenta es que hay potencias que son

sencillas de calcular, concretamente las de la forma b2i (n).


Aritmetica





Para calcularlas empezamos por i = 0, es decir b20 = b1 = b.


Aritmetica






Si la tenemos calculada hasta el valor i , entonces el valor i + 1 se calculaelevando al cuadrado la anterior (y haciendo la reduccion modulo n

correspondiente) porque(

b2i)2

= b2ib2i = b

2i+2i = b2i+1

.


Aritmetica








b2i)2

= b2ib2i = b

2i+2i = b2i+1

.

Una vez que tenemos calculadas modulo n estas potencias, utilizamos larepresentacion binaria de e = e0 + e1 · 2 + ...+ et2

t y deducimos que

be = b

e0+e1·2+...+et2t

= be0· (b2)e1 · · ·

(

b2t)et

(n)


Aritmetica








b2i)2

= b2ib2i = b

2i+2i = b2i+1

.

Una vez que tenemos calculadas modulo n estas potencias, utilizamos larepresentacion binaria de e = e0 + e1 · 2 + ...+ et2

t y deducimos que

be = b

e0+e1·2+...+et2t

= be0· (b2)e1 · · ·

(

b2t)et

(n)

y esta es una operacion que involucra a lo sumo t multiplicaciones.


Aritmetica


Ejemplo

Sea b = 74, e = 53 y n = 81, vamos a calcular be(n).

e(div) e(bin) b be

acum

53 1 74 74 74

26 0 49 1 74

13 1 52 52 41

6 0 31 1 41

3 1 70 70 35

1 1 40 40 23

La primera columna son las divisiones sucesivas que nos permitenescribir e en binario en la segunda columna. Luego tenemos en lacolumna b las potencias sucesivas b

2i y en la cuarta columna(

b2i)ei

que es el mismo numero si el exponente es 1 o 1 si el exponente es0. La ultima columna nos permite acumular el producto. Elresultado es pues 23.


Aritmetica


Formula de Euler

Formula de Euler

Sea n un numero entero positivo y b una unidad en Z⋆n, entonces

bϕ(n) ≡ 1(n)

Esta propiedad es interesante por varias razones.


Aritmetica


Formula de Euler

Formula de Euler


bϕ(n) ≡ 1(n)


Una de ellas es que nos permite calcular el inverso decualquier numero utilizando el algoritmo de exponenciacionmodular, concretamente bϕ(n)−1b = bϕ(n) = 1 y por lo tantobϕ(n)−1 es el inverso de b modulo n.


Aritmetica


Formula de Euler

Formula de Euler


bϕ(n) ≡ 1(n)


Una de ellas es que nos permite calcular el inverso decualquier numero utilizando el algoritmo de exponenciacionmodular, concretamente bϕ(n)−1b = bϕ(n) = 1 y por lo tantobϕ(n)−1 es el inverso de b modulo n.

Normalmente es mas sencillo el calculo del inverso utilizandoel algoritmo de Euclides extendido, pero esta es otraalternativa que podemos considerar.

Álgebra y matemática discreta sesión de teoría 4

Documents