Desde los primeros ábacos hasta los modernos procesadores cuánticos, la aritmética ha sido el cimiento sobre el cual se construye la tecnología. En este artículo exploraremos cómo los conceptos básicos de suma, resta, multiplicación y división han evolucionado para convertirse en algoritmos complejos que impulsan la inteligencia artificial, la criptografía y más. Si quieres profundizar en los fundamentos, revisa nuestra introducción a la aritmética.
De las operaciones básicas a los primeros algoritmos
La transición del cálculo manual a los métodos algorítmicos comenzó con la necesidad de resolver problemas más complejos de manera eficiente.
Ejemplo: Multiplicación egipcia
Los antiguos egipcios usaban un método de duplicación para multiplicar. Para calcular $13 \times 24$:
- Escribían dos columnas: una comenzando en 1 y otra en 24
- Duplicaban cada columna hasta que la izquierda alcance 13:
1 24 2 48 4 96 8 192 - Sumaban los valores de la derecha correspondientes a 1 + 4 + 8 = 13: $24 + 96 + 192 = 312$
Algoritmos fundamentales en computación
Los sistemas modernos se basan en algoritmos aritméticos optimizados.
Teorema 1: Algoritmo de la división
Para cualesquiera enteros $a$ y $b$ con $b > 0$, existen únicos enteros $q$ y $r$ tales que:
$$a = bq + r \quad \text{con} \quad 0 \leq r < b$$
Demostración:
Sea $S = \{a – bk \mid k \in \mathbb{Z}, a – bk \geq 0\}$. Por el principio del buen orden, S tiene un mínimo elemento $r = a – bq$. Se cumple $r < b$ pues si $r \geq b$, entonces $a - b(q+1) = r - b \geq 0$ sería un elemento menor en S, contradiciendo la minimalidad de r.
Aritmética modular en criptografía
La aritmética modular es fundamental en sistemas de encriptación como RSA.
Ejemplo: Cálculo de congruencias
Calcular $7^{23} \mod 11$ usando exponenciación rápida:
- $7^1 \equiv 7 \mod 11$
- $7^2 \equiv 49 \equiv 5 \mod 11$
- $7^4 \equiv (7^2)^2 \equiv 5^2 \equiv 3 \mod 11$
- $7^8 \equiv (7^4)^2 \equiv 3^2 \equiv 9 \mod 11$
- $7^{16} \equiv (7^8)^2 \equiv 9^2 \equiv 4 \mod 11$
- $23 = 16 + 4 + 2 + 1$
- $7^{23} \equiv 4 \times 3 \times 5 \times 7 \equiv 420 \mod 11 \equiv 2 \mod 11$
Teoremas clave en aritmética computacional
Teorema 2: Pequeño Teorema de Fermat
Si $p$ es primo y $a$ no es divisible por $p$, entonces:
$$a^{p-1} \equiv 1 \mod p$$
Demostración:
Consideremos los números $a, 2a, 3a, …, (p-1)a \mod p$. Todos son distintos y no nulos, por lo que deben ser una permutación de $1, 2, …, p-1$. Multiplicándolos:
$$a^{p-1}(p-1)! \equiv (p-1)! \mod p \Rightarrow a^{p-1} \equiv 1 \mod p$$
Teorema 3: Teorema Chino del Resto
Si $n_1, n_2, …, n_k$ son coprimos dos a dos, entonces el sistema:
$$x \equiv a_1 \mod n_1$$
$$x \equiv a_2 \mod n_2$$
$$\vdots$$
$$x \equiv a_k \mod n_k$$
tiene solución única módulo $N = n_1n_2\cdots n_k$.
Demostración:
Para cada $i$, sea $N_i = N/n_i$. Como $N_i$ y $n_i$ son coprimos, existe $M_i$ tal que $M_iN_i \equiv 1 \mod n_i$. La solución es:
$$x \equiv \sum_{i=1}^k a_iM_iN_i \mod N$$
Ejercicios resueltos
Ejercicio 1: Algoritmo de Euclides
Encuentra $\gcd(1071, 462)$ usando el algoritmo de Euclides.
Solución:
- $1071 = 2 \times 462 + 147$
- $462 = 3 \times 147 + 21$
- $147 = 7 \times 21 + 0$
- El último resto no nulo es 21, por tanto $\gcd(1071, 462) = 21$
Ejercicio 2: Aritmética modular
Resuelve $5x \equiv 3 \mod 17$.
Solución:
- Encontramos el inverso de 5 módulo 17. Como $5 \times 7 = 35 \equiv 1 \mod 17$, el inverso es 7.
- Multiplicamos ambos lados por 7: $x \equiv 3 \times 7 \equiv 21 \mod 17 \equiv 4 \mod 17$
Ejercicio 3: Teorema Chino del Resto
Resuelve el sistema:
$$x \equiv 2 \mod 3$$
$$x \equiv 3 \mod 5$$
$$x \equiv 2 \mod 7$$
Solución:
- $N = 3 \times 5 \times 7 = 105$
- $N_1 = 35$, $M_1 \equiv 35^{-1} \mod 3 \equiv 2$
- $N_2 = 21$, $M_2 \equiv 21^{-1} \mod 5 \equiv 1$
- $N_3 = 15$, $M_3 \equiv 15^{-1} \mod 7 \equiv 1$
- $x \equiv 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 \mod 105$
- $x \equiv 140 + 63 + 30 \mod 105 \equiv 233 \mod 105 \equiv 23 \mod 105$
Ejercicio 4: Exponenciación rápida
Calcula $3^{29} \mod 11$.
Solución:
- Descomponemos 29 en binario: $29 = 16 + 8 + 4 + 1$
- $3^1 \equiv 3 \mod 11$
- $3^2 \equiv 9 \mod 11$
- $3^4 \equiv 9^2 \equiv 81 \mod 11 \equiv 4 \mod 11$
- $3^8 \equiv 4^2 \equiv 16 \mod 11 \equiv 5 \mod 11$
- $3^{16} \equiv 5^2 \equiv 25 \mod 11 \equiv 3 \mod 11$
- $3^{29} \equiv 3^{16} \times 3^8 \times 3^4 \times 3^1 \equiv 3 \times 5 \times 4 \times 3 \mod 11$
- $\equiv 180 \mod 11 \equiv 4 \mod 11$
Ejercicio 5: Aplicación del Pequeño Teorema de Fermat
Demuestra que $17$ divide a $3^{32} – 2^{32}$.
Solución:
- Por el Pequeño Teorema de Fermat, como 17 es primo:
$$3^{16} \equiv 1 \mod 17$$
$$2^{16} \equiv 1 \mod 17$$ - Elevando al cuadrado:
$$3^{32} \equiv (3^{16})^2 \equiv 1 \mod 17$$
$$2^{32} \equiv (2^{16})^2 \equiv 1 \mod 17$$ - Restando:
$$3^{32} – 2^{32} \equiv 1 – 1 \equiv 0 \mod 17$$
Aplicaciones prácticas
La aritmética avanzada es fundamental en:
- Criptografía: Algoritmos RSA y firma digital
- Gráficos por computadora: Operaciones matriciales
- Machine Learning: Optimización de funciones
- Blockchain: Pruebas de trabajo criptográficas
Para más aplicaciones, visita nuestro artículo sobre aplicaciones matemáticas modernas.
Conclusión
Desde los métodos manuales hasta los algoritmos computacionales modernos, la aritmética sigue siendo la base de la tecnología. Hemos explorado teoremas fundamentales como el de Fermat y el Chino del Resto, demostrado su utilidad en ejercicios prácticos y visto sus aplicaciones en campos avanzados. El dominio de estos conceptos abre las puertas a la comprensión de sistemas complejos y al desarrollo de nuevas tecnologías.
«`