Teoria Numeros

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

Prof. Walter Mora F.,
Escuela de Matemática
Instituto Tecnológico de Costa Rica.
(https://tecdigital.tec.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 no permiteventa 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 o completitud delcontenido.
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://tecdigital.tec.ac.cr/revistamatematica/Libros/TeoriaNumeros/WMora_TeoriaNumeros.pdf

2

Copyright© Revista digital Matemática Educación eInternet (www.tec-digital.itcr.ac.cr/revistamatematica/). Primera 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 de Matemática,Instituto Tecnológico de Costa Rica. 2010.
219 pp.ISBN Obra Independiente: 978-9968-641-11-1
1. Teoría de números. 2. Algoritmos 3. Programación.

Contenido

Prefacio

6
PARTE I

1

Fundamentos
1.1
1.2
1.3
1.4

2

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

2
2
5
5
7
11

Divisibilidad

14

2.1

15
17
18
21
22
27
29
31
32
34
36
39
43

2.2
2.3
2.4
2.5
2.6
2.7
2.8

3INTRODUCCCION A LA TEORIA DE NUMEROS.

“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.1
Algoritmo e implementación.
Ecuaciones Diofánticas lineales.
Teorema fundamental de la aritmética
EjerciciosCongruencias

47
3

4

CONTENIDO

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 un elemento módulo m.
El Teorema “pequeño” de Fermat.
Teorema de Euler
4.3.1
Un recíproco del Teorema pequeño de Fermat
Teorema de Wilson
Teorema de CarmichaelEjercicios

Ra´ices primitivas y logaritmo discreto
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
Teorema Chino 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 deReciprocidad Cuadrática.
Símbolo de Jacobi.
Ejercicios

47
50
52
53
56
61
63
66
67
71
71
73
75
82
83
85
88
92
92
92
97
101
104
104
106
108
112
115
121
123

Estimaciones, Estadísticas y Promedios

126

7.1
7.2
7.3
7.4

126
130
132
134
134
136
138
140
143
146

7.5

7.6

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órmulade Legendre para π ( x ).
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
Teorema de Mertens.
Números Armónicos

5

7.7

Acerca de los factores de un número grande
Ejercicios
PARTE II

8

INTRODUCCION A LA TEORIA ALGORITMICA DE NUMEROS.

Algoritmos para el mcd

153

8.1
8.2
8.3

154
155
159
160
162
163
164
165...