Números

Siempre vamos a trabajar con números enteros ($\Z$) a partir de ahora. Estos son los únicos números con los que el ordenador trabaja cómodamente, porque los números flotantes están sujetos a aproximaciones y errores de precisión.

$\Z$ es un anillo conmutativo (ver Álgebra), no es un cuerpo, por lo tanto es posible que un número no tenga inverso. Entonces no hay división para todos los números enteros.

División Entera

Se lee: a divide a b, a es factor de b, b multiplica a a.

Algoritmo de división

El algoritmo de división nos permite encontrar los dos únicos enteros $q$ y $r$ que cumplen:

$$ a = bq + r \implies r = a - bq $$

con $0 \le r < b$.

Esto permite crear la siguiente definición:

$a \text{ mod } b$ es la operación que devuelve el resto de la división entera entre $a$ y $b$, y la operación suelo sobre un número real $x$, $\lfloor x \rfloor$, es el mayor entero $z$ tal que $z \le x$.

Este es el código Python que implementa el algoritmo de división:

 1def cociente_positivo(a, b):
 2    q = 0
 3    while a - q*b >= b:
 4        q += 1
 5    return q
 6
 7def cociente_negativo(a, b):
 8    q = -1
 9    while a - q*b < 0:
10        q -= 1
11    return q
12
13cociente = lambda a, b:
14    cociente_positivo(a, b) if a >= 0 else cociente_negativo(a, b)
15resto    = lambda a, b: a - cociente(a, b)*b

Máximo común divisor

Se puede calcular tomando los factores primos comunes de $a$ y $b$ elevados al menor exponente. Pero ojo, factorizar es NP!. Para ello es mejor usar el algoritmo de Euclides.

Algoritmo de Euclides

Se trata de un algoritmo de complejidad computacional logarítmica $\Theta(\log n)$ temporalmente y $\Theta(1)$ espacialmente, por tanto es muy eficiente (mucho más que factorizando).

Para comprender su funcionamiento, es necesario conocer el siguiente lema:

Se comprenderá mejor con un ejemplo:

Este es el código Python que implementa este algoritmo:

1def gcd(a, b):
2    dividendo = a
3    divisor   = b
4    while resto > 0:
5        resto     = dividendo % divisor
6        dividendo = divisor
7        divisor   = resto
8    return dividendo

Y alternativamente, se puede formular de forma recursiva:

1def gcd_re(a, b):
2    if min(a, b) == 0:
3        return max(a, b)
4    else:
5        return gcd_re(b, a%b)

Mínimo común múltiplo

También se puede calcular tomando los factores primos de $a$ y $b$ elevados al mayor exponente, pero es mucho más cómodo calcular $$\text{lcm}(a,b) = \frac{ab}{\gcd(a,b)}.$$

El código en Python para este, ya resulta mucho más sencillo:

1lcm = lambda a, b: int(a * b / gcd(a, b))

Teorema de Bézout

Esta identidad cobrará particular importancia en Aritmética Modular.

Algoritmo de Euclides Extendido

Este algoritmo, utiliza la mismas iteraciones que el algoritmo de Euclides, pero además nos permite calcular los coeficientes de Bézout.

Para ello se reutilizarán las expresiones calculadas en el ejemplo visto en el algoritmo de Euclides:

$$ \begin{align} 166 =& \, 414 - 1 \times 248 \\ 82 =& \, 248 - 1 \times 166 \\ 2 =& \, 166 - 2 \times 82 \\ 0 =& \, 82 - 2 \times 41 \end{align} $$

Y ahora, simplemente se opera:

$$ \begin{align*} \gcd(414, 248) = 2 =& \overbrace{166 - 2 \times 82}^{(3)}\\ =& 166 - 2 \times (\overbrace{248 - 1 \times 166}^{(2)}) = 3 \times 166 - 2 \times 248 \\ =& 3 \times (\overbrace{414 - 1 \times 248}^{(1)}) - 2 \times 248 = 3 \times 414 - 5 \times 248 \\ \end{align*} $$

Por lo que se concluye con que $s=3$ y $t=-5$.

Y este es el código Python correspondiente:

 1def gcd_ex(a, b):
 2    (r_ant, r) = (a, b)
 3    (s_ant, s) = (1, 0)
 4    (t_ant, t) = (0, 1)
 5    while r != 0:
 6        cociente = r_ant // r
 7        (r_ant, r) = (r, r_ant - cociente * r)
 8        (s_ant, s) = (s, s_ant - cociente * s)
 9        (t_ant, t) = (t, t_ant - cociente * t)
10    return s_ant, t_ant

Números primos

Por ejemplo los primos de Marsenne, que son de la forma $2^p - 1$ son buenos candidatos a ser primos, pero no todos lo son.

Por eso factorizar es un problema NP, se puede comprobar que un número es primo en tiempo polinómico, porque solo se tiene que iterar hasta la raiz del número.

Unidades e inversos

Por ejemplo, el conjunto de unidades de los enteros es $\set{-1, 1}$.

Si se combinan estas dos definiciones, se puede decir que $a$ es una unidad si tiene un inverso multiplicativo.

Representación de enteros

Este es el teorema de expansión en base $b$ de $n$:

Esto quiere decir que si tenemos un número en una base, este se puede convertir a base $b$, y $a_0, \ldots, a_k$ serán sus cifras en dicha base.

Algoritmo de conversión de base

$$ \begin{align*} & a = q_0 b + r_0 \\ \text{Si } q_0 \ne 0: \quad & q_0 = q_1 b + r_1 \\ \text{Si } q_0 \ne 0: \quad & q_1 = q_2 b + r_2 \\ \vdots \\ \text{Si } q_i = 0: \quad & q_{i - 1} = r_i \\ \end{align*} $$

Y las cifras en base $b$ serán $r_i \ldots r_0$.

Hay algunas bases que se pueden «optimizar»:

$$ 011011_2 = \overbrace{1 + 1 \times 2 + 0 \times 2^2}^{a_0} + \overbrace{1 \times 2^3 + 1 \times 2^4 + 0 \times 2^5}^{(1 + 1 \times 2 + 0 \times 2^2) 2^3} $$

Por tanto, se puede convertir rápidamente de binario (base 2), a octal (base 8), a hexadecimal (base 16), …; y viceversa.

Criterios de divisibilidad

Para ver si un número es divisible entre otro de forma rápida, se puede utilizar la aritmética modular combinada con la representación de enteros ya vista.

Véanse un par de ejemplos: