Download n - Rogelio Davila

Teoría de
Números
Instructor:
Luis Eduardo Falcón
Números Primos
Número Primo
Un número p se dice que es primo si
p es un entero positivo mayor que 1,
cuyos únicos divisores son el 1 y p
mismo.
Un número que no es primo se
llama compuesto.
Teorema Fundamental de la Aritmética
Cualquier entero positivo mayor a 1
puede escribirse de manera única
como un producto de primos, donde
los factores primos se escriben en
orden no descendente.
252  2  2  3  3  7
 2 3 7
2
2
•La cardinalidad del conjunto de
todos los números primos es 0 , es
decir, infinita numerable.
•Si n es un entero compuesto,
entonces n tiene un factor primo no
mayor que n .
•Para cualesquier número entero
positivo n , existen al menos n
enteros compuestos consecutivos.
Al menos se sabe que los enteros
consecutivos de la forma:
n  1! 2
n  1! 3

n  1! n  1
son compuestos.
•Conjetura de Goldbach:
Cualquier número par positivo
mayor a 2, puede escribirse como la
suma de dos primos.
10  3  7  5  5
24  5  19  7  17  11  13
Una variante de la criba de Eratóstenes
nos permite obtener (de una manera no
muy eficiente por cierto) todos los
primos menores que un entero dado:
Por ejemplo, como
30  5.4772...
entonces para encontrar todos los primos
menores que 30, hay que cancelar todos los
múltiplos del 2, 3 y 5.
Máximo
Divisor
Común
•Máximo común divisor = Máximo divisor común
•Mínimo común múltiplo = Mínimo múltiplo común
•Mínimo común denominador = Mínimo denominador común
Se dice que el entero d es un divisor
común de los enteros a y b si
d |a
y d |b
Por ejemplo,
 1,  2,  3,  6
Son los divisores comunes del 24 y el 30.
Máximo Divisor Común
El máximo divisor común, mdc,
de dos enteros a y b, es el mayor
entero que divide a ambos.
El mdc de a y b lo denotamos:
mdc  a, b
mdc  24, 84  12
24
12
6
2
84
42
21
7
2
2
3
24, 84  12
Primos Relativos
Decimos que los enteros a y b
son primos relativos si
a, b  1
Por ejemplo:
3, 7   1
8,13  1
9, 16   1
Algoritmo
de la División
o
de Euclides
Algoritmo de Euclides o de la División
n|m
Si m y n son dos enteros cualesquiera, n > 0,
entonces existe un par único de enteros, q y r,
tales que:
m  qnr
donde
0  r  n.
Si r = 0 decimos que “n divide a m ”, o que “la
división es exacta”.
Observemos que en el algoritmo de la división
el numerador m puede ser cualesquier entero.
Sin embargo, el denominador n debe ser un
entero positivo.
¿Qué nos dice entonces la expresión m  q n  r ?
... que cualquier entero m puede escribirse como un
múltiplo q de n, más un residuo r.
Aclaramos que q puede ser positivo, negativo o cero.
Y que el residuo r puede ser 0, 1, 2, ..., n – 1.
Analicemos el caso n = 3, es decir 3 | m , entonces:
m  3q  r
Es decir, cualquier entero m puede escribirse como
un múltiplo de 3, más un residuo r : 0, 1 o 2.
Así, podremos agrupar TODOS los enteros en
tres clases de equivalencia, módulo 3, las cuales
denotaremos como [0], [1] y [2].
Clases de equivalencia, módulo 3:
[ 0 ]  ,  9,  6,  3, 0, 3, 6, 9, 
[1]  ,  8,  5,  2, 1, 4, 7, 10, 
Algunos elementos
de la clase [ 2 ]
[ 2 ]  ,  7,  4, 1, 2, 5, 8, 11, 
8  3  2   2
5  3  1  2
2  3  0   2
 1  3   1  2
 4  3   2   2
Si m y n son dos enteros cualesquiera, n > 0,
entonces por el algoritmo de la división existen
q y r, tales que:
m  qnr
donde
0  r  n , y definimos las operaciones:
m div n : q
m mod n  r
Algoritmo de Euclides para obtener el mdc
Sean a y b enteros positivos, entonces
el máximo divisor común, mdc, de a y b
es el último residuo no cero de la
aplicación sucesiva del algoritmo de
Euclides.
Si a y b son enteros positivos y
a  c mod b
entonces
mdc a, b  mdc c, b
Por ejemplo:
mdc 689, 234  mdc 234, 221  mdc 221,13  13
221  689 mod 234
13  234 mod 221
0  221mod 13
Por ejemplo, para obtener (198, 252),
se puede hacer en forma de listado
calculando el módulo de los dos
últimos encontrados:
252, 198, 54, 36, 18, 0
entonces, en este caso
mdc 198, 252  18
Teorema de Lamé
El número de divisiones necesarias para
encontrar el máximo divisor común de
dos enteros positivos a y b usando el
algoritmo de Euclides, no es mayor que
5k,
donde k es el número de dígitos (en base
10) del menor de los números a y b .
Por ejemplo, para un número de 1000 dígitos decimales, en vez de
realizar 10^1000 divisiones (utilizando el algoritmo que
aprendemos en la primaria), con el algoritmo euclidiano se harían
5000 aproximadamente.
Congruencias Lineales
a x  b mod n
Teorema:
Sean a, b, n enteros cualesquiera con
n > 0 y donde
d : mdc a, n
entonces la congruencia lineal:
Caso I:
a x  b mod n
no tiene solución si d | b .
a x  b mod n
d : mdc a, n
Caso II:
Tiene exactamente d soluciones
módulo n, si d | b .
Además, dichas soluciones se
encuentran espaciadas una
n
distancia .
d
a x  b mod n
d : mdc a, n
Caso III:
Tiene solución única si d = 1.
Y la solución puede obtenerse con la
inversa de a, es decir,
x  a b mod n 
1
Teorema:
Sea p un número primo.
El entero positivo a es su propio
inverso multiplicativo módulo p
si y sólo si
a  1mod  p
o bien
a  1mod  p
Teorema:
Sean a y b enteros.
Existen enteros x y y tales que
ax  by  1
si y sólo si,
mdc a, n  1
Teorema del Residuo Chino
Sean n1 , n2 , , nk enteros positivos
y primos relativos dos-a-dos.
Entonces el sistema de congruencias
x  a1 mod n1 
x  a2 mod n2 

x  ak mod nk 
tiene una solución única módulo
N : n1n2 nk
Además, dicha solución se puede
expresar como
x  a1 N1 y1  a2 N 2 y2    ak N k yk  mod N 
donde
N : n1n2 nk
N j : N / n j
N j y j  1 mod n j 
Lo cual implica
O sea,
N
N , n   1
j
1
j
 yj
j
Grupo Z
*
n
Sea n un entero positivo. Entonces
el conjunto
Z :  a  Z n | mdca, n   1 
*
n
es un Grupo con la operación de
multiplicación en Z n .
Inclusive el número de elementos
*
que hay en Z n es  n .
Es decir
 
# Z   n 
*
n
Donde  es la función de Euler.
Función  de Euler
Denotaremos por  n la cantidad
de enteros de entre el 1, 2,..., n
que son primos relativos con n.
Por ejemplo:
 12  4
ya que los enteros 1, 5, 7 y 11 son los únicos
primos relativos del 1 al 12 con el 12.
Teorema:
Si p y q son dos números primos
diferentes, entonces
  pq     p   q 
  p  1q  1
 pq  q  p  1
Demostración:
Si expresamos los qp números como sigue:
1
p 1
2 p 1 
2
p  2 2p  2 
3
p 3 2p 3 



p
2p
3p
q  1 p  1
q  1 p  2
q  1 p  3


qp
entonces todos los q múltiplos de p:
p, 2 p, 3 p, , qp
dividen a qp. Entonces hay que restarle q
términos a qp.
sigue
Análogamente todos los p múltiplos de q
q, 2q, 3q, , pq
dividen a pq. Entonces también hay que
restarle ahora p términos a qp.
Por ser p y q números primos, en las dos listas
que acabamos de dar de los factores de qp el
único término que se repitió fue el qp mismo.
Entonces hay que sumarle un término qp.
Además por ser p y q números primos, estos
son los únicos factores que tiene qp. Así
  pq  pq  q  p  1
Por ejemplo:
 15   3* 5
1
6
11
2
7
12
1 4 7 10 13
3
8
13
2 5 8 11 14
4
9
14
3 6 9 12 15
5 10 15
5 múltiplos de 3
3 múltiplos de 5
 15   3* 5  15  3  5  1  8