Teoría elemental de números Matemática discreta

Matemática discreta. Teoría elemental de números

1

Resultados previos • Axioma: todo subconjunto no vacío de N tiene mínimo, con el orden usual en N. • Toda sucesión decreciente en N converge.

Matemática discreta. Teoría elemental de números

2

Divisibilidad

Divisibilidad • Si a,b∈Z, a divide a b , a⎥ b, si ∃c∈Z tal que b=a·c. Se dice también que b es múltiplo de a o que a es divisor de b. En caso contrario, a∤b, a no divide a b.

Matemática discreta. Teoría elemental de números

3

Divisibilidad

Propiedades de divisibilidad ∀a, b, c ∈Z • 1⎥ a a⎥ a a⎥ 0 • Si a⎥ b y b⎥ a, entonces a=± b • a⎥ b, entonces a⎥ b·c • a⎥ b y a⎥ c, entonces a⎥ bx+cy ∀x,y ∈Z • Si x=y+z, a⎥ x, a⎥ y, entonces a⎥ z ∀x,y,z ∈Z

Matemática discreta. Teoría elemental de números

4

Divisibilidad

División euclídea Dados a,b∈Z siendo b≠0, existen únicos q,r∈Z tales que a=b·q+r, con 0≤ r1, p es primo si ∀n∈N n⎥ p ⇒ n=p ó n=1 • Todo natural mayor que 1 es divisible por, al menos, un número primo.

Matemática discreta. Teoría elemental de números

6

Números primos

Teorema fundamental de la aritmética • ∀n∈N, n>1, existen únicos p1, .., pr∈N y existen únicos α1, .., αr∈N* tales que n= p1α1...prαr Todo natural se descompone de manera única como producto de potencias de números primos. Matemática discreta. Teoría elemental de números

7

Números primos

Máximo común divisor Dados a,b∈Z no simultáneamente nulos. • d es divisor común de a y b si d⎥ a y d⎥ b. • El máximo común divisor de a y b, mcd(a,b), es el mayor de los divisores comunes de a y b. • a y b son primos relativos si mcd(a,b)=1. • Si b≠0 y r es el resto de la división euclídea entre a y b, entonces: – Los divisores comunes de a y b son divisores de r. – Los divisores comunes de b y r son divisores de a. Matemática discreta. Teoría elemental de números

8

Números primos

Algoritmo de Euclides • Dados a,b∈Z* y r el resto de la división euclídea entre a y b, entonces mcd(a,b) = mcd(b,r) • Nos proporciona un algoritmo para calcular el mcd utilizando la división euclídea. • mcd(a,b) = mcd(⏐a⏐,⏐b⏐)

Matemática discreta. Teoría elemental de números

9

Números primos

Algoritmo de Euclides 2 • Sean a,b∈Z+ con a≥b>0, llamamos r0=a y r1=b. Aplicamos sucesivas veces la división euclídea: r0=q1·r1+ r2. r1=q2·r2+ r3.

0< r2< r1 0< r3< r2 ................

rn-2=qn-1·rn-1+ rn rn-1=qn·rn+ rn+1

0< rn< rn-1 rn+1=0

Entonces, el mcd(a,b)=rn Matemática discreta. Teoría elemental de números

10

Números primos

ejemplo • mcd(6,9)=3 9=6·1+3 6=3·2+0 El último resto distinto de 0 es 3, el mcd. • mcd(24,62)=2 62=24·2+14 24=14·1+10 14=10·1+4 10=4·2+2 4=2·2+0 El último resto distinto de 0 es 2, el mcd. Matemática discreta. Teoría elemental de números

11

Números primos

Teorema de Bezout Dados a,b∈N* y mcd(a,b)=d, entonces ∃x,y∈Z tales que d=ax+by Identidad de Bezout mcd(a,b)=1 ⇔ ∃x,y∈Z tales que 1=ax+by • Dados a,b∈Z se verifica – Si p⎥ a·b y p es primo, entonces p⎥ a ó p⎥ b. – Si p⎥ a·b y mcd(a,p)=1, entonces p⎥ b. Matemática discreta. Teoría elemental de números

12

Ecuaciones diofánticas

Ecuaciones diofánticas • Buscamos soluciones enteras de una ecuación. • Ecuación diofántica lineal en dos variables ax+by=c a, b, c ∈Z • Diofanto, s. III a.C.

Matemática discreta. Teoría elemental de números

13

Ecuaciones diofánticas

Ecuaciones diofánticas 2 • Dados a,b,c∈Z, mcd(a,b)=d, y dada la ecuación ax+by=c – Si d∤c la ecuación no tiene soluciones enteras. – Si d⎥ c la ecuación tiene infinitas soluciones enteras. A partir de una solución particular (x0,y0) calculamos el resto de las soluciones x= x0+(b/d)·n

n ∈Z

y=y0-(a/d)·n Matemática discreta. Teoría elemental de números

14

Ecuaciones diofánticas

Ecuaciones diofánticas 3 • Para calcular una solución particular: – dividimos ax+by=c por mcd(a,b)=d y obtenemos a´x+b´y=c´ – como mcd(a´,b´)=1, por la identidad de Bezout a´x+b´y=1 tiene solución. – Encontramos la solución (x1,y1) de a´x+b´y=1 por el algoritmos de Euclides. – Una solución particular es (c´x1,cý1).

Matemática discreta. Teoría elemental de números

15

Ecuaciones diofánticas

ejemplo (1) 6x+4y=10. Como mcd(6,4)=2⎥10, dividimos la ecuación por 2 (2) 3x+2y=5. Como mcd(3,2)=1, la ecuación (3) 3x+2y=1 tiene solución (identidad de Bezout). 3=2·1+1, luego (1,-1) es solución de (3) y (5,-5) es solución particular de (2) x= 5+(4/2)·n=5+2·n n ∈Z y=-5-(6/2)·n=-5-3n Matemática discreta. Teoría elemental de números

16

Aritmética modular

Aritmética modular Dado m ∈N • a es congruente con b módulo m, a≡b (mod m), si m⎥ b-a, es decir, ∃q∈Z tal que b=a+qm. • a≡b (mod m) ⇔ ∃qa,qb∈Z y ∃r∈Z que verifican a= qam+r b= qbm+r • ∀z∈Z, z es congruente módulo m forzosamente con un elemento del conjunto {0, 1, ..., m-1}. Matemática discreta. Teoría elemental de números

17

Aritmética modular

Clases de equivalencia • La relación ≡ (mod m) es de equivalencia. – Reflexiva a≡a (mod m) – Simétrica a≡b (mod m) ⇒ b≡a (mod m) – Transitiva a≡b (mod m) y b≡c (mod m) ⇒ a≡c (mod m)

• Dado k∈Z, se define la clase de equivalencia de k como [k]=⎯k={x ∈Z / x ≡k (mod m) }. ejemplo: ≡ (mod 3) [0]=⎯0={0,3,6,9,12,...,-3,-6,-9,-12,...}. [1]=⎯1={1,4,7,10,...,-2,-5,-8,-11...}. [2]=⎯2={2,5,8,11,...,-1,-4,-7,-10,...}. Matemática discreta. Teoría elemental de números

18

Aritmética modular

Conjunto cociente • Z/≡ (mod m)={⎯k/ k∈Z}. • ≡ (mod m) define en Z una partición llamada Zm que está formada por m clases de equivalencia Zm={⎯0,⎯1,...,⎯m-1}. ejemplo: En Z, ≡ (mod 3) induce la partición Z3={⎯0,⎯1,⎯2}

Matemática discreta. Teoría elemental de números

19

Aritmética modular

Propiedades a,b,c,d ∈ Z, m∈N* • Si en Zm [a]=[b] y [c]=[d], entonces la clase de la suma y el producto es independiente del representante que elijamos de cada clase. – [a+c]=[b+d] – [a·c]=[b·d]

• Propiedad cancelativa: si en Zm [a·c]=[b·c] y mcd(m,c)=1, entonces [a]=[b] Matemática discreta. Teoría elemental de números

20

Aritmética modular

Aritmética en Zn • Suma de clases ⊕: ZnxZn →Zn:[a] ⊕ [b]=[a+b] Cumple las propiedades: – – – –

Asociativa: [a] ⊕ ([b]⊕[c]) = ([a]⊕[b]) ⊕ [c] Conmutativa: [a]⊕[b] = [b]⊕[a] Elemento neutro: [0]⊕[a]=[a]⊕[0]=[a] Elemento opuesto: -[a]⊕[a]=[a]⊕(-[a])=[0]

Matemática discreta. Teoría elemental de números

21

Aritmética modular

ejemplo 1 Tabla de la suma de clases en Z4 ⊕

[0]

[1]

[2]

[3]

[0]

[0]

[1]

[2]

[3]

[1]

[1]

[2]

[3]

[0]

[2]

[2]

[3]

[0]

[1]

[3]

[3]

[0]

[1]

[2]

Matemática discreta. Teoría elemental de números

22

Aritmética modular

ejemplo 2 En Z7 • -[2]=[-2]=[5] -2-5=-7 • [5] ⊕ (-[10])=[5]⊕[-10]=[5]⊕[4]=[9]=[2] -10= -2·7+4,-10-4 ∈7· [5] ⊕ (-[10])=[5-10]=[-5]=[2] -5= -1·7+2, -5-2 ∈7· • 3·[5]=[5]⊕[5]⊕[5]=[3·5]=[15]=[1] • -3·[5]=-[5]⊕(-[5])⊕(-[5])=[-3·5]=[-15]=[6] Matemática discreta. Teoría elemental de números

23

Aritmética modular

Aritmética en Zn • Producto de clases +: ZnxZn →Zn:[a] + [b]=[a·b] Cumple las propiedades: – Asociativa: [a] + ([b]+[c]) = ([a]+[b]) + [c] – Conmutativa: [a]+[b] = [b]+[a] – Elemento neutro: [1]+[a]=[a]+[1]=[a] – Elemento inverso: si mcd(a,n)=1 [a]-1+[a]=[a]+[a]-1=[1] (si n es primo, existe el inverso ∀[a]∈ Zn) Matemática discreta. Teoría elemental de números

24

Aritmética modular

ejemplo 1 Tabla del producto de clases en Z4 +

[0]

[1]

[2]

[3]

[0]

[0]

[0]

[0]

[0]

[1]

[0]

[1]

[2]

[3]

[2]

[0]

[2]

[0]

[2]

[3]

[0]

[3]

[2]

[1]

Matemática discreta. Teoría elemental de números

25

Aritmética modular

ejemplo 2 En Z7 • como mcd(7,2)=1, por la identidad de Bezout ∃ α,β∈Z / α·2+β·7=1, por tanto [α·2+β·7]=[1] ⇒[α·2] ⊕ [β·7]=[1] ⇒ ⇒[α·2] ⊕ [0]=[1] ⇒ [α] + [2] =[1] ⇒ ⇒[2]-1 =[α] Para que se cumpla α·2+β·7=1 basta tomar α=4 y β=-1, luego [2]-1=[4]. Efectivamente, [2]+[4]=[8]=[1] Matemática discreta. Teoría elemental de números

26

Aritmética modular

ejemplo 3 En Z6. Como mcd(6,2)≠1, ∃ [2]-1, es decir, ∃ α tal que [2]+[α]=[1]. Efectivamente, basta observar la tabla del producto de clases en Z6 + [1] [2] [3] [4] [5]

[1] [1] [2] [3] [4] [5]

Matemática discreta. Teoría elemental de números

[2] [2] [4] [0] [2] [4]

[3] [3] [0] [3] [0] [3]

[4] [4] [2] [0] [4] [2]

[5] [5] [4] [3] [2] [1] 27

Aritmética modular

Propiedad distributiva del producto respecto de la suma de clases ∀n ∈N* y ∀ [a],[b],[c] ∈Zn [a] + ([b] ⊕ [c]) = ([a] + [b]) ⊕ ([a] + [c])

Matemática discreta. Teoría elemental de números

28

Aritmética modular

Ecuaciones modulares Dados a,b∈Z, en Zn si mcd(a,n)=d la ecuación [a]·[x]=[b] – no tiene solución si d∤b – tiene d soluciones en Zn si d⎥ b

• [a]·[x]=[a·x]=[b] existe ⇔ a·x-b es múltiplo de n, es decir, si ∃ k∈Z / ax-b=kn. La ecuación ax+kn=b tiene solución ⇔ mcd(a,n)⎥ b. Entonces, si x0 es solución particular de ax+kn=b, las soluciones en Zn vienen dadas por [x0], [x0+n/d], [x0+2·n/d], ..., [x0+(d-1)·n/d].

Matemática discreta. Teoría elemental de números

29

Aritmética modular

ejemplo Las soluciones de [5]·[x]=[6] son: En Z4: como [5]=[1] y [6]=[2] tenemos [1]·[x]=[2] como mcd(1,4)=1 y 1⎥ 2, hay una única solución. Consideramos la ecuación 1·x+4·k=1 que tiene solución particular x=5 y k=-1, por tanto una solución particular de 1·x +4·k=2 es x=10. Como [10]=[2], la única solución es [2]. En Z10: como mcd(5,10)=5 y 5∤6, no hay solución.

Matemática discreta. Teoría elemental de números

30

Aritmética modular

ejemplo Las soluciones de [5]·[x]=[6] son: En Z4: como [5]=[1] y [6]=[2] tenemos [1]·[x]=[2] como mcd(1,4)=1 y 1⎥ 2, hay una única solución. Consideramos la ecuación 1·x+4·k=1 que tiene solución particular x=5 y k=-1, por tanto una solución particular de 1·x +4·k=2 es x=10. Como [10]=[2], la única solución es [2]. En Z10: como mcd(5,10)=5 y 5∤6, no hay solución.

Matemática discreta. Teoría elemental de números

31

Diofanto de Alejandría • “Dios le concedió el ser un muchacho durante una sexta parte de su vida, y añadiendo a esto una doceava parte, El pobló de vello sus mejillas; Le iluminó con la luz del matrimonio después de una séptima parte, y cinco años después de su matrimonio Le concedió un hijo. Pero ¡ay! Infeliz niño nacido tarde; después de alcanzar la mitad de la medida de la vida de su padre, el frío destino se lo llevó. Después de consolar sus penas con la ciencia de los números durante cuatro años más, finalizó su vida”. Matemática discreta. Teoría elemental de números

32