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 }.

Probar que 1 pertenece a S.

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

Demostrar entonces que k + 1 pertenece a S.

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.

Para todo n natural:

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

Primera propiedad: P(1) pertenece a S

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

Segunda propiedad: P(k) y P(k + 1) pertenecen a S

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 / d}

para todo t que sea entero.

28x + 36y = 44

28 = 36 · 0 + 28 => 3º Resto: 28 = 28 - 0 · 36

36 = 28 · 1 + 8 => 2º Resto: 8 = 36 - 1 · 28

28 = 8 · 3 + 4 => 1º Resto: 4 = 28 - 3 · 8

8 = 4 · 2 + 0 => Ultima división

m.c.d.(28, 36) = 4

Como 4 divide a 44 (44 / 4 = 11), la ecuación tiene solución

28a' + 36b' = 4

Se toma el 1º Resto: 4 = 28 - 3 · 8

Se sustituye 8: 4 = 28 - 3 · (36 - 1 · 28) = 4 · 28 + (-3) · 36

Se sustituye 28: 4 = 4 · (28 - 0 · 36) + (-3) · 36 = 4 · 28 + (-3) · 36

a' = 4 | b' = -3

Una solución sería: x0 = 44 · 4 / 4 = 44 , y0 = 44 · (-3) / 4 = -33

Y la solución general: {44 + 36t/4, -33 - 28t/4 } = { 44 + 9t, -33 - 7t}

Ecuaciones cuadráticas

La ecuación diofántica x^2 - y^2 = n con n > 0, tiene solución si y sólo si n se puede factorizar como producto de dos números de la misma paridad, es decir, ambos pares o ambos impares. Si existen, las soluciones de esta ecuación tienen la forma:

   x = a + b / 2     ||     y = a - b / 2

donde x + y = a y x - y = b.

Hallar todas las soluciones de ecuaciones de la forma x^2 - y^2 = n

La ecuación tiene solución si n se puede factorizar como producto de dos números de la misma paridad. Las soluciones tendrán la forma:

   x = a + b / 2

   y = a - b / 2

donde n = a · b , a = x + y y b = x - y. Primero se averiguan todos los factores primos y se divide el número entre cada uno de ellos. Se toman aquellas parejas con la misma paridad. Se aplican las fórmulas anteriores y se obtienen todas las soluciones, para a >= b.

x^2 - y^2 = 120

120 = 2 · 2 · 2 · 3 · 5 = 2^3 · 3 · 5

120 = 60 · 2 = 30 · 4 = 20 · 6 = 12 · 10

Se toman todas las parejas en las que a >= b

    a     b      x = a + b / 2     y = a - b / 2

   ======================

   60     2           31                   29

   30     4           17                   13

   20     6           13                    7

   12    10          11                    1

Las soluciones serán: { 31, 29 } , { 17, 13 } , { 13, 7 } y { 11, 1 }.

Algoritmo de factorización de Fermat

Determinar el mínimo entero positivo q que satisfaga que q^2 >= n.

Estudiar si alguno de los números q^2 - n, (q + 1)^2 - n, (q + 2)^2 - n, ... es un cuadrado.

Si para alguno de estos números m, m^2 - n es un cuadrado, entonces n será primo.

Estudiar si un número es compuesto mediante el Algoritmo de factorización de Fermat

Un número es compuesto si es producto de dos números impares. Primero se hace la raíz cuadrada entera y se toma el valor entero mayor q y un intervalo:

   [q^2 ... n + 1 / 2)

Después se van haciendo operaciones q^2 - n y se va incrementando q hasta obtener un número cuadrado. Entonces se sustituyen el q resultante y el número cuadrado en x^2 e y^2:

   x^2 = q     ||     y^2 = número cuadrado     ||     n = x^2 - y^2

Y a continuación, se despejan a y b:

   a = x + y     ||     b = x - y     ||     n = a · b

n = 22733

q >= Raíz( 22733 ) = 151

El intervalo será: [151^2...22733 + 1 / 2) = [151^2...11367) = 151 <= q < 11367

151^2 - 22733 = 22801 - 22733 = 68 no es cuadrado

152^2 - 22733 = 23104 - 22733 = 371 no es cuadrado

153^2 - 22733 = 23409 - 22733 = 676 = 26^2 sí es cuadrado

x = 153     ||     y = 26

a = 153 + 26 = 179

b = 153 - 26 = 127

22733 = 179 · 127 sí es compuesto

Ecuaciones pitagóricas

Las soluciones de la ecuación pitagórica x^2 + y^2 = z^2 que satisfacen las condiciones m.c.d.(x, y, z) = 1, 2 | x y x, y, z > 0, vienen dadas por las fórmulas x = 2 · s · t, y = s^2 - t^2, z = s^2 + t^2, para naturales s, t con s > t tales que m.c.d.(s, t) = 1, y s y t tienen distinta paridad.

CONGRUENCIAS

Sea m > 0. Dados a y b enteros se dice que a y b son congruentes módulo m si a - b es divisible por m. Simbólicamente esta relación se escribe:

   a == b mód (m) si y sólo si m | (a - b)

Fijado m > 0, cada número entero a es congruente con uno de los enteros 0, 1, 2, ... , m - 1. Entonces a == r mód (m), el número r se denomina menor resíduo no negativo de a módulo m, que no es otra cosa que a MOD m = r.

Teoremas

Sean a, b, c, d, h y m enteros con h # 0 y m > 0 entonces:

a == b mód (m) si y sólo si al dividir a y b por m el resto obtenido es el mismo

a == a mód (m)

Si a == b mód (m) entonces b == a mód (m)

Si a == b mód (m) y b == c mód (m) entonces a == c mód (m)

Si a == b mód (m) y c == d mód (m) entonces a + c == b + d mód (m) y a · c == b · d mód (m)

Si a == b mód (m) entonces h · a == h · b mód (m)

Si h | a, h | b, m.c.d.(h, m) = 1 y a == b mód (m) entonces a / h == b / h mód (m)

Ecuación de la forma ax == b mód (m)

La ecuación ax == b mód (m) tiene solución si y sólo si d divide a b donde d es el m.c.d.(a, m). Además el número de soluciones no congruentes módulo m es exactamente d.

Resolver una congruencia del tipo ax == b mód (m)

Una congruencia ax == b mód (m) es equivalente a una ecuación diofántica ax + mk = b. Se calcula el máximo común divisor de a y m, se le llama d y se comprueba que d divida a b. Por el Algoritmo de Euclides de la división se halla a' en:

   a' = b - m / a

y se sustituye en:

   x0 = n · a' / d

   x = x0 - a · t / d

Si x0 es negativo se halla una solución t hasta que x sea positivo.

2x == 6 mód (10)

Ecuación diofántica: 2x + 10k = 6

m.c.d.(2, 10) = 2

Se comprueba que 2 divide a 6

a' = 6 - 10 /2 = -4

x0 = 6 · (-4) / 2 = -12

x = -12 - 10t / 2 = -12 - 5t

Una solución positiva es t = -3: x = -12 - 5 · (-3) = -12 + 15 = 3

La solución general es: x = 3 + 5k

Teorema chino del resto

El sistema de congruencias aix == bi mód (mi), i = 1, 2, ..., k donde m.c.d.(mi, mj) = 1 si i # j y m.c.d.(ai, mi) = 1 para 1 <= i <= k, tiene una única solución x0 módulo m1m2...mk y las demás soluciones son de la forma x = x0 + zm1m2...mk, donde z es un entero.

Resolver un sistema de congruencias y presentar la ecuación general

Se comprueba que los módulos sean primos, es decir, que el máximo común divisor entre ellos sea uno. Si se cumple, la ecuación tendrá la forma:

   ax = bi mód (mi)

donde las soluciones xi serán igual a bi. Se hace el producto de los módulos y se divide entre cada uno de ellos:

   producto de mi = m, donde ti = m / mi

Tendremos un nuevo sistema de ecuaciones con la forma general:

   tiyi = 1 mód (mi)

Se averiguan las respectivas yi y se procede a averiguar el valor buscado:

   x0 = suma de i [ 1 ... n ] en xi · ti · yi

La ecuación general será:

   x = x0 + mk

x = 2 mód (5)

2x = 1 mód (7)

3x = 4 mód (11)

m.c.d.(5, 7) = 1     ||     m.c.d.(7, 11) = 1     ||     m.c.d.(5, 11) = 1

x1 = 2   ||   x2 = 1   ||   x3 = 4   ||   m = 5 · 7 · 11 = 385

  77y1 = 1 mód (5)      55y2 = 1 mód (7)      35y3 = 1 mód (11)

 -75y1 = 0 mód (5)    -49y2 = 0 mód (7)     -33y3 = 0 mód (11)

======================================

    2y1 = 1 mód (5)       6y2 = 1 mód (7)        2y3 = 1 mód (11)

y1 = 3     ||     y2 = 6     ||     y3 = 6

El valor buscado es: x0 = 2 · 77 · 3 + 1 · 55 · 6 + 4 · 35 · 6 = 462 + 330 + 840 = 1632

La ecuación general será: x = 1632 + 385k

Pequeño Teorema de Fermat

Si p es un número primo que no divide al número a entonces a^p-1 == 1 mód (p).

Hallar el resto de dividir una potencia entre un número por el pequeño Teorema de Fermat

Se trata de hallar x en la siguiente expresión:

   a^n = x mód (p)

Se comprueba que p sea primo y que no divida a la base de la potencia. Si se cumple, se aplica el teorema: a^p-1 = 1 mód (p). Se desglosa el exponente de la potencia como una división entre p - 1 y se toma el resto como r1. Quedaría:

   n = (p - 1) · q + r1     ||     a^n = a^(p-1) · q · a^r1

Se halla el resto de la base sin exponente y se aplica en la siguiente fórmula a r2:

   a = y mód (p)     ||     a^p-1 = y^p-1 mód (p) = r2 mód (p)

Por último, sabiendo que x = r1 + r2, se aplica:

   a^n = x mód (p)

x = 113^34291 MOD 7

113^34291 = x mód (7)

Se comprueba que 7 es primo y no divide a 113

Como (p - 1) = 6: 34291 = 6 · 5715 + 1

113^34291 = 113^6 . 5715 + 113^1

113 = 1 mód (7)     ||     113^6 = 1^6 mód (7) = 1 mód (7)

113^34291 = (1 + 1) mód (7) = 2 mód (7)

x = 2

Teorema de Wilson

Si p es un número primo entonces (p - 1)! = -1 mód (p).

SISTEMAS DE NUMERACION

En la vida diaria el sistema de numeración empleado para escribir números naturales es el decimal. Las unidades se agrupan de 10 en 10 para unidades de segundo orden, que se llaman decenas. Estas, a su vez, se agrupan de 10 en 10 para formar unidades de tercer orden o centenas y así sucesivamente. Sea b >= 2 un número natural (llamado base). Entonces todo número natural n puede escribirse de manera única en base b de la forma:

   n = ak · b^k + ak-1 · b^k-1 + ... + a1 · b + a0

De ahora en adelante cuando tengamos un número en base b, escribimos simplemente:

   n = ( ak ak-1 ... a1 a0 ) · b

Cuando la base es mayor que 10, se necesitan nuevos símbolos. Usualmente se utilizan las letras del alfabeto. Así A = 10, B = 11, etc.

Criterio de divisibilidad por k

Un número n es divisible por k si y sólo si:

   Suma de i [ 0 ... t ] en ai . ri = 0 mód (k)

siendo t el último dígito del número n.

Resolver una ecuación mediante un cambio de base y efectuar la suma con otro número de la misma base

Comprobar si la incógnita está en el número o en la base. Si está en el número, se convierte el número contrario en decimal y se efectúa la división entre la base que sí se conoce. Si está en la base, se convierte el número contrario en decimal y se desglosa el número contrario en una ecuación de grado igual al número de dígitos menos uno. Se resuelve la ecuación y se toma el valor positivo. En general, para sumar dos números de la misma base, primero se convierten a decimal, se suman y se vuelven a dividir por la base anterior.

124¬5 = x¬9    ||   132¬x = 330¬5   ||   124¬5 + 330¬5

124¬5 = 4 · 5^0 + 2 · 5^1 + 1 · 5^2 = 4 + 10 + 25 = 39¬10

39 = 9 · 4 + 3   ||   4 = 9 · 0 + 4   ||   4 · 9^1 + 3 · 9^0 = 43¬9   ||   x = 43

330¬5 = 0 · 5^0 + 3 · 5^1 + 3 · 5^2 = 0 + 15 + 75 = 90¬10

132¬x = 90¬10   ||   x^2 + 3x + 2 = 90   ||   x = 8 , x = -11   ||   132¬8 =330¬5

x = 8

124¬5 = 39¬10   ||   330¬5 = 90¬10   ||   39 + 90 = 129¬10

129 = 5 · 25 + 4   ||   25 = 5 · 5 + 0   ||   5 = 5 · 1 + 0   ||   1 = 5 · 0 + 1

1 · 5^3 + 0 · 5^2 + 0 · 5^1 + 4 · 5^0 = 1004¬5   ||   129¬10 = 1004¬5