La teoría de números
La teoría
de números es una rama de las matemáticas que se ocupa de los números enteros.
Por tradición, la teoría de números era una rama de las matemáticas puras,
conocida por su naturaleza abstracta más que por sus aplicaciones. El gran
matemático inglés G. H. Hardy (1877-1947) usó la teoría de números como ejemplo
de una rama de las matemáticas bella pero impráctica. Sin embargo, a finales
del siglo XX, la teoría de números ha adquirido una gran importancia en los
sistemas criptográficos, esto es, sistemas que se usan para la seguridad en las
comunicaciones. En los capítulos anteriores, se usaron algunas definiciones
básicas de la teoría de números como “divide” y “número primo”. En la sección
5.1 se repasarán estas definiciones básicas y se ampliará el estudio a
factorización única, máximo común divisor y mínimo común múltiplo. En la
sección 5.2 se analizarán las representaciones de los números enteros y algunos
algoritmos para la aritmética entera. El algoritmo euclidiano para calcular el
máximo común divisor es el tema de la sección 5.3. Éste es sin duda uno de los
algoritmos más antiguos. Euclides vivió aproximadamente en 295 A.C., y el
algoritmo tal vez es anterior.
Divisores
En
esta sección se presentan las definiciones y terminología básicas. Primero se
recordará la definición de “divide”, y se introducirá cierta terminología
relacionada.
Sean
n y d enteros, d 0. Se dice que d divide
a n si existe un entero q que satisface n = dq; q se llama el cociente y d el
divisor o factor de n. Si d divide a n, se escribe d|n. Si d no divide a n, se
escribe ▼ d | /n.
Como
21 = 3 · 7, 3 divide a 21 y escribimos 3|21. El cociente es 7; 3 recibe el
nombre de divisor o factor de 21. Se observa que si n y d son enteros positivos
y d|n, entonces d≤n. (Si d|n, existe unentero q tal que n = dq. Como n y d son
enteros positivos, 1 ≤q. Por lo tanto, d≤dq = n). Ya sea que un entero d > 0
divida o no a un entero n, se obtiene un cociente único q y un residuo r como
lo establece el teorema del cociente-residuo (Teorema 1.8.5): Existen enteros
únicos q (cociente) y r (residuo) que satisfacen n = dq+r, 0 ≤r < d. El
residuo r es igual a cero si y sólo si d divide a n.
Un
entero mayor que 1 cuyos únicos divisores positivos son 1 y él mismo se llama
primo. Un entero mayor que 1 que no es primo se llama compuesto.
El
entero 23 es primo porque sus únicos divisores son 1 y él mismo. El entero 34
es compuesto porque es divisible entre 17, que no es 1 ni 34
Si
un entero n > 1 es compuesto, entonces tiene un divisor positivo d diferente
de 1 y él mismo. Como d es positivo y d
1, d > 1. Como d es un divisor de n, d≤n. Como d n, d < n. Por lo tanto, para determinar si
un entero positivo n es compuesto, es suficiente con probar si alguno de los
enteros
2,
3, . . . , n – 1
divide
a n. Si algún entero en esta lista divide a n, entonces n es compuesto. Si no
hay un entero en esta lista que divida a n, entonces n es primo. (En realidad,
la lista se puede reducir de manera considerable; vea el teorema 5.1.7).
Por
inspección, se encuentra que ningún número de la lista
2,
3, 4, 5, . . . , 41, 42
divide
a 43; entonces 43 es primo. Se verifica la lista
2,
3, 4, 5, . . . , 449, 450 en busca de
divisores potenciales de 451, se encuentra que 11 divide a 451 (451 =11 ·41);
así, 451 es compuesto.
En
el ejemplo 5.1.6, para determinar si un entero positivo n > 1 es primo, se
verificaron los divisores potenciales
2,
3, . . . , n – 1.
En
realidad es suficiente con verificar 2,3 . . . .{√n}.
Representaciones
de enteros y algoritmos enteros
Un
bit es un dígito binario, es decir, un 0 o un 1. En una computadora digital,
los datos y las instrucciones se codifican como bits. (El término digital se
refiere al uso de los dígitos 0 y 1). La tecnología determina cómo se
representan físicamente los bits dentro del sistema de la computadora. El
hardware actual se apoya en el estado de un circuito electrónico para
representar un bit. El circuito debe ser capaz de estar en dos estados: uno que
representa a 1, y el otro a 0. En esta sección se estudia el sistema de números
binario, que representa enteros que usan bits, y el sistema numérico
hexadecimal, que representa enteros que usan 16 símbolos. El sistema de números
octal, que representa enteros que usan 8 símbolos, se estudiará antes del
ejercicio 42. En el sistema numérico decimal, para representar los enteros se
usan los 10 símbolos 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9. Al representar un entero,
la posición del símbolo es significativa; leyendo desde la derecha, el primer
símbolo representa al número de unidades, el siguiente símbolo el número de
decenas, el siguiente el número de centenas, y así sucesivamente.
En
general, el símbolo en la posición n (donde el símbolo en la extrema derecha
está en la posición 0) representa el número de 10n que hay. Como 100 = 1, el
símbolo en la posición 0 representa el número de 100 o decenas; como 101 =10,
el símbolo en la posición 1 representa el número de 101 o decenas; como 102
=100, el símbolo en la posición 2 representa el número de 102 o centenas, y así
sucesivamente. El valor en el que está basado el sistema (10 en este caso)
recibe el nombre de base del sistema numérico. En el sistema numérico binario
(base 2), para representar enteros se necesitan sólo dos símbolos, 0 y 1. Para
representar un entero, leyendo de derecha a izquierda, el primer símbolo
representa el número de unos, el siguiente símbolo el número de números dos, el
siguiente el número de cuatros, el siguiente el número de ochos, etcétera
101101=1·25
+0·24 +1·23 +1·22 +0·21 +1·20
Comentarios