Divisibilidad
Dados dos enteros \(x\) e \(y\) decimos que \(y\) dvidide a \(x\) \((y \mid x)\),
si \(x = y \cdot q, \;q \in \mathbb{Z}\).
Si \(x\) es divisible por \(y\), entonces \(x\) es un múltiplo de \(y\).
Propiedades básicas divide a
Sean \(a, b, c \in \mathbb{Z}\), entonces:
1) \(1 \mid a\)
\[\begin{aligned} a &= 1 \cdot a \\ a &= a \cdot 1 \\ -a &= a \cdot (-1) \end{aligned} \]2) \(a \mid 0\) y solo \(0 \mid 0\)
\[\begin{aligned} 0 &= a \cdot 0 \\ 0 \mid a &\implies a = 0 \cdot q = 0 \end{aligned} \]3) Si \(a \mid b \implies a \mid bc\)
\[\begin{aligned} a \mid b &\implies b = a \cdot q \\ bc = a \cdot qc &\implies a \mid bc \end{aligned} \]4) Si \(a \mid b \; \land \; a \mid (b + c)\)
\[\begin{aligned} &a \mid b \land a \mid c \implies b = a \cdot q \land c = a \cdot q' \\ &b + c = a \cdot q + a \cdot q' = a(q + q') \implies a \mid (b + c) \end{aligned} \]5) Si \(a \mid b \; \land \; a \mid c \implies a \mid (rb + sc) \; \forall r, s \in \mathbb{Z}\)
\[\begin{aligned} &a \mid b \land a \mid c \implies b = a \cdot q \land c = a \cdot q' \\ &rb + sc = a \cdot rq + a \cdot sq' = a(rq + sq') \implies a \mid (rb + sc) \end{aligned} \]6) Si \(a \mid b + c \; \land \; a \mid c \implies a \mid b\)
\[\begin{aligned} &a \mid b + c \land a \mid c \implies b + c = a \cdot q \land c = a \cdot q' \\ &b = (b + c) - c = a \cdot q - a \cdot q' = a(q - q') \implies a \mid b \end{aligned} \]7) Si \(a \mid b \implies \pm a \mid \pm b\)
\[\begin{aligned} a &\mid b \implies b = a \cdot q \\ -b &= a \cdot (-q) \implies a \mid -b \\ -b &= -a \cdot q \implies -a \mid -b \\ b &= -a \cdot (-q) \implies -a \mid b \\ \end{aligned} \]D1) \(a \mid a\) (Reflexividad)
D2) \(a \mid b \land b \mid a \implies a = b\) (Antisimetría)
D3) \(a \mid b \land b \mid c \implies a \mid c\) (Transitividad)
Algoritmo de la división
\[a = b \cdot q + r , \;0 \leq r < b \]Sean \(a \in \mathbb{Z}\) y \(b \in \mathbb{N}\) existen enteros únicos \(q\) y \(r\) tales que:
Donde \(q\) es el cociente y \(r\) es el resto de dividir \(b\) por \(a\).
Ejemplo:
\[\begin{aligned} a &= 13, \;b = 5 \\ 13 &= 5 \cdot 2 + 3 \end{aligned} \]Ejercicios resueltos - Algoritmo de la división
1.
Dado \(m \in \mathbb{N}\) hallar los restos posibles de \(m^2\) y \(m^3\) en la división por \(3\).
El primer paso es dividir \(m\) por \(3\) usando el algoritmo:
\[m = 3 \cdot q + r, \;0 \leq r < 3, r \in \{0, 1, 2\} \]Para \(m^2\):
\[m^2 = (3 \cdot q + r)^2 \]Ahora expandimos y aplicamos factor común de \(3\):
\[3 \cdot q^2 + 3 \cdot 2qr + r^2 = 3 \cdot (q^2 + 2qr) + r^2 \]El resto de dividir \(m^2\) por \(3\) es \(r^2\). Ahora podemos calcular los restos posibles de \(m^2\)
\[\begin{align*} 0 \leq r < 3 &\implies 0 \leq r^2 < 3, \;r^2 \in \{0, 1\} \\ \end{align*} \]Desarrollos en base b
\[x = r_n 10^n + r_{n-1} 10^{n-1} + \ldots + r_1 10+ r_0 \]Todo natural \(x\) se puede expresar como:
Donde \(r_n \neq 0\) y \(0 \leq r_i < 10\).
\(x\) se representa como \((r_n r_{n-1} \ldots r_1 r_0)_{10}\).
Ejemplo:
Si queremos escribir el número \(407\) de la siguiente forma (base \(5\)):
\[407 = r_n 5^n + r_{n-1} 5^{n-1} + \ldots + r_1 5 + r_0 \]Con \(0 \leq r_i < 5\) lo podemos hacer de forma algorítmica:
Necesitamos dividir el número original y los sucesivos cocientes por \(5\):
\[\begin{align*} 407 &= 5 \cdot 81 + 2 \; (1) \\ 81 &= 5 \cdot 16 + 1 \; (2) \\ 16 &= 5 \cdot 3 + 1 \; (3) \\ 3 &= 5 \cdot 0 + 3 \; (4) \end{align*} \]Y ahora reemplazamos los valores de los cocientes:
\[\begin{align*} 407 &= 5 \cdot 81 + 2 \; (1) \\ &= 5 \cdot (5 \cdot 16 + 1) + 2 \; (2) \\ &= 5^2 \cdot 16 + 5 + 2 \; \\ &= 5^2 \cdot (5 \cdot 3 + 1) + 5 + 2 \; (3) \\ &= 5^3 \cdot 3 + 5^2 \cdot 1 + 5 \cdot 1 + 2 \; \\ \end{align*} \]Por lo que el número \(407\) en base \(5\) sería \((3112)_5\).
Conversiones de base
Podemos calcular la conversión de un número de base \(b\) a base \(10\).
Ejemplo:
Convertir \((1304)_6\) a base \(10\):
\[\begin{align*} (1304)_6 &= 1 \cdot 6^3 + 3 \cdot 6^2 + 0 \cdot 6^1 + 4 \cdot 6^0 \\ &= 1 \cdot 216 + 3 \cdot 36 + 0 \cdot 6 + 4 \cdot 1 \\ &= 216 + 108 + 0 + 4 \\ &= 328 \end{align*} \]Si quisieramos convertir \((1304)_6\) a otra base (por ejemplo, \(5\)), primero lo convertimos a base \(10\) y luego a la base deseada.
Ejercicios resueltos - Desarrollos en base b y conversiones de base
1.
Convertir \((1011)_2\) a base \(10\):
\[(1011)_2 = 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 8 + 0 + 2 + 1 = 11 \]2.
Convertir \((B38)_{16}\) a base \(8\):
Para resolver este ejercicio, primero necesitamos saber que los números en base \(16\) son \(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F\). Sabiendo esto, necesitamos convertirlo a base \(10\) y luego a base \(8\).
\[(B38)_{16} = 11 \cdot 16^2 + 3 \cdot 16^1 + 8 \cdot 16^0 = 2816 + 48 + 8 = 2872 \]Ahora convertimos \(2872\) a base \(8\):
\[\begin{align*} 2872 &= 8 \cdot 359 + 0 \; (1) \\ 359 &= 8 \cdot 44 + 7 \; (2) \\ 44 &= 8 \cdot 5 + 4 \; (3) \\ 5 &= 8 \cdot 0 + 5 \; (4) \end{align*} \]Podemos decir que \((B38)_{16} = (5470)_8\).
Máximo común divisor (mcd)
Sean \(a, b \in \mathbb{Z}\) alguno de ellos no nulo, denotamos \(\textnormal{mcd}(a, b)\) o \((a, b)\) al máximo común divisor entre \(a\) y \(b\).
Propiedades del mcd
1) \(\textnormal{mcd}(a, b) = \textnormal{mcd}(b, a) = \textnormal{mcd}(\pm a, \pm b)\)
2) \(a > 0,\;\textnormal{mcd}(a,0) = a,\;\textnormal{mcd}(a, a) = a\)
3) \(\textnormal{mcd}(1, b) = 1\)
4) \(\textnormal{mcd}(a, b) = \textnormal{mcd}(a, b - a)\)
Algoritmo de Euclides
Sean \(a, b \in \mathbb{Z}\), con \(b \neq 0\), entonces:
\(a = bq + r \rightarrow \textnormal{mcd}(a, b) = \textnormal{mcd}(b, r)\)
Ejemplo:
Encontrar el \(\textnormal{mcd}(174, 72)\)
\[\begin{align} &174 = 72 \cdot 2 + 30 \implies \textnormal{mcd}(174, 72) = \textnormal{mcd}(72, 30) \\ &72 = 30 \cdot 2 + 12 \implies \textnormal{mcd}(72, 30) = \textnormal{mcd}(30, 12) \\ &30 = 12 \cdot 2 + 6 \implies \textnormal{mcd}(30, 12) = \textnormal{mcd}(12, 6) \\ &12 = 6 \cdot 2 + 0 \implies \textnormal{mcd}(12, 6) = \textnormal{mcd}(6, 0) = 6 \end{align} \]Por lo tanto, \(\textnormal{mcd}(174, 72) = 6\).
Notemos que:
\[\begin{align} &\textnormal{mcd}(72, 174) = (72, 174 - 72) = (72, 102) \\ &\textnormal{mcd}(72, 102) = (72, 102 - 72) = (72, 30) \\ &\textnormal{mcd}(30, 72) = (30, 72 - 30) = (30, 42) \\ &\textnormal{mcd}(30, 42) = (30, 42 - 30) = (30, 12) \\ &\textnormal{mcd}(12, 30) = (12, 30 - 12) = (12, 18) \\ &\textnormal{mcd}(12, 18) = (12, 18 - 12) = (12, 6) \\ &\textnormal{mcd}(6, 12) = (6, 12 - 6) = (6, 6) = 6 \end{align} \]Tenemos la propiedad de que \(\textnormal{mcd}(a, b) = \textnormal{mcd}(a, b - a)\)
Ejemplo 2:
Encontrar el \(\textnormal{mcd}(174, 72)\) y escribir \(d = s \cdot 174 + t \cdot 72\)
\[\begin{align*} 174 = 72 \cdot 2 + 30 &\implies 30 = 174 - 72 \cdot 2 \; (1) \\ 72 = 30 \cdot 2 + 12 &\implies 12 = 72 - 30 \cdot 2 \; (2) \\ 30 = 12 \cdot 2 + 6 &\implies 6 = 30 - 12 \cdot 2 \; (3) \\ 12 = 6 \cdot 2 + 0 \end{align*} \]Sabemos que \(\textnormal{mcd}(174, 72) = 6\), por lo que podemos reemplazar los valores de los restos:
\[\begin{align*} 6 &= 30 - 12 \cdot 2 \; (3) \\ &= 1 \cdot 30 - 2 \cdot (72 - 30 \cdot 2) \; (2) \\ &= 1 \cdot 30 + (-2) \cdot 72 + 4 \cdot 30 \\ &= 5 \cdot 30 + (-2) \cdot 72 \\ &= 5 \cdot (174 - 72 \cdot 2) + (-2) \cdot 72 \\ &= 5 \cdot 174 + (-10) \cdot 72 + (-2) \cdot 72 \\ &= 5 \cdot 174 + (-12) \cdot 72 \end{align*} \]Por lo que \(d = 6, \;s = 5, \;t = -12\).
Mínimo común múltiplo (mcm)
Si \(a, b \in \mathbb{Z}\), alguno de ellos no nulo, denotamos \(\textnormal{mcm}(a, b)\) al mínimo común múltiplo entre \(a\) y \(b\).
La forma de calcularlo es:
\[\textnormal{mcm}(a, b) = \frac{|ab|}{\textnormal{mcd}(a, b)} \]Si \(a\) y \(b\) son naturales coprimos, entonces \(\; \textnormal{mcd}(a, b) = 1 \; \land \; \textnormal{mcm}(a, b) = ab\)
Reglas de divisibilidad
Existen reglas o patrones determinados que nos permiten saber si un número es divisible por otro. Algunos de los mas utilizados son:
-
Un número es divisible por \(2\) si su última cifra es par.
-
Un número es divisible por \(3\) si la suma de sus cifras es divisible por \(3\).
-
Un número es divisible por \(4\) si termina en \(00\) o es divisible por \(4\).
-
Un número es divisible por \(5\) si termina en \(5\) o \(0\)
-
Un número es divisible por \(6\) si la suma de sus cifras es divisible por \(2\) y \(3\).
-
Un número es divisible por \(9\) si la suma de sus cifras da \(9\).
-
Un número es divisible por \(10\) si su última cifra es \(0\).
-
Un número es divisible por \(11\) si la resta entre la suma de cifras en posición impar y la suma de cifras en posición par es divisible por \(11\).
Ejercicios resueltos - Reglas de divisibilidad
1.
Determinar si \(110110001100\) es primo.
La última cifra es \(0\), por lo tanto es divisible por \(2\). La suma de sus cifras es \(6\), por lo que es divisible por \(2, 3, 6\). El número termina en \(0\), también es divisible por \(5, 10\). El número no es primo.
2.
Existe un único número \(d \in \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}\) tal que \(11 \mid 15646897d\)
Primero sumamos las cifras en posición impares y sumar las cifras en posición pares:
\[1 + 6 + 6 + 9 + d = 22 + d \\ 5 + 4 + 8 + 7 = 24 \]Descartamos \(0, 1\) ya que \((22 - 24) \lor (23 - 24) < 0\). Mientras que \(2\) es candidato, \(22 + 2 - 24 = 0\).
Si \(22 + d = 35\) podriamos restar \(24\) y obtener el siguiente número divisible por \(11\). Sin embargo, esto no es posible con los números del conjunto, por lo tanto solo tenemos que \(d = 2\) cumple la condición. Verdadero.
Factorización prima
Teorema Fundamental de la Aritmética
Todo entero \(n > 1\) puede ser escrito de manera única como producto de primos (salvo el orden de los factores).
Propiedades de la factorización prima
Sean \(a \in \mathbb{Z}\) y \(p\) primo:
1) \(p \not{\mid} \; a \implies \textnormal{mcd}(a, p) = 1\)
2) \(p, p'\) primos y \(p \mid p' \implies p = p'\)
3) \(n > 0\) no primo \(\implies \exists m > 0\) tal que \(m \mid n, \; m \leq \sqrt{n}\)
Criterio de la raíz
Sea \(n \geq 2\), si para todo \(m\) tal que \(1 < m \leq \sqrt{n}\), se cumple que \(m \not{\mid} \; n\), entonces \(n\) es primo.
Ejemplo:
Podemos verificar si \(467\) es primo o no:
\[\begin{align*} \sqrt{467} &\approx 21.6 \\ 2 \leq m \leq 21 &\implies 3, 5, 7, 11, 13, 17, 19 \not{\mid} \; 467 \end{align*} \]Comprobamos que los números no dividen a \(467\), por lo que \(467\) es primo.
Ejercicios resueltos - Factorización prima
1.
Calcular el mínimo común múltiplo y el máximo común divisor de \(4032\) y \(11^8 \cdot 7^5 \cdot 3^2 \cdot 2\).
Primero podemos expresar el número \(4032\) como producto de primos. Para ello necesitamos dividir el número por los primos más pequeños posibles:
\[\begin{align*} 2 &\mid 4032 \\ 2 &\mid 2016 \\ 2 &\mid 1008 \\ 2 &\mid 504 \\ 2 &\mid 252 \\ 2 &\mid 126 \\ 3 &\mid 63 \\ 3 &\mid 21 \\ 7 &\mid 7 \end{align*} \]Por lo tanto, tenemos que:
\[2^6 \cdot 3^2 \cdot 7 = 4032 \]Ahora, tenemos ambos números expresados como producto de primos. Para dar con el mcd, debemos elegir los primos comunes con menor exponente:
\[\textnormal{mcd}(2^6 \cdot 3^2 \cdot 7, 11^8 \cdot 7^5 \cdot 3^2 \cdot 2) = 2 \cdot 3^2 \cdot 7 \]Para el mcm, debemos elegir todos los primos con mayor exponente entre ambos números:
\[\textnormal{mcm}(2^6 \cdot 3^2 \cdot 7, 11^8 \cdot 7^5 \cdot 3^2 \cdot 2) = 2^6 \cdot 3^2 \cdot 7^5 \cdot 11^8 \]2.
Dar el conjunto de divisores de \(4032\).
Por el ejercicio anterior, sabemos que \(4032 = 2^6 \cdot 3^2 \cdot 7\). Entonces, los divisores de \(4032\) son todos los números que se pueden formar con los exponentes de los primos:
\[k \mid 4032 \implies k \in \{\; 2^i \cdot 3^j \cdot 7^l \mid 0 \leq i \leq 6, \; 0 \leq j \leq 2, \; 0 \leq l \leq 1 \; \} \]Teorema - Números pares
Si \(m, n \in \mathbb{Z}\), tales que \(m \geq 2 \land n \geq 2 \implies m^2 \neq 2n^2\).
No puede ocurrir que \(m^2 = 2n^2\) porque si ocurriera ese número tendría en la descomposición prima por un lado \(2\) a una potencia impar y por otro lado \(2\) a una potencia par.
Con esto podemos probar que \(\sqrt{2}\) es irracional. Para ello suponemos que \(\sqrt{2}\) es racional:
\[\sqrt{2} = \frac{m}{n} \]Entendemos esta fracción como una fracción irreducible, sin embargo esto no se cumple:
\[2 = \frac{m^2}{n^2} \implies 2n^2 = m^2 \]\(m^2 = 2n^2\), por lo que \(m\) es par. Sabiendo que \(m\) es par, lo reescribimos como \(m = 2k\):
\[4k^2 = 2n^2 \implies 2k^2 = n^2 \]Ambos números son pares, la fracción sigue siendo reducible.
Por lo que \(m^2 = 2n^2\) es un absurdo y \(\sqrt{2}\) es irracional.