Introducción a la Teoría de Números: Ejemplos y Algoritmos – Walter Mora – 2da Edición

Prefacio

PARTE I INTRODUCCCION A LA TEORIA DE NUMEROS

1 Fundamentos
1.1 Principios
1.2 Valor absoluto y la función sgn(x)
1.3 Las funciones TxU VxW y JxK
1.4 Números Poligonales y Piramidales

2 Divisibilidad
2.1 Algoritmo de la división
2.2 Números Primos
2.3 Criba de Eratóstenes: Cómo colar números primos
2.3.1 Algoritmo e implementación
2.4 Máximo común divisor
2.5 Algoritmo de Euclides I
2.5.1 Algoritmo e implementación
2.6 Algoritmo Extendido de Euclides
2.6.1 Algoritmo e implementación
2.7 Ecuaciones Diofánticas lineales
2.8 Teorema fundamental de la aritmética

3 Congruencias
3.1 Congruencias módulo m
3.2 Calendarios: ¿Qué día nació Ud?
3.3 Trucos de divisibilidad
3.4 Cuadrados Mágicos
3.5 Clases residuales módulo m
3.6 Congruencias lineales
3.7 Teorema Chino del resto
3.8 Congruencias de Orden Superior

4 Potencias mod m
4.1 Orden de un elemento módulo m
4.2 El Teorema pequeño de Fermat
4.3 Teorema de Euler
4.3.1 El recíproco del Teorema pequeño de Fermat
4.4 Teorema de Wilson
4.5 Teorema de Carmichael

5 Raíces primitivas y logaritmo discreto
5.1 Introducción
5.2 Raíces Primitivas
5.3 Logaritmo discreto o Indicador

6 Residuos Cuadráticos
6.1 Congruencias cuadráticas módulo m
6.2 Criterio de Euler
6.3 Símbolos de Legendre y Jacobi
6.3.1 Lema de Gauss
6.3.2 Ley de Reciprocidad Cuadrática
6.4 Símbolo de Jacobi

7 Estimaciones, Estadísticas y Promedios
7.1 Funciones Aritméticas
7.2 A los números primos les gusta los juegos de azar
7.3 Orden de Magnitud
7.4 Teorema de los números primos
7.4.1 Fórmula de Legendre para ?(x)
7.4.2 Fórmula de Meisel para ?(x)
7.5 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
7.6 Números Armónicos
7.7 Acerca de los factores de un número grande

PARTE II INTRODUCCION A LA TEORIA ALGORITMICA DE NUMEROS

8 Algoritmos para el mcd
8.1 Parte entera
8.2 División con menor resto
8.3 Algoritmo de Euclides II
8.3.1 Algoritmo e implementación
8.4 Algoritmo de Euclides con menor resto
8.4.1 Implementación
8.5 Algoritmo binario
8.5.1 Algoritmo e Implementación
8.6 Algoritmo LSBGCD (left-shift binary algorithm)
8.6.1 Algoritmo e Implementación
8.7 Algoritmo Extendido de Euclides
8.8 Inversos multiplicativos en m

9 Números Primos y factorización
9.1 Introduccción
9.2 Criba de Eratóstenes
9.3 Primos entre m y n
9.4 Factorización por ensayo y error
9.4.1 Probando con una progresión aritmética
9.4.2 Algoritmo
9.5 Método de factorización rho de Pollard
9.5.1 Algoritmo e implementación
9.6 Pruebas de Primalidad
9.7 Prueba de primalidad de Miller-Rabin
9.7.1 Algoritmo e implementación
9.8 Algoritmo Chino del Resto
9.8.1 Algoritmo e implementación

Bibliografía
Solución de los Ejercicios