5.1: Teoría de números- Divisibilidad y Congruencia

En esta sección, obtendremos algo de práctica para probar propiedades de enteros.

5.1A. Divisibilidad.

Todo estudiante de matemáticas sabe que algunos números son pares y algunos números son impares; algunos números son divisibles por 3, y algunos no lo son; etc. Introducimos una notación que facilite hablar sobre si un número\(b\) es o no divisible por otro número\(a\):

Definición\(5.1.1\).

Supongamos\(a, b \in \mathbb{Z}\). Decimos que\(a\) es un divisor de\(b\) (y escribimos “\(a \mid b\)”) si existe\(k \in \mathbb{Z}\), tal que\(ak = b\). (Dado que la multiplicación es conmutativa y la igualdad es simétrica, esta ecuación también se puede escribir como\(b = ka\).)

Notación\(5.1.2\).

\(a \nmid b\)es una abreviatura de “\(a\)no divide”\(b\).

Observación\(5.1.3\).

Cuando\(a\) es un divisor de\(b\), también podemos decir:

1. \(a\)divide\(b\), o
2. \(a\)es un factor de\(b\), o
3. \(b\)es un múltiplo de\(a\), o
4. \(b\)es divisible por\(a\).

Ejemplo\(5.1.4\).

1. Tenemos\(5 \mid 30\), porque\(5 \cdot 6=30\), y\(6 \in \mathbb{Z}\).
2. Tenemos\(5 \nmid 27\), porque no hay entero\(k\), tal que\(5k = 27\).

Ejercicio\(5.1.5\).

Llene cada pieza en blanco con\(\mid\) o\(\nmid\), según corresponda.

1. 3________18
2. 4________18
3. 5________18
4. 6________18
5. 18________6
6. −6________6

La siguiente definición es quizás el ejemplo más conocido de divisibilidad.

Definición\(5.1.6\).

Vamos\(n \in \mathbb{Z}\). Decimos que\(n\) es par iff\(2 \mid n\). Decimos que\(n\) es extraño iff\(2 \nmid n\).

Aquí hay algunos ejemplos de pruebas que involucran la divisibilidad. Asumiremos el hecho bien conocido de que la suma, diferencia y producto de los enteros son enteros: para todos\(k_{1}, k_{2} \in \mathbb{Z}\), lo sabemos\(k_{1}+k_{2} \in \mathbb{Z}, k_{1}-k_{2} \in \mathbb{Z}\), y\(k_{1} k_{2} \in \mathbb{Z} .\) también, el negativo de cualquier entero es un entero: para todos\(k \in \mathbb{Z}\), tenemos\(−k \in \mathbb{Z}\).

Nuestro primer resultado es una generalización del hecho bien conocido de que la suma de dos números pares es par.

Proposición\(5.1.7\).

Supongamos\(a, b_{1}, b_{2} \in \mathbb{Z}\). Si\(a \mid b_{1}\) y\(a \mid b_{2}\), entonces\(a \mid\left(b_{1}+b_{2}\right)\).

Scratchwork. Desde\(a \mid b_{1}\) y\(a \mid b_{2}\), sabemos que hay algunos\(k \in \mathbb{Z}\), tal que\(ak = b_{1}\), y sabemos que hay algunos\(k \in \mathbb{Z}\), tales que\(ak = b_{2}\). Sin embargo, estos son probablemente dos valores diferentes de\(k\), por lo que necesitamos darles nombres diferentes si queremos hablar de ambos al mismo tiempo. Entonces llamemos al primero\(k_{1}\) y al segundo\(k_{2}\):

• existe\(k_{1} \in \mathbb{Z}\), tal que\(a k_{1}=b_{1}\), y
• existe\(k_{2} \in \mathbb{Z}\), tal que\(a k_{2}=b_{2}\).

Para mostrar\(a \mid\left(b_{1}+b_{2}\right)\), queremos encontrar algunos\(k \in \mathbb{Z}\), tales que\[a k \stackrel{?}{=} b_{1}+b_{2} .\]
Desde\(b_{1}+b_{2}=a k_{1}+a k_{2}=a\left(k_{1}+k_{2}\right)\), esto significa que queremos\[a k \stackrel{?}{=} a\left(k_{1}+k_{2}\right) .\]
Así que está claro que debemos dejar\(k = k_{1} + k_{2}\).

Prueba

Ya que, por supuesto, a es un divisor de ambos\(b_{1}\) y\(b_{2}\), existen\(k_{1}, k_{2} \in \mathbb{Z}\), tal que\(a k_{1}=b_{1}\) y\(a k_{2}=b_{2}\). Vamos\(k = k_{1} + k_{2}\). Entonces\(k \in \mathbb{Z}\) y\[a k=a\left(k_{1}+k_{2}\right)=a k_{1}+a k_{2}=b_{1}+b_{2} ,\]

así\(a\) es un divisor de\(b_{1} + b_{2}\), según se desee.

Proposición\(5.1.8\).

Supongamos\(a, b \in \mathbb{Z}\). Tenemos\(a \mid b\) iff\(a \mid −b\).

Scratchwork.

(\(\Rightarrow\)) Ya que\(a \mid b\), sabemos que hay algunos\(k\), tal que\(ak = b\). Para mostrar\(a \mid −b\), queremos encontrar algún otro\(k\) —llamémoslo\(k^{\prime}\) — tal que\(a k^{\prime} \stackrel{?}{=}-b\). Ya que\(-b=-(a k)=a(-k)\), esto significa que queremos\(a k^{\prime} \stackrel{?}{=} a(-k)\). Entonces debemos dejar\(k^{\prime} = −k\).

(\(\Leftarrow\)) Ya que\(a \mid −b\), sabemos que hay algunos\(k\), tal que\(ak = −b\). Para mostrar\(a \mid b\), queremos encontrar algunos\(k^{\prime}\), tal que\(a k^{\prime} \stackrel{?}{=} b .\) desde\(−b = ak\), tenemos\(b = −(ak) = a(−k)\), así podemos dejar\(k^{\prime} = −k\). Este es el mismo trabajo que en la prueba de (\(\Rightarrow\)), y la prueba oficial que se da a continuación evita la necesidad de repetir este álgebra, apelando al resultado que ya hemos probado.

Prueba

(\(\Rightarrow\)) Por supuesto, hay algunos\(k \in \mathbb{Z}\), tales que\(ak = b\). Entonces\(−k \in \mathbb{Z}\), y tenemos\(a(−k) = −ak = −b\), Por lo tanto,\(a\) divide\(−b\).

(\(\Leftarrow\)) Asumir\(a \mid −b\). Del párrafo anterior, concluimos que\(a \mid −(−b) = b\), según se desee.

Ejercicio\(5.1.9\).

Asumir\(a, a^{\prime} , b, b^{\prime} \in \mathbb{Z}\).

1. \(a \mid b\)Demuéstralo si y\(a \mid b^{\prime}\), entonces\(a \mid b - b^{\prime}\).
2. Demuestre que\(a \mid b\) iff\(−a \mid b\).
3. Espectáculo\(1 \mid b\).
4. Espectáculo\(a \mid 0\).
5. Demuéstralo si\(0 \mid b\), entonces\(b = 0\).
6. Demuéstralo si\(a \mid b\), entonces\(a | bb^{\prime}\).
7. \(a \mid b\)Demuéstralo si y\(a^{\prime} \mid b^{\prime}\), entonces\(a a^{\prime} \mid b b^{\prime}\).

Proposición\(5.1.10\).

Supongamos\(a, b_{1}, b_{2} \in \mathbb{Z}\). Si\(a \mid b_{1}\) y\(a \nmid b_{2}\), entonces\(a \nmid\left(b_{1}+b_{2}\right)\).

Prueba

Asumir\(a \mid b_{1}\) y\(a \nmid b_{2}\).

Supongamos\(a \mid\left(b_{1}+b_{2}\right)\). (Esto conducirá a una contradicción.) Entonces\(a\) es un divisor de ambos\(b_{1} +b_{2}\) y (por suposición)\(b_{1}\). Entonces el ejercicio nos\(5.1.9(1)\) dice\[a \mid\left(\left(b_{1}+b_{2}\right)-b_{1}\right)=b_{2}\]
Esto contradice la suposición de que\(a \nmid b_{2}\).

Porque lleva a una contradicción, nuestra hipótesis que\(a \mid\left(b_{1}+b_{2}\right)\) debe ser falsa. Esto significa\(a \nmid\left(b_{1}+b_{2}\right) .\)

Es bien sabido que 1 y −1 son los únicos enteros cuyo recíproco es también un entero. En el lenguaje de la divisibilidad, esto puede reafirmarse como el siguiente dato útil:\[\text { For any integer } n \text {, we have } n \mid 1 \text { iff } n=\pm 1 \text {. }\]

Ejercicio\(5.1.11\).

Demostrar:

1. Para todos\(a \in \mathbb{Z}\), tenemos\(a \mid a\).
2. Para todos\(a, b, c \in \mathbb{Z}\), si\(a \mid b\) y\(b \mid c\), entonces\(a \mid c\).
3. No es cierto que, para todos\(a, b \in \mathbb{Z}\), tenemos\(a \mid b\) iff\(b \mid a\).

Observación\(5.1.12\).

Las tres partes del ejercicio anterior muestran que la divisibilidad es “reflexiva” y “transitiva”, pero no “simétrica”. Estos términos se definirán en Definición\(7.1.9\).

Ejercicio\(5.1.13\).

Asumir\(a, b, x, y \in \mathbb{Z}\). Demostrar:

1. Si\(a \mid x\) y\(b \mid y\), entonces\(ab \mid 2xy\).
2. Si\(a, b \in \mathbb{N}^{+}\), y\(a \mid b\), entonces\(a \leq b\).

Ejercicio\(5.1.14\).

Demostrar o desacreditar cada aseveración.

1. Para todos\(a, b_{1}, b_{2} \in \mathbb{Z}\), si\(a \nmid b_{1}\) y\(a \nmid b_{2}\), entonces\(a \nmid\left(b_{1}+b_{2}\right)\).
2. Para todos\(a, b_{1}, b_{2} \in \mathbb{Z}\), si\(a \nmid b_{1}\) y\(a \nmid b_{2},\), entonces\(a \nmid b_{1} b_{2}\).
3. Para todos\(a, b, c \in \mathbb{Z} \text {, }\) si\(a \nmid b\) y\(b \nmid c\), entonces\(a \nmid c\).
4. Para todos\(a, b \in \mathbb{Z}\), si\(a \nmid b\), entonces\(a \nmid −b\).

5.1B. Módulo de congruencia\(n\).

Definición\(5.1.15\).

Supongamos\(a, b, n \in \mathbb{Z}\). Decimos que\(a\) es congruente con el\(b\) módulo\(n\) iff\(a − b\) es divisible por\(n\). La notación para esto es:\(a \equiv b(\bmod n)\).

Ejemplo\(5.1.16\).

1. Tenemos\(22 \equiv 0(\bmod 2)\), porque\(22 − 0 = 22 = 11 \times 2\) es un múltiplo de 2. (De manera más general, para\(a \in \mathbb{Z}\), se puede demostrar que el\(a \equiv 0 (\bmod 2)\) iff\(a\) es parejo.)
2. Tenemos\(15 \equiv 1 (\bmod 2)\), porque\(15 − 1 = 14 = 7 \times 2\) es un múltiplo de 2. (De manera más general, para\(a \in \mathbb{Z}\), se puede demostrar que\(a \equiv 1 (\bmod 2)\) iff\(a\) es impar.)
3. Tenemos\(28 \equiv 13 (\bmod 5)\), porque\(28 − 13 = 15 = 3 \times 5\) es un múltiplo de 5.
4. Para cualquiera\(a, n \in \mathbb{Z}\), no es difícil ver que\(a \equiv 0 (\bmod n)\) iff\(a\) es un múltiplo de\(n\).

Ejercicio\(5.1.17\).

Llene cada pieza en blanco con\(\equiv\) o\(\not \equiv\), según corresponda.

1. 14______5\((\bmod 2)\)
2. 14______5\((\bmod 3)\)
3. 14______5\((\bmod 4)\)
4. 14______32\((\bmod 2)\)
5. 14______32\((\bmod 3)\)
6. 14______32\((\bmod 4)\)

Ejercicio\(5.1.18\).

(“El módulo de congruencia\(n\) es reflexivo, simétrico y transitivo.”) Vamos\(n \in \mathbb{Z}\). Demostrar:

1. Para todos\(a \in \mathbb{Z}\), tenemos\(a \equiv a (\bmod n)\).
2. Para todos\(a, b \in \mathbb{Z}\), tenemos\(a \equiv b (\bmod n)\) iff\(b \equiv a (\bmod n)\).
3. Para todos\(a, b, c \in \mathbb{Z}\), si\(a \equiv b (\bmod n)\) y\(b \equiv c (\bmod n)\), entonces\(a \equiv c (\bmod n)\).

Ejercicio\(5.1.19\).

Asumir\(a_{1} \equiv a_{2} (\bmod n)\) y\(b_{1} \equiv b_{2} (\bmod n)\). Mostrar:

1. \(a_{1}+b_{1} \equiv a_{2}+b_{2}(\bmod n)\).
2. \(a_{1}-b_{1} \equiv a_{2}-b_{2}(\bmod n)\).
3. \(a_{1} b_{1} \equiv a_{2} b_{2}(\bmod n)\). [Pista:\(a_{1} b_{1}-a_{2} b_{2}=a_{1}\left(b_{1}-b_{2}\right)+\left(a_{1}-a_{2}\right) b_{2}\).]

A los niños se les enseña que si un número\(a\) se divide por un número\(n\), entonces puede haber un resto, pero el resto siempre es menor que\(n\). Esa idea se dice más precisamente en el siguiente teorema:

Teorema\(5.1.20\) (Division Algorithm).

Supongamos\(a, n \in \mathbb{Z}\), y\(n \neq 0\). Entonces existen enteros únicos\(q\) y\(r\) en\(\mathbb{Z}\), tal que:

1. \(a = qn + r\), y
2. \(0 \leq r < |n|\).

Definición\(5.1.21\).

En la situación del Teorema\(5.1.20\), el número\(r\) se llama el resto cuando\(a\) se divide por\(n\).

El siguiente ejercicio revela la estrecha relación entre congruencia y restos.

Ejercicio\(5.1.22\).

Supongamos\(a, b, n \in \mathbb{Z}\) (y\(n \neq 0\)).

1. Dejar\(r\) ser el resto cuando\(a\) se divide por\(n\). Espectáculo\(a \equiv r (\bmod n)\).
2. Demostrar que\(a \equiv b (\bmod n)\) iff\(a\) y\(b\) tener el mismo resto cuando se divide por\(n\).

Observación\(5.1.23\).

A partir de la segunda mitad de las partes (1) y (2) del Ejemplo\(5.1.16\), vemos que cada entero es congruente con 0 o 1 módulo 2 (y no con ambos).

\(n\)es parejo iff\(n \equiv 0 (\bmod 2)\).
\(n\)es impar iff\(n \equiv 0 (\bmod 2)\).

El ejercicio\(5.1.22(1)\) generaliza esto a congruencia módulo números distintos de 2: si\(n \equiv \mathbb{N}^{+}\), entonces cada entero es congruente (módulo\(n\)) a algún número en\(\{0,1,2, \ldots, n-1\}\).

Ejemplo\(5.1.24\).

Demostremos que si\(n\) es impar, entonces también\(9n+ 6\) es impar. Para ver esto, tenga en cuenta que:

• \(9 \equiv 1 (\bmod 2)\), porque\(9 = 4(2) + 1\),
• \(n \equiv 1 (\bmod 2)\), porque\(n\) es extraño, y
• \(6 \equiv 0 (\bmod 2)\), porque\(6 = 3(2) + 0\).

Por lo tanto, usando Ejercicio\(5.1.19\), tenemos\(9n + 6 \equiv (1)(1) + 0 \equiv 1 (\bmod 2)\).

El mismo método se puede aplicar en los siguientes ejercicios:

Ejercicio\(5.1.25\).

Vamos\(n \in \mathbb{Z}\).

1. \(6n + 3\)El espectáculo es impar.
2. Demuestre que si\(n\) es par, entonces\(5n + 3\) es impar.
3. Demostrar que si\(n\) es impar, entonces\(5n + 3\) es par.

Proposición\(5.1.26\).

Vamos\(n \in \mathbb{Z}\). Entonces\(n^{2} + n\) es parejo.

Prueba

De Remark\(5.1.23\), sabemos que\(n\) es congruente con 0 o 1 módulo 2. Consideramos estas dos posibilidades como casos separados.

Caso 1. Asumir\(n \equiv 0 (\bmod 2)\). Por el supuesto de este caso, tenemos\(n = 2q\), para algunos\(q \in \mathbb{Z}\). Por lo tanto\[n^{2}+n=(2 q)^{2}+2 q=4 q^{2}+2 q=2\left(2 q^{2}+q\right)\]
es divisible por 2.

Caso 2. Asumir\(n \equiv 1 (\bmod 2)\). Por el supuesto de este caso, tenemos\(n = 2q + 1\), para algunos\(q \in \mathbb{Z}\). Por lo tanto\[n^{2}+n=(2 q+1)^{2}+(2 q+1)=\left(4 q^{2}+4 q+1\right)+(2 q+1)=4 q^{2}+6 q+2=2\left(2 q^{2}+3 q+1\right)\]
es divisible por 2.

Ejercicio\(5.1.27\).

Vamos\(n \in \mathbb{Z}\).

1. Demuestre que si\(n\) es par, entonces\(n^{2} \equiv 0 (\bmod 4)\). [Pista: Tenemos\(n = 2q\), para algunos\(q \in \mathbb{Z}\).]
2. Mostrar que si\(n\) es impar, entonces n 2 ≡ 1 (mod 8). [Pista: Tenemos n = 2q + 1, para algunos q ∈ Z.]
3. Demuestre que si\(n^{2}\) es par, entonces\(n\) es par.

5.1C. Ejemplos de números irracionales.

Todo número racional es un número real (en otras palabras,\(\mathbb{Q} \subset \mathbb{R}\)), pero quizás no sea tan obvio que algunos números reales no sean racionales (en otras palabras,\(\mathbb{R} \not \subset \mathbb{Q}\)). Se dice que tales números son irracionales. Damos ahora uno de los ejemplos más simples de un número irracional.

Proposición\(5.1.28\).

\(\sqrt{2}\)es irratioinal.

Prueba

POR CONTRADICCIÓN.

Supongamos que\(\sqrt{2}\) es racional. (Esto conducirá a una contradicción.) Por definición, esto significa\(\sqrt{2}=a / b\) para algunos\(a, b \in \mathbb{Z}\), con\(b \neq 0\). Al reducir a los términos más bajos, podemos suponer eso\(a\) y no\(b\) tener factores comunes. En particular,\[\text { it is not the case that both } a \text { and } b \text { are even. }\]
tenemos\[\frac{a^{2}}{b^{2}}=\left(\frac{a}{b}\right)^{2}=\sqrt{2}^{2}=2 ,\]
así\(a^{2}=2 b^{2}\) es parejo. Entonces Ejercicio nos\(5.1.27(3)\) dice que\[a \text { is even, }\]
así tenemos\(a = 2k\), para algunos\(k \in \mathbb{Z}\). Entonces\[2 b^{2}=a^{2}=(2 k)^{2}=4 k^{2} ,\]
así\(b^{2} = 2k^{2}\) es parejo. Entonces Ejercicio nos\(5.1.27(3)\) dice que Ahora\[b \text { is even. }\]
hemos demostrado eso\(a\) y\(b\) estamos parejos, pero esto contradice el hecho, mencionado anteriormente, de que no es el caso de que ambos\(a\) y\(b\) sean parejos.

Ejercicio\(5.1.29\).

1. Para\(n \in \mathbb{Z}\), demuéstralo si\(3 \nmid n\), entonces\(n^{2} \equiv 1(\bmod 3)\).
2. Demostrar que\(\sqrt{3}\) es irracional.
3. ¿Es\(\sqrt{4}\) irracional?

Observación\(5.1.30\).

Los números famosos\(\pi=3.14159 \ldots\) y también\(e=2.71828 \ldots\) son irracionales, pero estos ejemplos son mucho más difíciles de probar que la Proposición\(5.1.28\).