introduccion a la teoria de numeros

INTRODUCCIÓN a la
TEOR´ DE NÚMEROS.
IA
Ejemplos y algoritmos.

Prof. Walter Mora F.,
Escuela de Matemática
Instituto Tecnológico de Costa Rica.
(www.tec-digital.itcr.ac.cr/revistamatematica/)

Este libro se distribuye bajo la licencia Creative Commons Reconocimiento - No Comercial - Sin obra
derivada 3.0 Unported License. Esta licencia permite copiado y distribución gratuita, pero nopermite venta ni modificaciones de
este material. Ver http://creativecommons.org/.
Límite de responsabilidad y exención de garantía: El autor o los autores han hecho su mejor esfuerzo en la preparación de este
material. Esta edición se proporciona“tal cual”. Se distribuye gratuitamente con la esperanza de que sea útil, pero sin ninguna
garantía expresa o implícita respecto a la exactitud ocompletitud del contenido.
La Revista digital Matemáticas, Educación e Internet es una publicación electrónica. El material publicado en ella expresa la
opinión de sus autores y no necesariamente la opinión de la revista ni la del Instituto Tecnológico de Costa Rica.
https://dl.dropbox.com/u/56645701/walter_mora_matematica_itcr/Libros/TeoriaNumeros/WMora_TeoriaNumeros.pdf

2

Copyright©Revista digital Matemática Educación e Internet (www.tec-digital.itcr.ac.cr/revistamatematica/). Segunda Edición.
Correo Electrónico: wmora2@gmail.com
Escuela de Matemática
Instituto Tecnológico de Costa Rica
Apdo. 159-7050, Cartago
Teléfono (506)25502225
Fax (506)25502493

Mora Flores, Walter.
Introducción a la Teoría de Números. Ejemplos y algoritmos. 1ra ed.
– Escuela deMatemática,Instituto Tecnológico de Costa Rica. 2010.
217 pp.
ISBN Obra Independiente: 978-9968-641-11-1
1. Teoría de números. 2. Algoritmos 3. Programación.

Contenido

Prefacio

7
PARTE I

1

Fundamentos
1.1
1.2
1.3
1.4

2

INTRODUCCCION A LA TEORIA DE NUMEROS.

Principios
Valor absoluto y la función sgn( x )
Las funciones x
x y x
Números Poligonales y Piramidales
Ejercicios

2
2
55
7
11

Divisibilidad

13

2.1

14
17
17
20
22
26
29
30
32
34
36
39

2.2
2.3
2.4
2.5
2.6
2.7
2.8

“Algoritmo de la división”
Ejercicios
Números Primos.
Criba de Eratóstenes: Cómo colar números primos.
2.3.1
Algoritmo e implementación.
Máximo común divisor
Algoritmo de Euclides I.
2.5.1
Algoritmo e implementación.
Algoritmo Extendido de Euclides.
2.6.1Algoritmo e implementación.
Ecuaciones Diofánticas lineales.
Teorema fundamental de la aritmética

3

4

CONTENIDO

Ejercicios
3

Congruencias
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8

4

Potencias mod m
4.1
4.2
4.3
4.4
4.5

5

Introducción
Raíces Primitivas
Logaritmo discreto o Indicador
Ejercicios

Residuos Cuadráticos
6.1
6.2
6.3

6.4

7

Orden de unelemento módulo m.
El Teorema “pequeño” de Fermat.
Teorema de Euler
4.3.1
El recíproco del Teorema pequeño de Fermat
Teorema de Wilson
Teorema de Carmichael
Ejercicios

Ra´ces primitivas y logaritmo discreto
i
5.1
5.2
5.3

6

Congruencias módulo m
Calendarios: ¿Qué día nació Ud?.
Trucos de divisibilidad.
Cuadrados Mágicos
Clases residuales módulo m
Congruencias lineales
TeoremaChino del resto
Congruencias de Orden Superior
Ejercicios

Congruencias cuadráticas módulo m
Criterio de Euler
Símbolos de Legendre y Jacobi
6.3.1
Lema de Gauss
6.3.2
Ley de Reciprocidad Cuadrática.
Símbolo de Jacobi.
Ejercicios

43
46
46
49
51
52
55
60
63
66
67
70
70
72
74
82
82
85
88
91
91
91
96
100
102
102
104
106
110
114
119
121

Estimaciones,Estadísticas y Promedios

124

7.1
7.2
7.3
7.4

124
128
130
132
133

Funciones Aritméticas
A los números primos les gusta los juegos de azar.
Orden de Magnitud
Teorema de los números primos
7.4.1
Fórmula de Legendre para π ( x ).

5

7.4.2
Fórmula de Meisel para π ( x ).
Estimación de π ( x ). Teorema de los números primos.
7.5.1
La función Zeta de Riemann
7.5.2...