Teoria elemntal de numeros

Teoría elemental de números
Matemática discreta

Matemática discreta. Teoría elemental de números

1

Resultados previos
• Axioma: todo subconjunto no vacío de N tiene mínimo, con el orden usual en N. • Toda sucesión decreciente en N converge.

Matemática discreta. Teoría elemental de números

2

Divisibilidad

Divisibilidad
• Si a,b∈Z, a divide a b , a⎥ b, si ∃c∈Z tal queb=a·c. Se dice también que b es múltiplo de a o que a es divisor de b. En caso contrario, a∤b, a no divide a b.

Matemática discreta. Teoría elemental de números

3

Divisibilidad

Propiedades de divisibilidad
∀a, b, c ∈Z • 1⎥ a a⎥ a a⎥ 0 • Si a⎥ b y b⎥ a, entonces a=± b • a⎥ b, entonces a⎥ b·c • a⎥ b y a⎥ c, entonces a⎥ bx+cy ∀x,y ∈Z • Si x=y+z, a⎥ x, a⎥ y, entonces a⎥ z ∀x,y,z ∈ZMatemática discreta. Teoría elemental de números

4

Divisibilidad

División euclídea
Dados a,b∈Z siendo b≠0, existen únicos q,r∈Z tales que a=b·q+r, con 0≤ r1, p es primo si ∀n∈N n⎥ p ⇒ n=p ó n=1 • Todo natural mayor que 1 es divisible por, al menos, un número primo.

Matemática discreta. Teoría elemental de números

6

Números primos

Teorema fundamental de la aritmética
• ∀n∈N, n>1,existen únicos p1, .., pr∈N y existen únicos α1, .., αr∈N* tales que n= p1α1...prαr Todo natural se descompone de manera única como producto de potencias de números primos.
Matemática discreta. Teoría elemental de números 7

Números primos

Máximo común divisor
Dados a,b∈Z no simultáneamente nulos. • d es divisor común de a y b si d⎥ a y d⎥ b. • El máximo común divisor de a y b, mcd(a,b), esel mayor de los divisores comunes de a y b. • a y b son primos relativos si mcd(a,b)=1. • Si b≠0 y r es el resto de la división euclídea entre a y b, entonces:
– Los divisores comunes de a y b son divisores de r. – Los divisores comunes de b y r son divisores de a.
Matemática discreta. Teoría elemental de números 8

Números primos

Algoritmo de Euclides
• Dados a,b∈Z* y r el resto de ladivisión euclídea entre a y b, entonces mcd(a,b) = mcd(b,r) • Nos proporciona un algoritmo para calcular el mcd utilizando la división euclídea. • mcd(a,b) = mcd(⏐a⏐,⏐b⏐)

Matemática discreta. Teoría elemental de números

9

Números primos

Algoritmo de Euclides 2
• Sean a,b∈Z+ con a≥b>0, llamamos r0=a y r1=b. Aplicamos sucesivas veces la división euclídea: r0=q1·r1+ r2. r1=q2·r2+ r3.................

0< r2< r1 0< r3< r2 0< rn< rn-1 rn+1=0

rn-2=qn-1·rn-1+ rn rn-1=qn·rn+ rn+1 Entonces, el mcd(a,b)=rn
Matemática discreta. Teoría elemental de números

10

Números primos

ejemplo
• mcd(6,9)=3 9=6·1+3 6=3·2+0 El último resto distinto de 0 es 3, el mcd. • mcd(24,62)=2 62=24·2+14 24=14·1+10 14=10·1+4 10=4·2+2 4=2·2+0 El último resto distinto de 0 es 2, el mcd.
Matemáticadiscreta. Teoría elemental de números 11

Números primos

Teorema de Bezout
Dados a,b∈N* y mcd(a,b)=d, entonces ∃x,y∈Z tales que d=ax+by Identidad de Bezout mcd(a,b)=1 ⇔ ∃x,y∈Z tales que 1=ax+by • Dados a,b∈Z se verifica
– Si p⎥ a·b y p es primo, entonces p⎥ a ó p⎥ b. – Si p⎥ a·b y mcd(a,p)=1, entonces p⎥ b.
Matemática discreta. Teoría elemental de números 12

Ecuaciones diofánticasEcuaciones diofánticas
• Buscamos soluciones enteras de una ecuación. • Ecuación diofántica lineal en dos variables ax+by=c a, b, c ∈Z • Diofanto, s. III a.C.

Matemática discreta. Teoría elemental de números

13

Ecuaciones diofánticas

Ecuaciones diofánticas 2
• Dados a,b,c∈Z, mcd(a,b)=d, y dada la ecuación ax+by=c
– Si d∤c la ecuación no tiene soluciones enteras. – Si d⎥ c laecuación tiene infinitas soluciones enteras. A partir de una solución particular (x0,y0) calculamos el resto de las soluciones x= x0+(b/d)·n y=y0-(a/d)·n
Matemática discreta. Teoría elemental de números 14

n ∈Z

Ecuaciones diofánticas

Ecuaciones diofánticas 3
• Para calcular una solución particular:
– dividimos ax+by=c por mcd(a,b)=d y obtenemos a´x+b´y=c´ – como mcd(a´,b´)=1, por la...