Curso básico de
Teoría de Números

Curso básico de
Teoría de Números

Sebastián Castañeda Hernández

www.uninorte.edu.co

Km 5, vía a Puerto Colombia

A.A. 1569, Barranquilla (Colombia)

© Universidad del Norte, 2016

Sebastián Castañeda Hernández

Coordinación editorial

Zoila Sotomayor O.

Diagramación

Sebastian Castañeda Hernández

Diseño de portada

Joaquín Camargo Valle

Corrección de textos

Henry Stein

Procesos técnicos

Munir Kharfan de los Reyes

Desarrollo ePub

Lápiz Blanco S.A.S.

Hecho en Colombia

Made in Colombia

Contenido

Prólogo

1 Preliminares

1.1 Introducción

1.2 Números enteros

1.3 Divisibilidad y algoritmo de la división

1.4 Números primos y primos relativos

1.5 Grupos finitos

1.5.1 El grupo aditivo ℤ_n y el grupo de Euler

2 Teoría de congruencias

2.1 Introducción

2.2 La ecuación lineal diofantina

2.3 Congruencias lineales

2.4 Congruencias lineales en n variables

2.5 El teorema del resto

3 Funciones aritméticas

3.1 La función indicatriz de Euler

3.2 Funciones multiplicativas. Las funciones τ y σ

3.3 La función de Möbius y el producto de Dirichlet

4 Residuos cuadráticos. Raíces primitivas

4.1 Introducción

4.2 Congruencias cuadráticas módulo un primo

4.3 El símbolo de Legendre y la ley de reciprocidad cuadrática

4.4 Raíces primitivas

4.5 Existencia de raíces primitivas módulo m

A Lista de los primeros diez mil primos

Bibliografía

Prólogo

Este texto está dirigido a estudiantes de pregrado en Matemáticas. Presupone un conocimiento básico sobre Álgebra lineal, incluyendo rudimentos de teoría de grupos y, preferiblemente, de anillos.

El texto inicia con algunos preliminares sobre números enteros (presentados como subconjunto del campo ordenado de los números reales), divisibilidad y números primos, así como resultados básicos de grupos, especialmente grupos finitos. En esta primera edición los temas incluidos son pocos, pensados para un curso de un semestre con intensidad de tres horas semanales, pero se espera ampliarlo en futuras ediciones, año tras año, contando con la facilidad de la edición electrónica.

Temas de complementación y profundización se irán adicionando en ediciones futuras o podrán consultarse próximamente en la página web del autor (https://sites.google.com/site/scasta1957). Esta primera edición será ampliada y mejorada con la ayuda de los estudiantes y lectores si ellos así lo desean. En la página web mencionada se podrá tener acceso a software de ayuda, como tests de primalidad, determinación de residuos cuadráticos módulo un primo y cálculos en aritmética modular, entre otros.

La idea del texto es presentar la teoría básica requerida como fundamentación de las clases en un primer curso de Teoría de números y, como tal, se insiste principalmente en el manejo teórico por parte de los estudiantes; en la página web del autor antes indicada se hará la presentación de talleres y ejercicios adicionales sobre los temas tratados en el texto. Finalmente, estamos abiertos a cualquier sugerencia o corrección que los estudiantes o lectores consideren pertinentes.

El autor
scasta@uninorte.edu.co, scasta1957@gmail.com

CAPÍTULO

1

Preliminares

SECCIÓN 1.1

Introducción

En este primer capítulo presentamos algunos preliminares para el curso de Teoría de números; específicamente, cuestiones relativas a números enteros y a temas puntuales de Álgebra, especialmente de Teoría de grupos, y de estructuras cociente, en particular la estructura de anillo de ℤ_n. Los números enteros se introducirán como un subconjunto especial de los números reales, asumiendo que el estudiante-lector está familarizado con la estructura

(ℝ, +, ·, ≤)

como campo ordenado y completo.

SECCIÓN 1.2

Números enteros

Suponemos, como ya se mencionó, que se está familiarizado con la estructura de campo (ℝ, +, ·), así como con los axiomas de orden en ℝ, el axioma de completitud o del supremo, y el respectivo resultado dual relativo al ínfimo, y las principales propiedades y teoremas relativos a cotas, máximo, mínimo, etc. de subconjuntos de ℝ.

Claramente, el conjunto mismo de los reales es inductivo, de modo que la familia

= {I ⊆ ℝ|I es inductivo }

es no vacía. De igual manera es fácil demostrar (ejercicio) que la intersección de conjuntos inductivos es también un conjunto inductivo; es decir, es cerrado bajo intersecciones. El conjunto de los números naturales lo definimos como la intersección de todos los conjuntos inductivos. Notaremos tal conjunto por ℕ. Es decir:

De la definición anterior se sigue que ℕ es el menor (según la inclusión de conjuntos) conjunto inductivo. Esto significa:

1. ℕ es inductivo.

2. Para todo I ∈ se tiene que ℕ ⊆ I.

Tenemos el siguiente resultado inmediato, fundamental en las denominadas demostraciones por inducción.

Teorema 1.2.1. Principio de inducción matemática: Sea I ⊆ ℕ. Si I es inductivo, entonces I = ℕ

En particular, si consideramos el conjunto I = {x ∈ ℕ|x ≥ 1}, entonces se tiene que:

• 1 ∈ I.
• Si k ∈ I, entonces k ≥ 1, por lo que k +1 ≥ 2 ≥ 1. Como ℕ es inductivo se tiene además que (k +1) ∈ ℕ, luego (k +1) ∈ I.

Tenemos así que I es inductivo y por tanto I = ℕ. Así, resulta que todo número natural es positivo y que no existe un número natural entre 0 y 1. Definimos el conjunto de los números enteros, notado ℤ, como

ℤ = ℕ ∪{0}∪{−x|x ∈ ℕ}.

ℕ será también denominado el conjunto de los enteros positivos. El conjunto ℕ₀ = ℕ ∪ {0} = {0, 1, 2,... } será denominado conjunto de los números cardinales o enteros no negativos. EL conjunto ℤ⁻ = {−x|x ∈ ℕ} será, consecuentemente, denominado conjunto de los enteros negativos.

Algunos resultados básicos sobre enteros se resumen en el siguiente teorema¹.

Teorema 1.2.2.

1. ℕ, ℕ₀ y ℤ son cerrados para la adición y la multiplicación. (ℤ, +, ·) es un anillo conmutativo con identidad.

2. Si x, y ∈ ℤ y xy = 1 entonces y = x = ±1. Es decir, los únicos enteros con inverso multiplicativo entero son 1 y su inverso aditivo −1.

3. Principio del buen orden. Si A ⊆ ℕ₀ y A ≠ ∅, entonces A tiene un primer (mínimo) elemento. Dualmente, todo subconjunto no vacío del conjunto de los enteros negativos tiene un máximo o último elemento.

4. Para todo entero n, el conjunto {x ∈ ℤ|n < x < n +1} es vacío.

5. ℕ (y por tanto ℤ) no está acotado superiormente. El resultado dual es que ℤ⁻ (y por tanto ℤ) no está acotado inferiormente.

6. Propiedad arquimediana. Si x, y ∈ ℝ, con x > 0, existe un natural n tal que nx > y.

7. Si A ⊆ ℤ y A es acotado superiormente, entonces sup(A) ∈ A. Dualmente, si A está acotado inferiormente, entonces inf(A) ∈ A.

El principio de inducción (teorema 1.2.1), como se dijo, es el fundamento de las denominadas demostraciones por inducción matemática. Si P(n) es una proposición acerca del natural n, y si

I = {n ∈ ℕ|P(n) es verdadera },

entonces, por el teorema mencionado, se tiene que si I es inductivo, entonces I = ℕ lo que significa que P(n) es verdadera para todo número natural. Es decir, tenemos entonces que si se cumplen:

1. P (1) es verdadera.

2. Para todo natural k, si P(k) es verdadera, entonces P(k+1) es verdadera.

entonces P(n) es verdadera para todo número natural n.

Si n₀ es un entero cualquiera, el principio de inducción puede extenderse fácilmente al subconjunto

A = {n ∈ ℤ|n ≥ n₀}.

En efecto, supongamos que I es un subconjunto de A que satisface:

1. n₀ ∈ I.

2. Para todo k ∈ ℝ, si k ∈ I entonces k +1 ∈ I.

Entonces si x ∈ A se tiene x = n₀ + k para algún k ∈ ℕ₀. Si k = 0 se sigue que x = n₀ ∈ I. Si k > 0, entonces k ∈ ℕ y podemos usar el principio de inducción para probar que n₀ + k ∈ I para todo k ≥ 1.

Ahora, para k = 1 se tiene que como n₀ ∈ I, entonces n₀ +1 = n₀ + k ∈ I. Si se supone que n₀ + k ∈ I para un natural k, entonces por la segunda condición cumplida por I se sigue que (n₀ + k ) + 1 = n₀ + (k + 1) ∈ I, lo que termina la demostración. Se tiene entonces que A ⊆ I y, en consecuencia, A = I.

Tenemos entonces que si n₀ ∈ ℤ y P(n) es una proposición acerca del entero n y si se cumplen:

1. P(n₀) es verdadera.

2. Para todo entero k ≥ n₀ se verifica que si P(k) es verdadera, entonces P(k +1) lo es.

Necesariamente se sigue que P(n) es verdadera para todo entero n ≥ n₀.

Una tercera versión, muy útil, del principio de inducción es como sigue. La demostración se propone como ejercicio.

Teorema 1.2.3. Sea n₀ ∈ ℤ y A = {n ∈ ℤ|n ≥ n₀}. Sea I ⊆ A y supongamos que:

1. n₀ ∈ I.

2. Para todo entero k con n₀ ≤ k < n, si k ∈ I, entonces n ∈ I.

Entonces necesariamente se tiene que I = A.

SECCIÓN 1.3

Divisibilidad y algoritmo de la división

Si a divide a b es usual decir que a es un divisor de b y que b es un múltiplo de a. Algunas de las propiedades básicas de la relación de divisibilidad en ℤ se presentan a continuación.

Teorema 1.3.1.

1. La relación de divisibilidad es reflexiva y transitiva pero no es simétrica ni antisimétrica.

2. Para todo entero a se tiene que a|0, 1|a, −1|a. Además 0|a si y solo si a = 0.

3. Para todo entero a se tiene que a||a|, |a||a

4. Si a, b, c, d ∈ ℤ, entonces:

(a) a|b y b|a si, y sólo si |a| = |b|.

(b) Si a|b y b ≠ 0, entonces |a| ≤ |b|.

(c) Si a|b y a ≠ 0, entonces .

(d) Si a|b y a|c, entonces para todo par de enteros x, y se tiene que a|(bx + cy).

(e) Si ac|bc y c ≠ 0, entonces a|b.

(f) Si a|b y c|d, entonces ac|bd.

Demostración. La mayoría de las demostraciones son sencillas y se proponen como ejercicios. Por ejemplo, demostremos (4a). Si a|b y b|a, entonces existen enteros x, y tales que b = ax, a = by. Si b = 0, entonces a = 0 y |a| = |b|. Si b ≠ 0, entonces de b = (by)x = b(yx), se sigue que yx = 1, de donde y = x = ±1 y por tanto b = ±a, luego |a| = |b|. Ahora, si |a| = |b|, entonces a = b o a = −b, b = −a de donde a|b y b|a. Para demostrar (4b), notamos que si 0 ≠ b = ax, entonces |x| ≥ 1 y, por tanto|b| = |a||x| ≥ |a|.

Una relación reflexiva y transitiva es usualmente denominada un preorden. Para una tal relación pueden también definirse elementos maximales, minimales, máximo y mínimo de un conjunto respecto de dicho preorden, de manera similar como en conjuntos parcialmente ordenados. Sin embargo, no necesariamente elementos máximos (o mínimos) bajo un preorden son únicos. En el caso del conjunto de los enteros, en particular, la divisibilidad es un preorden (no antisimétrico) y, por ejemplo, 0 es un elemento máximo pues para todo x ∈ ℤ se cumple que x|0. 0 es también un elemento maximal pues, como lo indica el teorema anterior, si 0|x, entonces x = 0. Por su parte, 1 y −1 son elementos mínimos (aunque no minimales) en ℤ, bajo la relación de divisibilidad ya que para todo entero x se verifica que 1|x y −1|x. De particular interés en Teoría de números es la existencia de elementos maximales o máximos (y los duales, mínimo y minimales) de subconjuntos de ℤ bajo la relación de divisibilidad, en especial en subconjuntos de divisores comunes de un conjunto finito de enteros dados. Antes presentamos el algoritmo de la división que será de utilidad en la dirección mencionada.

Teorema 1.3.2. Algoritmo de la división. Sean a y b enteros con b > 0. Entonces existen enteros q y r tales que

Demostración. Si b > 0, por la propiedad arquimediana, teorema 1.2.2 (6), existe t₀ ∈ ℕ tal que t₀b ≥ −a, de modo que a + bt₀ ≥ 0. Así, el conjunto

A = {a + bt|t ∈ ℤ, a + tb ≥ 0} ⊆ ℕ₀

es no vacío y tiene, por tanto, un elemento mínimo (principio del buen orden). Sea r = min(A) ≥ 0, de modo que existe t₁ ∈ ℤ tal que r = a + bt₁ y haciendo q = −t₁ ∈ ℤ se tiene que a = bq + r.

Si r ≥ b, entonces se tendría

por lo que a +(−q − 1)b = a − qb − b ∈ A, de donde a − bq − b ≥ r = a − bq, de donde se seguiría que b ≤ 0, que contradice la positividad de b. Así, necesariamente, se tiene que r < b.

Si A es un subconjunto no vacío de ℤ y si

DC(A) = {x ∈ ℤ|∀y ∈ A : x|y}

es el conjunto de los divisores comunes de los elementos de A, entonces dicho conjunto es no vacío pues contiene al conjunto {−1, 1}. Si existe un elemento máximo (respecto de la relación de divisibilidad) de DC(A), digamos d, entonces d ∈ DC(A) y para todo x ∈ DC(A) se satisface que x|d. Claramente −d es también un máximo de DC(A), por lo que la unicidad no está garantizada. Para garantizar tal unicidad exigiremos que d ≥ 0.

Definimos inicialmente el máximo común divisor para dos enteros y después lo extenderemos a un número finito cualquiera de enteros. La definición, sin embargo, como se comentó en el párrafo anterior, puede extenderse a cualquier subconjunto de ℤ si bien en general no está garantizada la existencia.

Como se demostrará a continuación, la condición exigida de no negatividad garantiza la unicidad del máximo común divisor de dos enteros cualesquiera.

Teorema 1.3.3. Sean a y b enteros cualesquiera. Entonces existe un único máximo común divisor de a y b.

Demostración. Consideremos primero el caso en que uno de los dos enteros dados, o ambos, es cero. Supongamos, sin perder generalidad, que b = 0. Como todo entero divide a cero se tiene que |a||b y, además |a||a, |a| ≥ 0. Ahora, si c es un entero tal que c|a y c|b, entonces, como a||a| se sigue que c||a|, por lo que |a| es un máximo común divisor de a y b. Si d fuese otro máximo común divisor de a y b se tendría que d ≥ 0 y d||a|, |a||d, de donde se sigue que d = |d| = |a| y se tiene la unicidad.

Consideremos ahora el caso restante: a ≠ 0, b ≠ 0. Sea

A = {ax + by|x, y ∈ ℤ, ax + by > 0}

Como se sigue que |a| (y, por razones similares, también |b|) está en A, por lo que tal conjunto es no vacío y, por el principio del buen orden, existe

d = min(A) = ax₀ + by₀, para enteros x₀, y₀.

Claramente, todo entero que divida a a y b divide a d y d > 0. Como |a|, |b| ∈ A y |a||a, |b||b, bastará entonces con demostrar que para todo par de enteros x, y se cumple que d|ax + by = z ∈ A. Ahora bien, por el algoritmo de la división, existen q, r ∈ ℤ tales que

z = ax + by = dq + r, con 0 ≤ r < d.

Si r > 0, se tendría

r = ax + by − dq = ax + by − (ax₀ + by₀)q = a(x − qx₀) + b(y − qy₀) > 0

lo que implicaría que r ∈ A y, por la minimalidad de d, se tendría r ≥ d, contradiciendo que r < d. Se tiene así que r = 0 y, por tanto, d|z. En consecuencia, d es un máximo común divisor de a y b. Nuevamente, si d^' fuese también máximo común divisor de a y b, necesariamente se tendría |d| = |d^'| y como ambos son positivos se sigue que d = d^'.

Puesto que existe un único máximo común divisor de los enteros a y b, podemos hablar del máximo común divisor (abreviado mcd) de a y b y lo notaremos por (a, b). Claramente se tiene que (a, b) = (b, a).

En la demostración del teorema anterior se incluyó que el máximo común divisor entre un entero cualquiera, a, y cero es |a|, así como el importante resultado que, para enteros no nulos a y b, el máximo común divisor es una combinación lineal entera de a y b. Si alguno de los dos enteros, digamos b, es nulo, entonces el máximo común divisor de a y b es |a|, el cual es también una combinación lineal entera de a y b.

Tenemos así:

El teorema siguiente presenta las propiedades básicas del máximo común divisor de dos enteros.

Teorema 1.3.4. Sean a, b, c enteros. Entonces:

Algoritmo de Euclides: Si a = qb + r, para enteros cualesquiera q y r, entonces

Demostración.

1. 1.3 y 1.4 se siguen trivialmente de la definición.

2. Demostremos (1.5). Sea d = (a, b), entonces como d|a y d|b, se tiene que d|c||ac y d|c||bc. Ahora d = ax₁ + by₁, para x₁, y₁ ∈ ℤ por lo que

dc = acx₁ + bcy₁.

  Así, si z|ac y z|bc, entonces z|(ac)x₁ +(bc)y₁ = dc|d|c|. Se tiene entonces que d|c| = (ac, bc).

3. Si d = (a, b), entonces claramente d| − a y d|b y si c es divisor de −a y b lo es de a y b y, por tanto, de d. Se tiene así que d = (−a, b). De 1.6 se siguen

4. Para demostrar (1.7), hagamos d = ((a, b), c). de modo que d|(a, b) y d|c, por lo que d|a y d|b, d|c. Tenemos entonces que d|(b, c) y d|a.
Ahora, si z|a y z|(b, c), entonces z|a, z|b, z|c por lo que z|(a, b) y z|c y como d = ((a, b), c) se sigue que z|d. Se tiene entonces que d = (a, (b, c)).