PDF de programación - Teoría elemental de números NUMEROS ENTEROS

Teoría elemental de números

NUMEROS ENTEROS

La Teoría de Números es la parte de la Matemática que trata de los números enteros y sus propiedades. Estudia la
divisibilidad y la congruencia de números enteros, los números primos y su distribución, las operaciones algebraicas
entre ellos y las soluciones enteras de ecuaciones diofánticas. Se designará a los conjuntos de números naturales y
enteros por N y Z respectivamente.

N = { 1, 2, 3, 4, 5, ... }
Z = { ..., -4, -3, -2, -1, 0, 1, 2, 3, 4, ... }

El número 0 no es un número natural. El conjunto de los números enteros no negativos se designa por N U {0}. Uno
de los principios más importantes en la Teoría de Números es:

•

Principio de la buena ordenación: todo subconjunto no vacío de números enteros no negativos tiene un primer
elemento, es decir, tiene un elemento que es menor que todos los demás.

Operaciones con números enteros

Sean a y b dos números enteros. A partir de las operaciones suma (a + b) y producto (a · b), es fácil definir las
siguientes operaciones:

• Diferencia (d = a - b): otro entero que satisfaga la igualdad a = b + d.
• Divide a (a | b): si a # 0 y b = a · q, diremos que a divide a b, a es un divisor de b, a es un factor de b, o que b

es un múltiplo de a.

• Mayor que (b > a): si existe un número natural n tal que b = a + n.

Propiedades de los números enteros

Sean a, b, c, x e y números enteros:

•
•
•
•
•
•
•
•

a · 0 = 0
a · (-b) = -a · b
Si a # 0 y a · b = a · b, entonces b = c
Si a # 0 y a | b, entonces a | b · x
Sean a # 0 y b # 0, si a | b y b | c, entonces a | c
Sea a # 0, si a | b y a | c, entonces a | (b · x + c · y)
Sean a y b positivos, si a | b, entonces a <= b
Sean a # 0 y b # 0, si a | b y b | a, entonces a = b o a = -b

Valor absoluto

Llamaremos valor absoluto a la aplicación | | : Z -> Z, tal que todo número entero tiene imagen mediante | | y esta
imagen es única. Queda definida por:

•
•

Si n >= 0, entonces | n | = n
Si n < 0, entonces | n | = -n

Propiedades del valor absoluto

•
•
•
•
•

| n | pertenece a N U {0}
| n | = 0 si y sólo si n = 0
| a · b | = | a | · | b |
| a + b | <= | a | + | b |
Si a # 0, b # 0 y a | b, entonces | a | <= | b |

Algoritmo de la División

Sean a entero y b natural. Entonces existen números enteros q y r tales que:

a = b · q + r

con 0 <= r < | b |. Además q y r son únicos. A los números a, b, q y r se les llama respectivamente dividendo,
divisor, cociente y resto.

Módulo

Sean a y b números enteros con b # 0. Sea a = b · q + r donde 0 <= r < | b |. Definimos el operador módulo
(MOD) por:

a MOD b = r

Propiedades del operador MOD

Sean a, b, c, d y m números enteros con m # 0. Si a MOD m = c MOD m y b MOD m = d MOD m,
entonces:

•
•

(a + b) MOD m = (c + d) MOD m
(a · b) MOD m = (c · d) MOD m

Máximo común divisor

Sean a y b enteros. Un entero d # 0 es un divisor común de a y b si d | a y d | b. Un divisor común de a y b se llama
máximo común divisor de a y b si d > 0 y cada común divisor de a y b divide también a d. Se designa por:

m.c.d.(a, b) = d

Algoritmo de Euclides

El Algoritmo de Euclides se basa en sucesivas divisiones de dos números hasta obtener su máximo común divisor. Es
decir, si m.c.d.(a, b) = d y a = b · q + r, entonces tendremos:

d = rn-1 = m.c.d.(rn-2, rn-1) = m.c.d.(rn-3, rn-2) = ... = m.c.d.(b, r1) = m.c.d.(a, b)

Si hacemos la divisiones sucesivas partiendo del Algoritmo de la División original:

•
•
•
•
•

a = b · q1 + r1
b = r1 · q2 + r2
r1 = r2 · q3 + r3
...
rn-4 = rn-3 · qn-2 + rn-2

•
•

rn-3 = rn-2 · qn-1 + rn-1
rn-2 = rn-1 · qn + 0

Cálculo del máximo común divisor de dos números mediante el Algoritmo de Euclides de la división

Se procede con la división de tal forma que cumpla a = b · q + r donde q = a DIV b y r = a MOD b. A
continuación, si el resto es distinto de cero, se toma en la siguiente división: a = b y b = r, es decir, el divisor y el
resto de la división anterior. Cuando se llegue a una expresión con el resto igual a cero, el término b será el máximo
común divisor.
• m.c.d.(1312, 800) = d
•
1312 = 800 . 1 + 512
•
800 = 512 . 1 + 288
•
512 = 288 . 1 + 224
•
288 = 224 . 1 + 64
•
224 = 64 . 3 + 32
•
64 = 32 . 2 + 0
•
d = 32

NUMEROS PRIMOS

Dado un número entero p > 1, diremos que p es un número primo si 1 y p son los únicos divisores positivos de p. Un
entero a > 1 que no es primo le denominaremos número compuesto. Dos números, a y b, son primos entre sí, si se
tiene que m.c.d.(a, b) = 1.

Lema de Euclides

Sean a, b y c números enteros. Supongamos que a y c son primos entre sí y que c | a · b. Entonces c | b.

Teorema Fundamental de la Aritmética

Sea n un número mayor que 1. Entonces existen números primos p1, ... , pr tales que:

n = p1 · p2 · ... · pr

donde p1 <= p2 <= ... <= pr.

Teoremas

•
•
•
•

Sea p un entero mayor que 1 y primo. Para cualquier a y b enteros, si p | a · b entonces p | a o p | b.
El número de primos es infinito.
Si pn es el n-ésimo número primo entonces pn <= 2^(2^n-1).
Sea a un entero mayor que 1, entonces si para todo número primo p menor o igual que la raíz de a, p no divide al
número a, se verifica que a es primo.

Comprobar que un número es primo utilizando la criba de Erastóstenes

La criba de Erastóstenes dice que un número es primo si no es divisible por otro primo menor que la raíz cuadrada
entera del primero. Primero se desarrolla la criba y a continuación se divide el número por cada uno de los primos
contenidos en la criba.

n = 811
p < Raíz( 811 ) = 29

•
•
• Criba: 2, 3, 5, 7, 11, 13, 17, 19, 23 = i
• División: 29 MOD i # 0
•

811 sí es primo

Mínimo común múltiplo

Sean a y b dos números enteros. Llamaremos mínimo común múltiplo de a y b al menor entero positivo que sea
múltiplo de ambos. Lo designaremos por m.c.m.(a, b).

•

Sean a y b enteros no nulos, entonces | a · b | = [ m.c.d.(a, b) ] · [ m.c.m.(a, b) ]

EL PRINCIPIO DE INDUCCION

En las Matemáticas aparecen muchos problemas que tienen la siguiente forma general:

•
•

Sea P(n) una determinada propiedad acerca de un número natural n.
Se trata de probar que P(n) es verdadero para todo n que sea natural.

Teorema del Principio de Inducción

Sea S un conjunto de números naturales que satisface las dos condiciones siguientes:

•
•

El número 1 pertenece a S.
Para cada número k >= 1, si k pertenece a S entonces k + 1 también pertenece a S.

Entonces el conjunto S es igual a N.

Pasos a seguir

• Definir el conjunto S = { n pertenecientes a N tales que P(n) es verdadera }.
•
•
• Demostrar entonces que k + 1 pertenece a S.

Probar que 1 pertenece a S.
Suponer que k pertenece a S para k >= 1 arbitrario.

Principio Fuerte de Inducción

Sea S un conjunto de enteros positivos tales que:

•
•

1 pertenece a S.
Para cada entero n > 1, si k pertenece a S para todo entero k tal que 1 <= k < n entonces n pertenece a S.

Entonces S = N.

Demostrar una propiedad por el Principio de Inducción

Sea S el conjunto de los valores. Según dicho principio, la propiedad se debe cumplir para el elemento 1 y para
cualquier elemento k + 1 dado un k. Se presentan dos expresiones separadas con el signo igual, donde se les
añade un término k + 1 a ambas y se resuelve por la segunda expresión.

1^2 + 2^2 + ... + n^2 = n · (n + 1) · (2n + 1) / 6

Para todo n natural:
•
Primera propiedad: P(1) pertenece a S
•
Segunda propiedad: P(k) y P(k + 1) pertenecen a S
•

1^2 = 1 · (1 + 1) · (2 · 1 + 1) / 6 = 1 · 2 · 3 /6 = 6 / 6 = 1

1^2 + 2^2 + ... + k^2 + (k + 1)^2 = k · (k + 1) · (2k + 1) / 6 + (k + 1)^2 = k · (k + 1) · (2k + 1) +
6 · (k + 1)^2 / 6 = (k + 1) · (2k^2 + k + 6k + 6) / 6 = (k + 1) · (k + 2) · (2k + 3) / 6

Por lo tanto, se cumple la propiedad para todo natural

ECUACIONES DIOFANTICAS

Ecuaciones lineales de dos variables enteras

Sean a, b y n números enteros. La ecuación lineal a · x + b · y = n tiene solución entera x0 e y0 si y sólo si d =
m.c.d.(a, b) divide a n.

• Dada la ecuación a · x + b · y = n se calcula el m.c.d.(a, b) llegando a escribir d = a · q1 + b · q2 (a = b ·

•

q1 + r1 y b = r1 · q2 + r2), siendo una solución x0 = n · q1 / d e y0 = n · q2 / d.
Supongamos que a, b y n son enteros no nulos y d = m.c.d.(a, b) divide a n. Entonces la solución general de la
ecuación a · x + b · y = n tiene la forma: {x0 + t · b / d , y0 - t · a / d} donde t es cualquier entero.

Calcular los valores de dos incógnitas para que se cumpla la expresión d = ax + by

Se calcula el máximo común divisor de los coeficientes por el Algoritmo de Euclides de la división y se sitúan los restos
desde el último hasta el primero que sean distintos de cero:

r = a - b · q

Se comienza desde la primera expresión y se sustituye b por su equivalente en la ecuación siguiente. A continuación
pasamos a la siguiente ecuación y sustituimos a, y así sucesivamente. Cuando se llegue al final debe quedar:

d = m.c.d.(a, b)= ax + by

•
d = 322x + 406y
• m.c.d.(322, 406)
•
•
•
•
•
•
•
•
•
•
•
•
•
•

322 = 406 · 0 + 322
406 = 322 · 1 + 84
322 = 84 · 3 + 70
84 = 70 · 1 + 14
70 = 14 · 5 + 0
1º Resto: 14 = 84 - 1 · 70
2º Resto: 70 = 322 - 3 · 84
3º Resto: 84 =406 - 1 · 322
4º Resto: 322 = 322 - 0 · 406
Se toma el 1º Resto: 14 =84 - 1 · 70
Se sustituye 70: 14 = 84 - 1 · (322 - 3 · 84) = -322 + 4 · 84
Se sustituye 84: 14 = -322 + 4 · (406 - 1 · 322) = -5 · 322 + 406 · 4
Se sustituye 322: 14 = -5 · (322 - 0 · 406) + 4 · 406 = -5 · 322 + 4 · 406
x = -5 || y = 4

Hallar todas las soluciones de ecuaciones diofánticas del tipo ax + by = n

Primero se calcula el máximo común divisor de a y b, al que se le llamará d. Después se comprueba que d divide a n,
para saber si la ecuación tiene solución. Si es así, existen a' y b' tales que:

d = a' · a + b' · b

A continuación se averiguan a' y b' tomando la primera ecuación de los restos obtenidos del máximo común divisor de
a y b, y sustituyendo los b y los a:

r = a - b · q

Una solución de la ecuación sería:

x0 = n · a' / d
y0 = n · b' / d

Y la solución general del sistema sería:

{x0 + b · t / d , y0 - a · t /