Semana 4 - Numeros Enteros (Parte 1)

Números enteros — Parte 1

Hilo conductor: dividir deja un resto; tener el mismo resto es ser congruente. El algoritmo de Euclides encuentra el MCD y la factorización prima explica todos los divisores.

1. Divisibilidad

Para $a, d \in Z$ con $d \neq 0$ :

d ∣ a ⟺ \exists k \in Z : a = k d .

Si $d ∣ a$ , entonces $| d | \leq | a |$ (salvo $a = 0$ , que todo $d \neq 0$ divide).
Los únicos invertibles en $Z$ son $1$ y $- 1$ .
$a$ es primo si $a \neq 0, \pm 1$ y sus únicos divisores positivos son $1$ y $| a |$ .
$a$ es compuesto si $a \neq 0, \pm 1$ y no es primo.

Reglas de uso

Si sabés que...	Entonces...
$d ∣ a$ y $d ∣ b$	$d ∣ (a + b)$ y $d ∣ (a - b)$
$d ∣ a$	$d ∣ c a$ para todo $c \in Z$
$d ∣ a$	$d ∣ a^{n}$ para $n \in N$
$d ∣ (a + b)$ y $d ∣ a$	$d ∣ b$

Ojo: $d ∣ a b$ no implica $d ∣ a$ o $d ∣ b$ . Por ejemplo, $6 ∣ 3 \cdot 4$ , pero $6 ∤ 3$ y $6 ∤ 4$ .

2. Congruencias: mismo resto

a \equiv b (\mod d) ⟺ d ∣ (a - b), d \neq 0.

Es una relación de equivalencia: es reflexiva, simétrica y transitiva. En la práctica, permite reemplazar un número por otro con el mismo resto.

a \equiv b (\mod d) ⟹ {\begin{cases} a + c \equiv b + c (\mod d), \\ c a \equiv c b (\mod d), \\ a^{n} \equiv b^{n} (\mod d) . \end{cases}

En particular, se pueden sumar, multiplicar y potenciar congruencias término a término.

Mantra: módulo $d$ = “solo importa el resto al dividir por $d$ ”.

3. Algoritmo de división y restos

Para $a, d \in Z$ , $d \neq 0$ , existen únicos $k, r \in Z$ tales que

a = k d + r, 0 \leq r < | d | .

$k$ es el cociente y $r = r_{d} (a)$ , el resto de dividir $a$ por $d$ .

r_{d} (a) = 0 ⟺ d ∣ a ⟺ a \equiv 0 (\mod d) .

Dos números son congruentes módulo $d$ si y solo si tienen el mismo resto:

a \equiv b (\mod d) ⟺ r_{d} (a) = r_{d} (b) .

Para calcular con restos, reducí primero:

\begin{aligned} r_{d} (a + b) & = r_{d} (r_{d} (a) + r_{d} (b)), \\ r_{d} (a b) & = r_{d} (r_{d} (a) r_{d} (b)), \\ r_{d} (a^{n}) & = r_{d} (r_{d} (a)^{n}) . \end{aligned}

Base $d$ y criterios rápidos

Todo $a \in N_{0}$ se escribe de forma única como

a = (r_{n} \dots r_{1} r_{0})_{d} = \sum_{i = 0}^{n} r_{i} d^{i}, 0 \leq r_{i} < d .

Si $a = (r_{n} \dots r_{0})_{10}$ :

3 ∣ a ⟺ 3 ∣ \sum_{i} r_{i}, 11 ∣ a ⟺ 11 ∣ \sum_{i = 0}^{n} (- 1)^{i} r_{i} .

4. MCD y algoritmo de Euclides

Para $a, b \in Z$ , no ambos nulos, $mcd (a, b)$ es el mayor divisor positivo común.

d ∣ a \land d ∣ b ⟺ d ∣ mcd (a, b) .

La idea de Euclides es que el MCD no cambia al reemplazar el número grande por el resto:

mcd (a, b) = mcd (b, r_{b} (a)) .

Repetí divisiones hasta obtener resto $0$ ; el último resto no nulo es el MCD.

\begin{aligned} a & = q_{1} b + r_{1} \\ b & = q_{2} r_{1} + r_{2} \\ ⋮ \\ r_{m - 2} & = q_{m} r_{m - 1} + 0 \end{aligned} ⟹ mcd (a, b) = r_{m - 1} .

Además, existen $s, t \in Z$ tales que

mcd (a, b) = s a + t b .

Esta es la identidad de Bézout: las combinaciones enteras de $a$ y $b$ son exactamente los múltiplos de su MCD.

5. Coprimos y primos

a ⊥ b ⟺ mcd (a, b) = 1 ⟺ \exists s, t \in Z : s a + t b = 1.

Regla	Lectura
$c ⊥ d \Rightarrow c ∣ a$ y $d ∣ a ⟺ c d ∣ a$	factores coprimos se pueden juntar
$d ⊥ a \Rightarrow d ∣ a b ⟺ d ∣ b$	se puede “cancelar” $a$ solo si es coprimo con $d$
$p$ primo y $p ∣ a b$	$p ∣ a$ o $p ∣ b$

Todo entero $a \neq 0, \pm 1$ tiene factorización prima única, salvo el orden y el signo:

a = \pm p_{1}^{m_{1}} \dots p_{r}^{m_{r}},

donde los $p_{i}$ son primos positivos distintos y $m_{i} \geq 1$ .

Si $a = p_{1}^{m_{1}} \dots p_{r}^{m_{r}} > 0$ , cada divisor positivo es

d = p_{1}^{n_{1}} \dots p_{r}^{n_{r}}, 0 \leq n_{i} \leq m_{i},

por lo que

# {Div}_{+} (a) = (m_{1} + 1) \dots (m_{r} + 1) .

Mantra final: Euclides encuentra el MCD; Bézout lo escribe como combinación; la factorización prima cuenta y describe los divisores.