Estructuras Discretas Unidad 3 Teoría de números

1. Divisibilidad,

Contenido

• Números primos • Teorema fundamental de la aritmética.

2. Algoritmo de la división • •

Máximo común divisor y mínimo común múltiplo, Algoritmo de Euclides.

3. Congruencias. 4. Aplicaciones: criptografía (Diffie-Hellman, RSA), generación de números pseudoaleatorios.

Introducción • La teoría de números es una rama de las matemáticas que se ocupa de los números enteros. • Nace con los problemas de la divisibilidad de números naturales, siendo los griegos los primeros que llegan a obtener proposiciones generales de la misma, especialmente en los libros VII y IX de Euclides. • Gauss se le considera como el creador de esta.

Divisibilidad • Definición: • Si a ≠ 0, b son enteros, se dice que a divide a b si existe un entero c tal que ac=b (o a|b , o diremos que b es múltiplo de a).

a|b

c Z tal que a c b

• a es divisor de b, a divide a b, a es factor de b. • Si a no divide a b, se escribe: a | b • Ejemplo: . • 20 = 4 5 , es decir, 4 | 20. También, -4|20 así 20=(4)(-5).

• La relación de divisibilidad es reflexiva y transitiva, pero no es simétrica ni antisimétrica.

Teorema 1. a | b

a | kb, k Z

2. a | b b | a 3. a | b b | c

a

b

a|c

4. c | a c | b

c | (am nb), a, b, c, m, n Z

5. k Z {0}, a | b 6. a | b

b 0

ka | kb.

1 | a| |b|

Demostración 1. Existe u Z tal que au=b. Entonces, a(uk)=bk y así a|bk. 2. Observe que por definición, ni a≠0 ni b≠0 si a|b y b|a. Existen enteros, u, u’ con au=b y bu’=a. Así auu’=bu’=a, y asi uu’=1. De esto, u, u’ son enteros, entonces u= 1, u’=  1. Por lo tanto, a= b.

3. Existen enteros u, v con au=b, bv=c. Por lo tanto auv=c, y así a|c. 4. Existen enteros s, t con sc=a, tc=b. Entonces am+nb=c(sm+tn), dando c|(am+bn). 5. Existe un entero u con au=b. Entonces (ak)u=kb, y así a|b entonces ka|kb. Ya que k≠ 0 anulamos las k’s y por lo tanto (ak)u=kb entonces au=b entonces a|b, probando lo contrario. 6. Ya que b≠0 existe un entero u≠0 con au=b. Así |u|≥ 1 y entonces |a|.1 ≤|a|.|u|=|au|=|b|.|a|≥1

Números primos • Definición • Un número entero p Z se dice que es primo si y sólo si p ≠0, 1 y sus únicos divisores son el 1 y p. • Un número entero es compuesto si no es primo. • Si p es primo entonces –p es primo.

•

Para determinar si un entero positivo n es compuesto, es suficiente con probar si alguno de los enteros • 2,3,…, n-1

• •

Dividen a n. Si algún entero en esta lista divide a n, entonces n es compuesto; de lo contrario es primo. Ejemplo: Por inspección, se encuentra que ningún elemento de la lista 2,3,4,5,…, 41, 42

• •

Divide a 43; entonces 43 es primo. Para 451, se encuentra que 11 divide a 451 (451=11*41), así 451 es compuesto. Para determinar si un entero n >1 es primo, se verifican los divisores potenciales: 2,3,…, n-1

•

En realidad es suficiente con verificar: 2,3,…, (n-1)1/2

Teorema fundamental de la aritmética • Supongamos que existe un algoritmo que obtiene los factores primos de un numero compuesto: • Ejemplo: 1274 1274= 2*637 637=7*91 91=7*13 • Entonces 1274 = 2*7*7*13= 2*72*13 • De hecho, los factores primos son únicos. Este resultado se conoce como teorema fundamental de la aritmética o teorema de factorización

única.

Teorema fundamental de la aritmética • Todo número entero distinto de +1,-1 y 0 admite una descomposición única como producto de números primos positivos, es decir:

Ejercicio • Encuentre la descomposición prima de: • 9, 47, 209, 637 • 30, 105, 82320 • 950796, 2311, 1007

• ¿Cuales son primos?

Máximo común divisor • El máximo común divisor de dos enteros m y n (≠ 0) es el entero positivo más grande que divide a los dos: m y n. • Ejemplo: • Máximo común divisor de: 4 y 6 es 2. • Máximo común divisor de: 3 y 8 es 1.

Máximo común divisor Definición • Sean m y n enteros distintos de cero. Un divisor común de m y n es un entero que divide tanto a m como a n. El máximo común divisor, escrito mcd(m,n) • Es el divisor común de m y n más grande.

• Ejemplo: • • • •

Divisores de 30: 1, 2, 3, 5, 6, 10, 15, 30 Divisores de 105: 1, 3, 5, 7,15, 21, 35, 105 Divisores comunes de 30 y 105: 1, 3, 5, 15 Entonces mcd(30, 105)=15

• Ejemplo: • Utilizando sus factorizaciones primas: • 30= 2*3*5 • 105=3*5*7 • De esto observamos que 3 es un divisor común y 5 también es un divisor común y además 3*5=15 es un divisor común. Entonces 15 es el máximo común divisor de 30 y 105.

Teorema 8 • Sean m y n enteros, m >1, n>1, con factorizaciones primas: a a a

m

• y

n

p1 1 p2 2 ... pn n

p1b1 p2b2 ... pnbn

• Si el primo pi no es un factor de m o de n, ai=0 o bi=0 respectivamente. Entonces • mcd (m, n) p mín( a1 ,b1 ) p mín( a2 ,b2 ) ... p mín( an ,bn ) 1

2

n

• Ejemplo: • 82320=24*31*51*73*110 • 950796=22*32*50*74*111 Entonces • mcd(82320,950796)=2min(4,2)*3min(1,2)*5min( 1,0)*7min(3,4)*11min(0,1) • mcd(82320,950796)=22*31*50*73*110 =4116

Ejercicio • Encuentre: • • • •

mcd(0,17) mcd(110,273) mcd(20, 40) Mcd(331,993)

Algoritmo de Euclides • Si dividimos el entero no negativo a entre el entero positivo b, obtenemos un cociente q y un residuo r que satisface: a=bq+r, 0 ≤ r< b, q ≥ 0

• Ejemplo: • a=22, b=7, q=3, r=1; 22=7*3+1 • a=24, b=8, q=3, r=0; 24=8*3+0

Teorema 9 • Si a es un entero no negativo, b es un entero positivo y a=bq+r, 0 ≤ r< b, Entonces

mcd(a,b)=mcd(b,r)

• Dem: Sea c un divisor común de a y b. Entonces c|bq. Como c|a y c|bq, entonces c|a-bq(=r). Así, c es un divisor común de b y r. • Recíprocamente: si c es un divisor común de b y r, entonces c | bq y c|bq+r(=a) y c es un divisor común de a y b. Esto implica que mcd(a,b)=mcd(b,r)

• Ejemplo: Si dividimos 105 entre 30, obtenemos: • 105=30*3+15 • Por el teorema 9: • mcd(105,30)=mcd(30,15)

• Si dividimos 30 entre 15, obtenemos • 30= 15*2+0 • El residuo es 0. Por el teorema anterior: Mcd(30,15)=mcd(15,0)

• Por inspección, mcd(15,0)=15. Por tanto, • mcd(105,30)=mcd(30,15)=mcd(15,0)=15 • Este cálculo lo ilustra el algoritmo de Euclides

Ejercicios • Determine enteros q y r tales que a=bq+r, con 0≤r1, n>1, con factorizaciones primas m

p1a1 p2a2 ... pnan

n p p ... p •Y • (Si el primo pi no es un factor de m, se deja ai=0. Igual para n). Entonces b1 1

mcm(m, n)

máx ( a1 ,b1 ) 1

p

bn n

b2 2

máx ( a2 ,b2 ) 2

p

máx ( an ,bn ) n

... p

Mínimo común múltiplo • Ejemplo • 82320=24*31*51*73*110 • 950796=22*32*50*74*111 Entonces • mcm(82320,950796)=2máx(4,2)*3máx(1,2)*5má x(1,0)*7máx(3,4)*11máx(0,1) • mcm(82320,950796)=24*32*51*74*111 =19015920

Mínimo común múltiplo • Ejemplo: • mcd(30,105)=15 • mcm(30,105)=210

• mcd(30,105)*mcm(30,105)=15*210=3150 =30*105

Teorema 11 • Para cualesquiera enteros positivos m y n, mcd(m,n)*mcm(m,n)=mn • Dem: • Si m=1, entonces mcd(m,n)=1 y mcm(m,n)=n, así: • mcd(m,n)*mcm(m,n)=1*n=mn • Si n=1, entonces mcd(m,n)=1 y mcm(m,n)=m, así: • mcd(m,n)*mcm(m,n)=1*m=mn

• Si m > 1 y n >1 • Combinando los teoremas anteriores de mcd y mcm, con el hecho de que: • mín(x,y) + máx(x,y)=x + y para toda x y y. • Esto es verdadero porque uno de {mín(x,y), máx(x,y)} es igual a x y el otro a y.

•

Se escriben las factorizaciones primas de m y n como an b1 b2 a1 a2 1 2 1 2 n

m

•

p p ... p

•

p p ... pnbn

(si el primo pi no es un factor de mi, se hace ai=0. Si el primo pi no es un factor de n, se hace bi=0). Por el teorema 9

mcd (m, n) •

n

p1mín( a1 ,b1 ) p2mín( a2 ,b2 ) ... pnmín( an ,bn )

Y por el teorema 10

mcm(m, n)

Por lo tanto,

p1máx ( a1 ,b1 ) p2máx ( a2 ,b2 ) ... pnmáx ( an ,bn )

mcd(m, n) * mcm(m, n) [ p1mín ( a1 ,b1 ) p2mín ( a2 ,b2 ) ... pnmín ( an ,bn ) ] [ p1máx ( a1 ,b1 ) p2máx ( a2 ,b2 ) ... pnmáx ( an ,bn ) ] p1mín ( a1 ,b1 )

máx ( a1 ,b1 )

p1a1 b1 ... pnan

... pnmín ( an ,bn )

bn

[ p1a1 ... pnan ][ p1b1 ... pnbn ] mn

máx ( an ,bn )

Ejercicios • Determinar el mcm de cada par de números • • • •

60, 90 220, 1400 2091, 4807 110, 273

• Para cada ejercicio verifique que mcd(m,n)*mcm(m,n)=mn

Teorema 12: El algoritmo de la división • Teorema: • Si a, b son enteros con b>0 entonces existen q, r enteros únicos, con a=qb+r, 0≤r1. Para a,b enteros, se dice que a es congruente con b módulo n y se escribe a b(mod n), si • n|(a-b) o a=b+kn, k un entero.

• Ejemplo: • 17 2(mod 5), 5|(17-2), 17=2+3*5, k=3 • -7 -49(mod 6), 6|(-7+49)

• A es congruente con b módulo m, (a m b), si m|a-b • Ejemplo: • 25 7 32, • 32=4+7*4 • 25=4+7*3 • 32-25=7*(4-3)

• Ejemplo • 17

3

-28

• -28=2+3*(-10) • 17=2+3*5 • -28-17=3*(-10-5)

• Obtenemos que 32-25 es múltiplo de 7 y -28-17 es múltiplo de 3, al coincidir los valores de los restos, 4 y 2 respectivamente

• Teorema • Sean a,b enteros, m>0: a a mod m = b mod m. • Demostración

m

b

• Demostración • Dados a, b, m enteros m>0 existen c,r,c’,r’ únicos tales que a=cm+r, 0≤r0, al conjunto de clases de congruencia de Z módulo m lo designamos Z(m)={0,1,... , m 1 }

Ejemplo