.

1

TEORIA DE NUMEROS Temas:

DIVISIBILIDAD Y NUMEROS PRIMOS. PRUEBAS DE PRIMALIDAD. LA CRIBA DE ERATOSTENES. ALGORITMOS. TEOREMA: EXISTENCIA DE INFINITOS PRIMOS.

(Apuntes de apoyo a clases teóricas) (Tiempo de exposición 2 hs)

Bibliografía: 2

1. T. Hibbard. Apuntes de Cátedra. Año 2000. 2. J. Yazlle. Apuntes de Cátedra: Aritmética Elemental. U.N.Sa. Marzo 2006. 3. Grimaldi. Addison Wesley (1989), Matemática discreta y combinatoria. 4. Enzo Gentile. Eudeba (1984). Notas de aritmética. 5. Enzo Gentile. SECRETARIA GENERAL DE LA ORGANIZACION DE LOS ESTADOS AMERICANOS . (1985). Aritmética.

Objetivos: 3

1. Conceptualizar la relación “divide” en los números enteros 2. Definir número primo y compuesto. 3. Identificar las propiedades de los nros. Primos. 4. Proponer distintos algoritmos para testear

la primalidad de un número,

mejorando su eficiencia. 5. Proponer métodos que intenten producir solo nros. Primos.

6. Determinar la existencia de infinitos nros. Primos.

Aplicaciones del tema: 4

En Criptografía: los algoritmos de encriptación de mensajes utilizan números primos muy grandes (más de 300 dígitos)

Introducción: 5

¿ Qué les sugiere la siguiente lista de números? : 5,11,17, 23, 31, 61…? Efectivamente: son números primos. Vamos a estudiarlos porque nos interesa contestar las siguientes cuestiones: 1. ¿Cómo decidir si un número es primo? 2. ¿Cuál es el número primo más grande que se conoce? En 2010 el más grande era: 2 43.112.609 – 1, con 13.000.000 de dígitos. En 2014 el más grande es: : 2 57.885.161 – 1, con 17.000.000 de dígitos, descubierto en Febrero de 2013 por matemático estadounidense. 3.¿Habrán infinitos primos? 4. ¿Existirá una fórmula o método que produzca solo nros. Primos?

Introducción: 6

Retomemos el Teorema de la división en los Enteros:  a,b  , b 0,  c, r   / a = b.c + r, con 0  r < | b | Hagamos las siguientes operaciones: 16 / 5 = 3 y resto = 1  16 = 5.3 + 1 16 / 8 = 2 y resto = 0  16 = 8.2 + 0 ¿ 3 es divisor de 16 ? Efectivamente, 3 NO es divisor de 16 ; el resto  0 ¿ 8 es divisor de 16 ? Efectivamente, 8 SI es divisor de 16 ; el resto = 0

Entonces, vamos a proponer una definición para DIVISOR

Relación “divide”: Definición 7

Definición:  a,b  , b 0, decimos que b | a : b “divide a” a b “es factor de” a b “es un divisor de” a

O bien:

a “ es divisible por ” b a “es múltiplo de” b

b | a   k   / a = b.k Es decir, que el resto de dividir a entre b es 0

Relación “divide”: Propiedades 8

Observar que: I) b | 0. ya que  b  , b 0,  k   / 0 = b.k II)  a   - {0}, 0 = 0 . a

Cuánto vale a?

Cuánto vale k? k = 0

a = infinitos valores enteros

III) 1 y (-1) dividen a cualquier entero:  a  , a = k . 1

Cuánto vale k? k = a

 a  , a = k . (-1)

Cuánto vale k? k = -a

IV) Todo entero distinto de 0, es divisible por sí mismo y su opuesto:  a   - {0}, a  0 a=k.a

Cuánto vale k? k = 1

a = k . (-a)

Cuánto vale k? k = -1

V) Como consecuencia de i), ii), iii), iv): Todo numero entero posee “al menos” 4 divisores: 1, (-1), a, (-a)

Divisores Propios e Impropios: 9

Ejemplo: Si a = 4;

Cuáles son sus divisores?

1, (-1), 4, (-4), 2, (-2)

Divisores Divisores impropios propios

Si a = 5;

Cuáles son sus divisores?

1, (-1), 5, (-5)

Divisores impropios

Número Primo y compuesto: Definición 10

p , con | p | >1, es PRIMO si posee “exactamente 4 divisores”

ó p es PRIMO  | p | > 1 y p no tiene divisores propios Si a = 5;

Cuáles son sus divisores?

1, (-1), 5, (-5)

 5 es primo

Divisores impropios Si | a | > 1 y a no es primo  es COMPUESTO Observar: 0 es primo? . 0=0.1 , 0 = 0.2, 0 = 0.3 … 0 tiene infinitos divisores No es primo 0 es compuesto? . | 0 | < 1  No es COMPUESTO 1 es primo? . 2 es primo? . 1 es compuesto? . 2 es compuesto? .

6 es primo? . -3 es primo? . -3 es compuesto? . 6 es compuesto?

PRUEBAS DE PRIMALIDAD: 11

Pensemos en un primer algoritmo para detectar si p N , es PRIMO, contando la cantidad de divisores de p. Versión No recursiva: (Pizarrón) primo(p) = c := 0; Para i := 1 to p do Si (p mod i = 0) luego c := c+1 Fin_Para Si (c = 2) luego Verdadero Sino Falso

Versión recursiva: primo1(p) = si (p = 0) ó (p= 1) luego Falso sino aux(p, 1, 1) donde aux(p, d, c) = si (p = d) luego si c = 2 luego Verdadero sino Falso sino si (p mod d = 0) luego aux(p, d+1, c+1) sino aux(p, d+1, c)

PRUEBAS DE PRIMALIDAD… 12

Ahora, con la sig. Información, pensemos en un segundo algoritmo para detectar si p N , es PRIMO. - p no tiene divisores mayores que él. - Si p posee al menos un divisor, ya no es primo, caso contrario si es primo. primo2(p) = Si (p = 0) o (p=1) luego Falso sino aux(p, 2) donde aux(p, d) = Si (p = d) luego Verdadero sino si (p mod d = 0) luego Falso sino aux(p, d+1) Traza de ejecución p = 29: primo2(29)= aux(29, 2) // ya que 29  0 y 29  1 aux(29, 2) = aux(29, 3) // ya 29 mod 2  0 aux(29, 3) = aux(29, 4) // ya 29 mod 3  0 aux(29, 4) = aux(29, 5) // ya 29 mod 4  0 aux(29, 5) = aux(29,6)… aux(29,7)… aux(29,10)… aux(29, 29)=Verdadero Cantidad de invocaciones peor caso (p es primo) = p-1

PRUEBAS DE PRIMALIDAD… 13

Podemos pensar en un mejoramiento del algoritmo primo2(p), teniendo en cuenta: - Si p es par luego p no es Primo. - Si p es impar, buscar divisores a partir del 3 y probando solo divisores impares. Si se encontró un divisor p no es Primo, caso contrario si lo es. primo3(p) = Si (p = 0) o (p=1) luego Falso sino si (p = 2) luego Verdadero sino si (p mod 2 = 0) luego Falso sino aux(p, 3) donde aux(p, d) = Si (p = d) luego Verdadero sino si (p mod d = 0) luego Falso sino aux(p, d+2) Traza de ejecución p = 29: primo3(29)= aux(29, 3) // ya que 29  0 , 29  1, 29  2 y 29 mod 2  0 aux(29, 3) = aux(29, 5) // ya 29 mod 3  0 aux(29, 5) = aux(29, 7) = aux(29, 9) = aux(29, 11) = aux(29, 13) = aux(29, 15) = aux(29, 17) = … aux(29, 29) = Verdadero Cantidad de invocaciones peor caso (p es primo) = (p-1)/2

PRUEBAS DE PRIMALIDAD… 14

Podemos ahorrar aún más el trabajo buscando divisores solo hasta p/2: - Si p es par luego p no es Primo. - Si p es impar, buscar divisores a partir del 3 y probando solo divisores impares hasta p/2: primo4(p) = Si (p = 0) o (p=1) luego Falso sino si (p = 2) luego Verdadero sino si (p mod 2 = 0) luego Falso sino aux(p, 3) donde aux(p, d) = Si ( p/2 < d) luego Verdadero sino si (p mod d = 0) luego Falso sino aux(p, d+2)

Traza de ejecución p = 29: primo4(29)= aux(29, 3) // ya que 29  0 , 29  1, 29  2 y 29 mod 2  0 aux(29, 3) = aux(29, 5) // ya 29 mod 3  0 aux(29, 5) = aux(29,7)=aux(29,9)=aux(29,11)=aux(29,13)=aux(29,15)=Verdadero Cantidad de invocaciones peor caso (p es primo) = (p-1)/4

PRUEBAS DE PRIMALIDAD… 15

Podemos hacer un algoritmo más eficiente, si observamos la siguiente proposición: Sea n > 1, n   . Sea q   / q es el menor natural donde q2  n. Si n no tiene factores propios  q  n es primo. Esto nos da un cota superior para la búsqueda de divisores de n

primo5(p) = Si (p = 0) o (p=1) luego Falso sino si (p = 2) luego Verdadero sino si (p mod 2 = 0) luego Falso sino aux(p, 3) donde aux(p, d) = Si ( p < d2) luego Verdadero sino si (p mod d = 0) luego Falso sino aux(p, d+2)

PRUEBAS DE PRIMALIDAD… 16

Ejemplo: Si n = 29

Vemos que: 52 = 25 y 62 = 36

y 25 < 29 < 36

Por lo que se buscarán divisores de 29 hasta q = 5 primo5(p) = Si (p = 0) o (p=1) luego Falso sino si (p = 2) luego Verdadero sino si (p mod 2 = 0) luego Falso sino aux(p, 3) donde aux(p, d) = Si ( p < d2) luego Verdadero sino si (p mod d = 0) luego Falso sino aux(p, d+2) Traza de ejecución p = 29:

primo5(29)= aux(29, 3) // ya que 29  0 , 29  1, 29  2 y 29 mod 2  0 aux(29, 3) = aux(29, 5) // ya 29 mod 3  0 aux(29, 5) = aux(29,7)=Verdadero

Teorema: n+ si n es compuesto   p primo / p|n H) n es compuesto  n > 1 T)  p primo / p|n  n = p.k con k  + D) Definamos S = { d  N / d > 1  d | n } // divisores de n > 1 Se ve que S   ya que n  S : n | n Por el Principio del Buen Orden (PBO), S tiene un elemento mínimo, llamémosle p. ( p | n) Vamos a demostrar que p no puede ser compuesto: (por Contradicción) Supongamos que p es compuesto  p = c. k

; c es divisor  1 ; c < p

 Si c | p  p | n  c | n (por Transitiva)  c  S, siendo c < p  Lo cual contradice la minimalidad de p  p no es compuesto  p es primo □

La criba de Eratóstenes: 18

Eratóstenes: matemático, astrónomo y geógrafo griego . siglo III a.c Cómo se puede elaborar sistemáticamente una lista de números primos menores que un natural M? Opciones:

1. Invocar al algoritmo primo5(n) donde n = 2.. 50 y ver cuáles de esos n son primos 2. Criba de Eratóstenes: Idea: en vez de averiguar cuáles números menores que n son primos, Averiguaremos cuáles son compuestos.

La criba de Eratóstenes: 19

Procedimiento: M = 50 1. Escribir los n° desde el 2 hasta M en forma consecutiva. Será nuestra Lista inicial: 2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

2. Comenzando desde i = 2, vamos marcando o tachando todos los múltiplos de 2, menos el mismo 2.

La criba de Eratóstenes: 20

Procedimiento: M = 50 1. Escribir los n° desde el 2 hasta M en forma consecutiva. Será nuestra Lista inicial: 2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

2. Comenzando desde i = 2, vamos marcando o tachando todos los múltiplos de 2, menos el mismo 2. Observar que 22 < 50

La criba de Eratóstenes: 21

Procedimiento: M = 50

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

3. Continuamos desde i = 3, (el primer número que quedó sin marcar después del 2) , marcando o tachando todos los múltiplos de 3, menos el mismo 3.

La criba de Eratóstenes: 22

Procedimiento: M = 50

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

3. Continuamos desde i = 3, (el primer número que quedó sin marcar después del 2) , marcando o tachando todos los múltiplos de 3, menos el mismo 3. Observar que 32 < 50

La criba de Eratóstenes: 23

Procedimiento: M = 50

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

4. Continuamos desde i = 5, marcando o tachando todos los múltiplos de 5, menos el mismo 5.

La criba de Eratóstenes: 24

Procedimiento: M = 50

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

4. Continuamos desde i = 5, marcando o tachando todos los múltiplos de 5, menos el mismo 5. Observar que 52 < 50

La criba de Eratóstenes: 25

Procedimiento: M = 50

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41 42 43 44 45 46 47 48 49 50 4. Continuamos desde i = 7, marcando o tachando todos los múltiplos de 7, menos el mismo 7.

La criba de Eratóstenes: 26

Procedimiento: M = 50

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41 42 43 44 45 46 47 48 49 50 4. Continuamos desde i = 7, marcando o tachando todos los múltiplos de 7, menos el mismo 7. Observar que 72 < 50

La criba de Eratóstenes: 27

Procedimiento: M = 50

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41 42 43 44 45 46 47 48 49 50 Ahora el próximo número de la lista sin marcar o tachar es el 11. Observar que 112 > 50, por lo que terminamos el proceso

La criba de Eratóstenes: 28

Procedimiento: M = 50 6. Los números que quedaron sin marcar, son todos los primos menores que M .

2 11

3 13

5

7 17

23 31 41

19

29 37

43

47

Criba(50) = { 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}

Criba de Eratóstenes: Algoritmo 29

criba(M) = criba1(2, {2,3,4,…M}, M) donde criba1(i, C, M) = // i: es el nro. cuyos múltiplos hay que tachar // C: Lista o conjunto que contendrá nros. Primos // M: tope

si ( i2 > M) luego C sino sea D := C – { i * j : 1 < j 

𝑀 𝑖

}

sea e := menor nro  D mayor que i criba1(e, D,M)

Criba de Eratóstenes: Prueba del Algoritmo 30

criba(M) = criba1(2, {2,3,4,…M}, M) donde criba1(i, C,M) = si ( i2 > M) luego C sino sea D := C – { i * j : 1 < j 

𝑀 𝑖

}

sea e := menor nro  D mayor que i criba1(e, D,M)

criba(50) = criba1(2, {2,3,4, …, 49,50}, 50) criba1(2, {2,3,4,5,6,7,8,9,10,..,49,50}, 50) = criba1( 3, {2,3,5,7,9,11,13,15,17,19,…49},50) criba1(3, {2,3,5,7,9,11,13,15,17,19,…49} , 50) = criba1( 5,{2,3,5,7,11,13,17,19,…49} ,50) criba1(5,{2,3,5,7,11,13,17,19,…,49} ,50) = criba1(7, {2,3,5,7,11,13,17,19,…49} , 50) criba1(7, {2,3,5,7,11,13,17,19,…49} ,50) = criba1(11, {2,3,5,7,11,13,17,19,…47} ,50) criba1(11, {2,3,5,7,11,13,17,19,…47} ,50) = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}

Teorema:  infinitos números enteros que son primos La demostración la realizaremos por Contradicción: Supongamos que NO  infinitos nros. primos. H) No  infinitos nros primos, es decir Primos = { P1, P2, P3, … ,Pk,…Pn}, con Pi primos. T) Llegar a una contradicción por lo que la H) será falsa, luego el Teorema es Verdadero D) Formemos el nro n = P1 * P2 * P3 * … * Pk * … * Pn + 1 Se ve que n  N , que n  0 y que n  1 Se ve también que n no es primo (Ej : 2*3*5*7*11*13 + 1 = 30031 que es divisible por 59)  n es compuesto  n es divisible por algún primo (teorema anterior)  Sea n divisible por Pk  n = Pk * d  Pk | n  Pk | (P1* P2 * P3* …*Pk * …* Pn + 1)  resto(n, Pk ) = 1 Como n es divisible por Pk , lo anterior no puede suceder  La suposición de que n era compuesto se contradice   infinitos primos

Para finalizar la clase …. 32

 Conceptualizar la relación “divide” en los números enteros:  a,b  , b 0, : b | a   k   / a = b.k  Definir número primo: Tiene solo 4 divisores: 1, -1, a, -a  Definir número compuesto: Si | a | > 1 y a no es primo .  Proponer distintos algoritmos para testear

la primalidad de un número:

primo(p), primo1(p), primo2(p), primo3(p), primo4(p) y primo5(p) cada vez más eficientes.  Proponer métodos que intenten producir solo nros. Primos: criba(M)  Determinar la existencia de infinitos nros. Primos: Teorema. Ahora podemos respondernos a estas cuestiones: 1. ¿Cómo decidir si un número es primo? 2. ¿Cuál es el número primo más grande? 3.¿Habrán infinitos primos?