Teoría de números (para principiantes)

Lista de figuras vii

Lista de tablas ix

Prefacio xi

Capítulo uno

Números naturales 1

1.1. Adición y multiplicación de números naturales . . . . . . . . . . . . . 3

1.2. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3. Orden entre números naturales . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.4. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.5. Construcción de los números enteros . . . . . . . . . . . . . . . . . . . . . 8

1.6. Principio de inducción matemática . . . . . . . . . . . . . . . . . . . . . . . 10

1.7. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.8. Ejercicios adicionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Capítulo dos

Divisibilidad 29

2.1. Propiedades básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.2. Máximo común divisor (MCD) . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.3. Algoritmo de Euclides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.4. Propiedades del máximo común divisor. . . . . . . . . . . . . . . . . . . 35

2.5. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.6. Mínimo común múltiplo y generalizaciones . . . . . . . . . . . . . . . 45

2.7. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

2.8. Teorema fundamental de la aritmética . . . . . . . . . . . . . . . . . . . . 54

2.9. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

2.10.Algunas propiedades de los números primos . . . . . . . . . . . . . . . 58

2.11.Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

2.12.Algunas ecuaciones diofánticas . . . . . . . . . . . . . . . . . . . . . . . . . . 64

2.13.Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

2.14.Ejercicios adicionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

Capítulo tres

Funciones aritméticas 83

3.1. La función parte entera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

3.2. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

3.3. Las funciones número y suma de divisores . . . . . . . . . . . . . . . . 92

3.4. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

3.5. Números perfectos, de Mersenne y de Fermat . . . . . . . . . . . . . 97

3.6. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

3.7. La función Φ de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

3.8. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

3.9. Funciones multiplicativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

3.10.Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

3.11.La fórmula de inversión de Möbius . . . . . . . . . . . . . . . . . . . . . . 114

3.12.Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

3.13.Ejercicios adicionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

Capítulo cuatro

Congruencias 127

4.1. Definición y propiedades básicas . . . . . . . . . . . . . . . . . . . . . . . . . 129

4.2. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

4.3. Criterios de divisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

4.4. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

4.5. Aritmética módulo n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

4.6. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

4.7. Los teoremas de Euler y Fermat . . . . . . . . . . . . . . . . . . . . . . . . . 143

4.8. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

4.9. Congruencias lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

4.10.Sistemas de congruencias lineales . . . . . . . . . . . . . . . . . . . . . . . . 151

4.11.Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

4.12.El teorema chino del residuo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

4.13.Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

4.14.Congruencias de grado superior . . . . . . . . . . . . . . . . . . . . . . . . . 162

4.15.Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

4.16.Congruencias con módulo una potencia de un primo . . . . . . . . 165

4.17.Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

4.18.Teoremas de Lagrange y Wilson . . . . . . . . . . . . . . . . . . . . . . . . . 169

4.19.Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

4.20.Ejercicios adicionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173

Capítulo cinco

Residuos cuadráticos 181

5.1. Congruencias de segundo grado con módulo primo . . . . . . . . . 183

5.2. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

5.3. Ley de la reciprocidad cuadrática . . . . . . . . . . . . . . . . . . . . . . . . 191

5.4. El símbolo de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

5.5. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

5.6. Potencias módulo n y raíces primitivas . . . . . . . . . . . . . . . . . . . . 202

5.7. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206

5.8. Álgebra y teoría de números . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

5.9. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216

5.10.Ejercicios adicionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

Capítulo seis

Criptografía 223

6.1. Nociones básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225

6.2. Cifrados monográficos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226

6.3. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

6.4. Cifrado en bloques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

6.5. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248

6.6. Cifrados exponenciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

6.6.1. Algoritmo para calcular P

e módulo p . . . . . . . . . . . . . . . . . 253

6.7. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255

6.8. Sistemas de clave pública . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257

6.8.1. Sistema RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258

6.8.2. Sistema de Rabin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

6.8.3. Sistema de la mochila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

6.9. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269

Capítulo siete

Fracciones continuas 275

7.1. Fracciones continuas finitas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277

7.2. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278

7.3. Convergentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281

7.4. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282

7.5. Fracciones continuas infinitas . . . . . . . . . . . . . . . . . . . . . . . . . . . 284

7.6. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

7.7. Fracciones continuas periódicas . . . . . . . . . . . . . . . . . . . . . . . . . 288

7.8. Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

7.9. Aproximación de números irracionales . . . . . . . . . . . . . . . . . . . 293

7.10.Ejercicios y soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294

7.11.Ecuación de Pell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

7.12.Ejercicios adicionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304

Apéndice A

Números primos menores que 10 000 307

Índice 313

Referencias 315