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

Sean $a \in \mathbb{Z}$ y $b \in \mathbb{N}$ existen enteros únicos $q$ y $r$ tales que:

a = b \cdot q + r , \;0 \leq r < b

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

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

Todo natural $x$ se puede expresar como:

x = r_n 10^n + r_{n-1} 10^{n-1} + \ldots + r_1 10+ r_0

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

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

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

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.

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

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

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.