8.5: Aplicaciones en Teoría de Números

La inducción (o el hecho de que\(\mathbb{N}\) está bien ordenado) se puede utilizar para probar muchas propiedades importantes de los números naturales. Aquí solo hay tres ejemplos.

Definición\(8.5.1\).

Un elemento\(p\) de\(\mathbb{N}^{+}\) es primo iff\(p > 1\) y no\(p\) es divisible por ningún elemento\(\mathbb{N}^{+}\) distinto de 1 y\(p\).

Proposición\(8.5.2\).

Si\(n \in \mathbb{N}\) y\(n > 1\), entonces\(n\) es divisible por un número primo.

Prueba

Supongamos que hay algún número natural\(n > 1\), tal que no\(n\) sea divisible por un número primo. (Esto conducirá a una contradicción.) Dado que\(\mathbb{N}\) está bien ordenado, podemos suponer que\(n\) es el número más pequeño, por lo que:\[\text { If } 1<k<n \text { (and } k \in \mathbb{N} \text { ), then } k \text { is divisible by a prime number. }\]

Ya que\(n \mid n\), pero (por supuesto) no\(n\) es divisible por ningún número primo, sabemos que no\(n\) es primo. Por definición, esto significa que existe\(k \in \mathbb{N}\), tal que\(k \mid n\) y\(1 < k < n\). Desde la minimalidad de\(n\), sabemos que\(k\) es divisible por algún número primo\(p\). Entonces\(p \mid k\) y\(k \mid n\), entonces\(p \mid n\). Esto contradice el hecho de que no\(n\) es divisible por un número primo.

Teorema\(8.5.3\) (Fundamental Theorem of Arithmetic).

Cada número natural (que no sea 0 y 1) es un producto de números primos (o es en sí mismo un primo).

Prueba

POR CONTRADICION: Supongamos que hay algún número natural\(n > 1\), tal que no\(n\) es producto de números primos (y no es primo). Dado que\(\mathbb{N}\) está bien ordenado, podemos suponer que\(n\) es el número más pequeño, por lo que:\[\text { If } 1<k<n \text { (and } k \in \mathbb{N}), \text { then } k \text { is a product of prime numbers. }\]

Ya que no\(n\) es primo, es divisible por algún número natural\(k\), con\(1 < k < n\). Esto significa que podemos escribir\(n = km\), para algunos\(m \in \mathbb{N}^{+}\). Desde\(m = n / k\) y\(1 < k < n\), vemos eso\(1 < m < n\). Por lo tanto, la minimalidad de\(n\) implica que\(k\) y\(m\) son productos de números primos: decir\(k=p_{1} p_{2} \cdots p_{r}\) y\(m=q_{1} q_{2} \cdots q_{s}\). Entonces\[n=k m=\left(p_{1} p_{2} \cdots p_{r}\right)\left(q_{1} q_{2} \cdots q_{s}\right)\]

es un producto de números primos. Esto es una contradicción.

Comentario\(8.5.4\).

De hecho, cada número natural puede escribirse de una sola manera como producto de números primos (hasta reordenar el orden de los factores), pero no vamos a probar este hecho.

Definición\(8.5.5\).

Vamos\(a, b \in \mathbb{N}^{+}\). Decimos\(a\) y\(b\) son relativamente primos iff no tienen divisores en común, que no sean 1. (Es decir, si\(k \in \mathbb{N}^{+}\), y\(k\) es un divisor de ambos\(a\) y\(b\), entonces\(k = 1\). En otras palabras, el “mayor divisor común” de\(a\) y\(b\) es 1.)

Teorema\(8.5.6\).

Vamos\(a, b \in \mathbb{N}^{+}\). Si\(a\) y\(b\) son relativamente primos, entonces existen\(m, n \in \mathbb{Z}\), tal que\(ma + nb = 1\).

Prueba

Let\[S=\{m a+n b \mid m, n \in \mathbb{Z} k=\} \cap \mathbb{N}^{+} .\]

Es fácil ver eso\(a \in S\) (por dejar\(m = 1\) y\(n = 0\)), entonces\(S \neq \varnothing\). Por lo tanto, dado que\(\mathbb{N}\) está bien ordenado, podemos dejar que\(d\) sea el elemento más pequeño de\(S\). Entonces\(d \in S\), así tenemos\(d = m_{0}a+n_{0}b\) para algunos\(m_{0}, n_{0} \in \mathbb{Z}\).

Por el Algoritmo de División\((5.1.20)\), podemos escribir\[a=q d+r \text { with } 0 \leq r<d .\]

Entonces\[r=a-q d=a-q\left(m_{0} a+n_{0} b\right)=\left(1-q m_{0}\right) a+q n_{0} b=m a+n b ,\]

dónde\(m = 1 − qm \in \mathbb{Z}\) y\(n = qn \in \mathbb{Z}\). Por otro lado, ya que\(r < d\), y\(d\) es el elemento más pequeño de\(S\), sabemos\(r \notin S\). De la definición de\(S\), concluimos que\(r = 0\). Entonces\(d \mid a\).

Al repetir el mismo argumento con\(a\)\(b\) e intercambiado (\(m_{0}\)y\(n_{0}\) también intercambiado) vemos eso\(d \mid b\).

Por lo tanto,\(d\) es un divisor de ambos\(a\) y\(b\). Dado que\(a\) y\(b\) son relativamente primos, concluimos que\(d = 1\). Ya que\(d \in S\), esto significa\(1 \in S\), que establece la conclusión deseada.

Ejercicio\(8.5.7\).

Demostrar lo contrario del Teorema\(8.5.6\).

El teorema\(8.5.6\) es de fundamental importancia en la Teoría de Números, el estudio matemático de las propiedades de\(\mathbb{N}\) y\(\mathbb{Z}\). Estas son algunas de sus muchas consecuencias:

Ejercicio\(8.5.8\).

Asumir\(a, b \in \mathbb{N}^{+}\).

1. Mostrar\(a\) y\(b\) son relativamente primos si existe\(x \in \mathbb{Z}\), tal que\(x a \equiv 1(\bmod b)\).
2. Mostrar\(a\) y\(b\) son relativamente prime iff para todos\(y \in \mathbb{Z}\), existe\(x \in \mathbb{Z}\), tal que\(x a \equiv y(\bmod b)\).
3. (Teorema del resto chino) Supongamos\(a\) y\(b\) son relativamente primos. Para todos\(y_{1}, y_{2} \in \mathbb{Z}\), muestran que existe\(x \in \mathbb{Z}\), tal que\(x \equiv y_{1}(\bmod a)\) y\(x \equiv y_{2}(\bmod b)\).

La proposición\(8.5.2\) también tiene consecuencias importantes. Por ejemplo:

Corolario\(8.5.9\).

Hay infinitamente muchos números primos.

Prueba

POR CONTRADICCIÓN: Supongamos que sólo hay finitamente muchos números primos. Entonces podemos hacer una lista de todos ellos:\[\text { The set of all prime numbers is }\left\{p_{1}, p_{2}, \ldots, p_{n}\right\} .\]

Let\[N=p_{1} p_{2} \cdots p_{n} .\]

De la Proposición\(8.5.2\), sabemos que hay alguna prima\(p\), tal que\(p \mid (N + 1)\).

Ya que\(p_{1}, p_{2}, \ldots, p_{n}\) es una lista de todos los números primos, sabemos\(p = p_{i}\), para algunos\(i\). Por lo tanto\(p = p_{i}\) es uno de los factores en el producto que define\(N\), así\(p \mid N\). Por lo tanto,\(p\) divide ambos\(N\) y\(N + 1\), así (de\(5.1.9(1)\)) tenemos\[p \mid((N+1)-N)=1 .\]

Esto implica\(p = \pm 1\) (ver página 97), lo que contradice el hecho de que\(p\), al ser un número primo, debe serlo\(> 1\).