Algoritmo de división

Teorema

Dados $a$, $d \in \Z$ con $d ≠ 0$, existen $k, r \in \Z$ tales que

$$ a = k \cdot d + r\qquad \text{con } 0 ≤ r< |d| $$

Y además estos $k$ y $r$ son únicos.

$a$ dividendo

$k$ cociente

$r$ resto: $r_d(a) =$ resto de dividir a $a$ por $d$.

Observaciones:

1. Supongamos $0≤ a< |d|$, entonces

   $$ ⁍ $$

   (pues $a = 0\cdot d + a$ cumple condición de resto)

2. $r_d(a) = 0 \iff d|a \iff a \equiv 0 (d)$

3. Congruencia y restos:

   1. $a \equiv r_d(a) (\text{mod } d)$
   2. $a \equiv r(\text{mod } d)$ con $0 ≤ r < |d| \implies r = r_d(a)$
   3. $r_1 \equiv r_2 (\text{mod } d)$ con $0 ≤ r_1, r_2 < |d| \implies r_1 = r_2$
   4. $\boxed {a \equiv b (\text{mod } d) \iff r_d(a) = r_d(b)}$

Tablas de restos

1. Relación de resto con suma y producto

   1. $r_d(a+b) = r_d\big(r_d(a) + r_d(b) \big)$
   2. $r_d(ab) = r_d \big(r_d(a) \cdot r_d(b) \big)$
   3. $r_d(a^n) = r_d\big(r_d(a)^n\big)$

2. Tablas de restos

   $$ \begin{array}{c:c:c:c:c:c:c:c} r_7(a) & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline r_7(a^2) & 0 & 1 & 4 & 2 & 2 & 4 & 1 \\ \hdashline r_7(a^3) & 0 & 1 & 1 & 6 & 1 & 6 & 6 \end{array} $$

Sistemas de numeración

Desarrollo en base $d$

Teorema

Sea $d \in \N$, $d ≥ 2$

$\forall a \in \N_0$ se puede escribir en la forma

$$ a = r_nd^n + r_{n-1}d^{n-1}+...+ r_1d+r_0 $$

con $0 ≤ r_i < d$

para $0 ≤ i ≤ n$

con $r_n ≠ 0$ si $a ≠ 0$

Y este desarrollo es único, es decir $r_n, ..., r_0$ son únicos en esas condiciones.

Notación: $a = (r_nr_{n-1} ... r_1r_0)_d$