\( \newcommand{\Implies}{\Rightarrow} \newcommand{\Iff}{\Leftrightarrow} \renewcommand{\emptyset}{\varnothing} \newcommand{\powersetsym}{\mathcal{P}} \newcommand{\fto}{\rightarrow} \newcommand{\mto}{\mapsto} \newcommand{\Cx}{\mathbb{C}} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\Ns}{\mathbb{N}^*} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\K}{\mathbb{K}} \newcommand{\vv}[1]{\boldsymbol{#1}} \newcommand{\Abs}[1]{\left\lvert#1\right\rvert} \newcommand{\norm}[1]{ \left\|#1\right\| } \newcommand{\pnorm}[1]{\left\|#1\right\|_p} \newcommand{\supnorm}[1]{\left\|#1\right\|_\infty} \newcommand{\innerprod}[1]{\left\langle #1\right\rangle} \newcommand{\Ceil}[1]{\left\lceil #1\right\rceil} \newcommand{\Floor}[1]{\left\lfloor #1\right\rfloor} \newcommand{\Conj}[1]{\overline{#1}} \newcommand{\arccot}{\mathop{\text{arc\,cot}}\nolimits} \newcommand{\arcsec}{\mathop{\text{arc\,sec}}\nolimits} \newcommand{\arccsc}{\mathop{\text{arc\,csc}}\nolimits} \renewcommand{\arg}{\mathop{\text{arg}}\nolimits} \newcommand{\mcd}[1]{\mathop{\text{mcd}}\left(#1\right)} \newcommand{\mcm}[1]{\mathop{\text{mcm}}\left(#1\right)} \renewcommand{\ker}{\mathop{\text{ker}}\nolimits} \newcommand{\grad}{\mathop{\text{grad}}\nolimits} \newcommand{\dom}{\mathop{\text{dom}}\nolimits} \newcommand{\rng}{\mathop{\text{ran}}\nolimits} \newcommand{\diam}{\mathop{\text{diam}}\nolimits} \newcommand{\Obj}{\mathop{\text{obj}}\nolimits} \newcommand{\Hom}{\mathop{\text{hom}}\nolimits} \newcommand{\End}{\mathop{\text{end}}\nolimits} \newcommand{\Aut}[1]{\mathop{\mathrm{aut}}\nolimits(#1)} \newcommand{\Inn}[1]{\mathop{\mathrm{int}}\nolimits(#1)} \newcommand{\Deg}{\mathop{\mathrm{grad}}\nolimits} \newcommand{\Img}{\mathop{\text{im}}\nolimits} \newcommand{\Id}{\mathop{\mathrm{id}}\nolimits} \newcommand{\sgn}{\mathop{\mathrm{sgn}}\nolimits} \renewcommand{\Re}{\mathop{\mathrm{Re}}\nolimits} \renewcommand{\Im}{\mathop{\mathrm{Im}}\nolimits} \newcommand{\Char}{\mathop{\mathrm{car}}\nolimits} \renewcommand{\mod}[1]{\mathop{(\mathop{\text{mód}}\nolimits #1)}} \newcommand{\res}{\mathop{\text{mód}}} \newcommand{\categof}[1]{\mathsf{#1}} \newcommand{\CC}{\categof{C}} \newcommand{\CONJ}{\categof{Conj}} \newcommand{\SET}{\categof{Set}} \newcommand{\GRP}{\categof{Grp}} \newcommand{\AGRP}{\categof{Ab}} \newcommand{\morph}[1]{\mathrel{\mathop{\longrightarrow}\limits^{#1}}} \newcommand{\subgr}{\leq} \newcommand{\nsubgr}{\mathrel{\unlhd}} \newcommand{\iso}{\cong} \newcommand{\genby}[1]{\left\langle #1\right\rangle} \newcommand{\symgr}[1][n]{S_{#1}} \newcommand{\GenOf}[1]{\mathop{\text{gen}}\left(#1\right)} \newcommand{\normalizer}[2][G]{{\mathbf N}_{#1}(#2)} \newcommand{\centralizer}[2][G]{{\mathbf C}_{#1}(#2)} \newcommand{\orbit}[2][G]{\mathcal{O}_{#1}(#2)} \newcommand{\stab}[2][G]{#1(#2)} \newcommand{\GL}[2][n]{\mathrm{GL}(#1,#2)} \newcommand{\SL}[2][n]{\mathrm{SL}(#1,#2)} \newcommand{\Ort}[2][n]{\mathrm{O}(#1,#2)} \newcommand{\SO}[2][n]{\mathrm{SO}(#1,#2)} \newcommand{\KleinV}{\mathbf{V}}\)

[siguiente][anterior][arriba]

1.3 Números primos

Definición 1.24. Un entero \( p > 1 \) se dice primo si no tiene más divisores positivos que él mismo y la unidad. Un entero positivo \( x > 1 \) que no es primo, y que por tanto es de la forma \( ab \) con \( 1 < a,b < x \), se dice que es compuesto.

Es inmediato que todo entero \( x > 1 \) tiene al menos un divisor primo. En efecto, pues si \( x \) es primo, entonces éste es su propio divisor primo, y si es compuesto, entonces el menor de los divisores \( p > 1 \) de \( x \) ha de ser primo, pues de lo contrario existiría un \( d > 1 \) que divide a \( p \) y por tanto a \( x \), lo que no puede ser pues \( d < p \) y hemos supuesto que \( p \) es el menor de los divisores de \( x \) mayores a la unidad. Observemos que este divisor primo verifica \( p \leq \sqrt {x} \), pues \( x = py \) y \( 1 < p \leq y \), así que \( p^2 \leq x \).

El hecho siguiente se conocía desde la antigüedad y aparece como la Proposición 20 del Libro IX de los Elementos de Euclides.

Teorema 1.25 (Euclides). Existen infinitos números primos.
Demostración: Lo probaremos por reducción al absurdo. Supongamos que, contrario a lo que afirma el teorema, existe un número finito de primos, digamos \( p_1,\ldots ,p_n \). Entonces \( x = p_1p_2p_3\cdots p_n + 1 \) es un entero que no es divisible por ninguno de los primos listados, pues cada uno de ellos divide al primer término y para dividir a \( x \) tendrían que dividir también al 1. Se sigue entonces que \( x \) es, o bien un número primo mayor que todos los listados, o bien, como explicamos en el párrafo anterior al teorema, tiene un divisor primo que no puede ser ninguno de los que hemos listado.

A la fecha en la que se escriben estas letras, el más grande de los números primos que se conoce es \[ 2^{82,589,933} - 1, \] consistente de \( 24,862,048 \) dígitos y encontrado en diciembre de 2018.

Como observábamos más arriba, todo número entero \(x\) mayor a la unidad tiene al menos un divisor primo. Se deduce entonces por inducción que \(x\) puede descomponerse como un producto de números primos. Esto incluye, por supuesto, el caso en que \(x\) es él mismo un número primo, pues ahí lo que tenemos es un producto de primos con \(x\) como su único factor. Más aún, podemos definir el producto vacío de enteros (un producto sin ningún factor) como la unidad, y así afirmar que

Proposición 1.26. Todo entero positivo es un producto de números primos.
Demostración: Sea \(x\) un entero positivo, y razonemos por inducción sobre \(x\). Si \(x = 1\), el teorema es cierto, pues se trata del producto vacío de primos. Supongamos el teorema cierto para todos los enteros menores o iguales a \(x\). Si \(x + 1\) es primo, no hay nada más que decir. Si no lo es, entonces es un producto \(ab\) de enteros tales que \(a,b > 1\), o sea que \(a,b < x + 1\) y por lo tanto \(a,b\leq x\), luego la hipótesis de inducción nos dice que \(a\) y \(b\) son primos o producto de primos, por lo que \(x + 1 = ab\) es un producto de primos.

Como el lector pudo haberlo supuesto ya, la factorización de un entero positivo en producto de números primos es única salvo el orden de los factores. La razón detrás de esta propiedad es esencialmente la siguiente.

Proposición 1.27 (Lema de Euclides). Si \(x\) y \(y\) son enteros y \(p\) es un número primo tal que \(p\mid xy\), entonces \(p\mid x\) o \(p\mid y\).
Demostración: Supongamos que \(p\mid xy\) y que \(p\nmid x\). Entonces \(\mcd {p,x} = 1\) pues \(p\) es primo, así que \(p\mid y\) por el teorema 1.22.

Observemos que el recíproco del lema de Euclides también es cierto: si un entero \(p\) satisface la propiedad enunciada en el lema para cualesquiera enteros \(x\) y \(y\), entonces \(p\) ha de ser un número primo. En efecto, pues si en tales condiciones tuviésemos \(p = xy\) con \(x > 1\), entonces \(p\mid x\) pero también \(x\mid p\), o sea que \(x = p\) y \(y = 1\), y por lo tanto \(p\) es primo.

Teorema 1.28 (Teorema Fundamental de la Artimética).  Todo entero positivo \(x\) admite una factorización en un producto de números primos. Además, esta factorización es única salvo el orden de los factores.
Demostración: Por la teorema 1.26, \(x\) puede escribirse como un producto \(p_1\cdots p_n\) de \(n \geq 0\) números primos. Supongamos que \(q_1\cdots q_m\) es otra factorización prima de \(x\) de \(m\) factores. Sin pérdida de generalidad, podemos asumir que \(n \geq m\). Demostraremos por inducción sobre \(n\) que \(m = n\) y que ambas factorizaciones consisten de los mismos factores. Para \(n=0\), \(x = 1\) y la afirmación es trivialmente cierta. Supongamos ahora el teorema cierto para todo entero que sea producto de \(n\geq 1\) primos. Si \(p_1\cdots p_{n+1} = q_1\cdots q_m\) son factorizaciones primas de \(x\), entonces el lema Euclides nos dice que \(p_{n+1}\) divide a alguno de los primos \(q_1,\ldots ,q_m\), lo que sólo puede ocurrir si \(p_{n+1}\) es uno de estos primos, digamos \(p_{n+1} = q_i\). Dividiendo ambas factorizaciones de \(x\) entre este número, tenemos que \[ p_1\cdots p_n = q_1\cdots q_{i-1}q_{i+1}\cdots q_{m-1}, \] y por hipótesis de inducción, ambos miembros consisten exactamente de los mismos factores. Por lo tanto, \(p_1\cdots p_{n+1}\) y \(q_1\cdots q_m\) son factorizaciones de \(x\) que difieren, cuando mucho, en el orden de los factores.

Se sigue entonces que todo entero \(x\) es de forma única un producto \[ p_1^{k_1}\cdots p_n^{k_n},\quad i = 1,\ldots ,n, \] de potencias de números primos distintos. A esta forma de representar a \(x\) la llamamos la factorización prima de \(x\). Si admitimos factores \(p^{k_i} = 1\) de exponentes nulos, la factorización deja de ser única, pues obviamente factores así pueden insertarse arbitrariamente en la factorización. No obstante, la inclusión de estos factores permite que en las factorizaciones primas de dos o más enteros intervengan los mismos números primos.

Proposición 1.29. Si \(x = p_1^{k_1}\cdots p_n^{k_n}\) es una factorización prima de \(x\), entonces los divisores de \(x\) son precisamente los productos \(p_1^{l_1}\cdots p_n^{l_n}\) tales que \(0 \leq l_i \leq k_i\) para todo \(i = 1,\ldots ,n\).
Demostración: Es claro que todo producto de esta forma es un divisor de \(x\). Recíprocamente, si \(d\) es un divisor de \(x\), entonces \(x = dq\) para cierto \(q\in \Z \). Considerando la factorización prima de cada entero en esa igualdad, el lema de Euclides nos dice que que los únicos primos que pueden aparecer en la factorización prima de \(d\) son \(p_1,\ldots ,p_n\), y esto mismo aplica para \(q\). Puesto que el exponente de \(p_i\) en la factorización prima de \(x\) es la suma de los exponentes (posiblemente nulos) que \(p_i\) tiene en las factorizaciones primas de \(d\) y \(q\), concluimos que \(d = p_1^{l_1}\cdots p_n^{l_n}\) con \(l_i \leq k_i\) para todo \(i=1,\ldots ,n\).

Insertando primos con exponentes nulos en caso de ser necesario, podemos hacer que en las factorizaciones primas de dos enteros aparezcan los mismos números primos. Esto nos permite enunciar una caracterización útil del máximo común divisor de enteros.

Proposición 1.30. Si \(x,y > 0\) son enteros con factorizaciones primas \(p_1^{k_1}\cdots p_n^{k_n}\) y \(p_1^{l_1}\cdots p_n^{l_n}\), respectivamente, entonces \[ \mcd {x,y} = p_1^{\min (k_1,l_1)}\cdots p_n^{\min (k_n,l_n)}. \]
Demostración: Sea \(d = p_1^{\min (k_1,l_1)}\cdots p_n^{\min (k_n,l_n)}\). Claramente \(d\) es un divisor común de \(x\) y \(y\). Si \(d'\) es otro divisor común de \(x\) y \(y\), entonces, por la proposición anterior, \(d'\) es de la forma \(p_1^{t_1}\cdots p_n^{t_n}\) con \(t_i\leq k_i,l_i\), por lo que \(d'\) divide a \(d\), lo que nos dice que \(d\) es el máximo común divisor de \(x\) y \(y\).
Definición 1.31. Si \(x\) y \(y\) son dos enteros positivos, el mínimo común múltiplo de \(x\) y \(y\) es el menor de los enteros que son múltiplos tanto de \(x\) como de \(y\).
Proposición 1.32. Si \(x\) y \(y\) son enteros positivos y \(p_1^{k_1}\cdots p_n^{k_n}\) y \(p_1^{l_1}\cdots p_n^{l_n}\) son, respectivamente, sus factorizaciones primas, entonces \[ \mcm {x,y} = p_1^{\max (k_1,l_1)}\cdots p_n^{\max (k_n,l_n)}. \]

La demostración de la proposición anterior se deja como ejercicio al lector.

Corolario 1.33. Los múltiplos comunes de dos enteros no nulos \(x\) y \(y\) son los múltiplos de \(\mcm {x,y}\).

De las proposiciones 1.30 y  1.32 se de duce la siguiente relación entre el máximo común divisor y el mínimo común múltiplo.

Proposición 1.34. Para cualesquiera enteros positivos \(x\) y \(y\), \[ xy = \mcd {x,y}\cdot \mcm {x,y}. \]
Demostración: El resultado se sigue de las proposiciones 1.30 y 1.32 y de que \(k + l = \min (k,l) + \max (k,l)\).

En particular, tenemos que \(\mcd {x,y} = 1\) si y sólo si \(\mcm {x,y} = xy\). De esto se deducen hechos como el siguiente:

Proposición 1.35. Si \(x,y,n\in \Z \) con \(\mcd {x,y} = 1\), entonces \(x\mid n\) y \(y\mid n\) si y sólo si \(xy\mid n\).
Demostración: La suficiencia es evidente. Para el recíproco se sigue de que \(xy = \mcm {x,y}\), y como \(n\) es un múltiplo común de \(x\) y \(y\), éste ha de ser divisible entre \(xy\) por el teorema 1.33.

[siguiente][anterior][arriba]