Tema

3

Teoría elemental de números

Divisibilidad en Z. Algoritmo de Euclides, básico y extendido. Nºs primos. Teorema fundamental de la aritmética. Principio de inducción. Ec. Diofánticas. Congruencias : teorema chino de los restos, criterios de divisibilidad, sistemas de numeración.

Siendo a,b " Z, diremos que b>a, si existe un natural n tal que b=a+n.

Siendo a,b " Z, diremos que a | b , si existe un entero q tal que b=q·a

Principio del buen orden : `Todo subconjunto no vacío de Z+ tiene un 1er elemento'

Lo usaremos cuando veamos la inducción finita. Notese que el principio del buen orden esta definido para Z, y no se cumple por ejemplo en Q+ o R+.

Propiedades de la suma y el producto en Z

Son operaciones internas en Z

Son asociativas y conmutativas

Ambas tienen neutro, el de la suma es 0 y el de la multiplicación es 1.

El producto es distributivo respecto a la suma : a·(b+c)=(a·b)+(a·c)

Si a·b=0 ! a=0 o b=0

Todo elemento tiene opuesto. (un nº operado con su opuesto es 0)

De estas propiedades se desprende que (Z,+·) es un dominio con 1, y que (Z,+) es un grupo conmutativo o abeliano.

Propiedades de Z respecto a la suma y el producto : (chorradas)

a) a·0=0

b) a(-b)=-(ab), a(-1)=-a

c) Si a"0 , ab=ac ! b=c

d) Si a"0 y a|b ! a|bx " x " Z

e) Si a"0, b"0 a|b y b|c ! a|c

f) Sea a"0 si a|b, a|c !a|(cb+yc) para cq. par de enteros x e y

g) a,b>0, a|b !a"b

h)a"0,b"0, a|b, b|a ! a=b ó a=-b

k) Si a"b y m>0!am"bm

y m<0! am"bm

Demostración :

a) a·0=a·(0+0) ! a·0+a·0= 0·a

Sumando su opuesto -a·0 y queda 0+a·0=0 Como 0=neutro de la suma nos queda a·0=0

b) Hay que demostrar que a (-1)=-a

1+a·-1·a=(1+(-1))a=0·a=0

c) a"b , ab=a·c demostrar que c=b

ab+(-ac)=ac+(-ac)

ab-ac=0 ! a(b-c)=0 2 casos : a=0 NO, y b-c=0 ¡ b=c!

g) b=qa =a+...+a=a+(a+...+a) (q>0) q-1"0

k) a"b b·a"0

Valor absoluto : Es una aplicación f :Z!Z que a cada m "Z, le asocia |m|

Propiedades del valor absoluto en Z (chorradas)

|a| " 0

|a|=0 ! a=0

|a·b| = |a|·|b|

|a+b| " |a|+|b|

k>0 y |a| " k ! -k " a "k

Ejercicio : Probar que si a,b"Z y b"0 ! |a|"b ! a"b y -a"b :

`!' |a|"b ; entonces :

- |a|=a, a"0 ! |a| = a " -a "b

- -a, a<0 ! -a=|a|"b ...

`!' a"b y -a"b. El |a| puede ser a"b o -a"b ! |a|"b

Teorema de la división : Si a"Z, b"N. Entonces existen unos únicos q, r " Z / a=q·b+r, 0"r<b

(Viene a decir que si divides 2 números, no te va a salir de cada vez un cociente y resto diferentes)

A los números a, b, q y r se les llama dividendo, divisor, cociente y resto.

Demostración :

Sea bq el mayor múltiplo de b que es menor o igual que a, entonces b·q " a < b·(q+1)

Si definimos r=a-bq entonces

0"r = a-bq < b(q+1)-bq = b

asi r y q satisfacen las condiciones.

Ahora demostramos la unicidad de q y r. Si existen r1 y q1, r2 y q2 con

a= bq1+r1 = bq2+r2 , r1"r2

tendremos que b(q2-q1)=r1-r2, luego b|(r1-r2) y asi teniendo en cuenta que si x|y ! |a|"|b|, entonces |b| " |r1-r2| .

Como 0"r1<b y 0"r2<b es obvio que |r1-r2| < b = |b|,

que contradice la desigualdad |b| " |r1-r2|, luego r1-r2=0, asi r1=r2 y q1=q2.

Ejemplo : 3 dividido por 7 : 3=0·7+3, 0"3<7

7 dividido por 3 : 7=2·3+1, 0"1<3

Ejercicio :

Utilizando el algoritmo de la división probar que todo entero impar al cuadrado es múltiplo de 8 más 1.

n=2k+1 ! n2=8m+1

Dado un entero n cualquiera al dividirlo por 4 n=q4+r, 0"r<4, r=0,1,2,3

Si n impar ! r=1,3 (4q+1)2 = 16q2+8q+1 = 8(2q2+q)+1

(4q+3)2 = 16q2+24q+1 = 8(2q2+3q+1)+1

Todo entero que sea a la vez un cuadrado y un cubo es de la forma 7k o 7k+1

64=82=43, 64=q7+1, n=q7+r, 0"r<7, r=0,1,2,3,4,5,6

Si a"Z a=x2=y3, con x,y"Z

(7q+r)2 = 49q2+14qr+r2 = 7(7q2+2qr)+r2

Los resultados serían : 0,1,4,9 = 7·1+2, 16=2·7+2, 25=3·7+4, 36=5·7+1

Todo cuadrado sería : 7k, 7k+1, 7k+2 o 7k+4

Para el cubo sería :

(7q+r)3 = 73q3+3·72·q2·r + 3·7·q·r2 + r3 = 7·(72q3 + 21q2·r + 3q·r2) + r3

Los resultados son : 0,1,8 = 1·7+1, 27=3·7+6, 64=9·7+1, 125=17·7+6, 216=30·7+6

Todo cubo sería : 7k, 7k+1, 7k+6

Operador MOD

Sean a,b enteros con b"0, si a=qb+r, 0 "r<|b| entonces tenemos que `a MOD b = r'

Ejemplo : 3 mod 7=3, 7 mod 3=1, -15 mod 8=1, -23 mod -17=11

Propiedades :

Sean a,b,c,d,m " Z, m"0,

a mod m=b mod m,

c mod m=d mod m,

entonces (a+c) mod m = (b+d) mod m de la misma forma que (a·c) mod m=b·d mod m.

Demostración : apuntes pág. 7

Maximo Común Divisor

Sea a,b,d"Z, d"0, se dice que d es MCD de a,b si cumple : - d|a, d|b

- si " d´ tal que d´|a y d´|b ! d´|d

Propiedades :

Si " mcd (a,b) es único

El mcd de una sucesión finita sería : mcd (a1, a2 , ...a) =d / d>0 y cumple : - d|

- Si " d´ / d´|
! d´|d

Algoritmo de Euclides (Es el algoritmo para el calculo del mcd de dos nºs a y b)

Al calcular mcd(a,b) podemos suponer que a"b>0

Dividimos a por b : a=q1·b+r1 con 0"r1<b

pueden ocurrir 2 cosas :

divido b por r1 : b=q2·r1+r2 , 0"r2<r1

Tenemos que :

r2=0, r1|b !r1=mcd (r1,b)=mcd(a,b)

o bien r2"0, divido r1 por r2 : r1 = q3·r2+r3, 0 " r3 <r2, r1 > r2 > r3 >...> rn

El proceso siempre llegara a un paso de manera que

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

rn-1 = mcd(rn-1,rn-2) = mcd(rn-2, rn-3) = mcd(r1,b) = mcd(a,b)

Algoritmo extendido de Euclides

........................................................

Teorema (consecuencia del algoritmo de Euclides) uned24,ap36, Dems. en pág.10 apuntes

Para k"Z : mcd (ka,kb) = |k|·mcd(a,b)

Es decir : si d | (a,b) también se cumple que kd | (ka, kb) , y si además d es mcd, kd también sera mcd .

Teorema de Bedut

Sean a,b " Z, a,b>0

" mcd(a,b)=d entonces d=  a+  b para algunos ,  " Z

Dems: s={ax+by>0 / x,y " Z }

mcd(4,6)

S={x4+y6>0 / x,y " Z}= {1·4+1·6,-1·4+1·6, ............??

S " " a=1a+0b>0, a " S

" d " S d menos el elemento de S

d ! d=  a+  b con  ,  " Z

¿d=mcd (a,b)?

1) d|a

a=qd+r " Z " Z

r=aqd=a-q(  a +  b)=(1-q  ) a+ (-q) b " ......??

2) d|b (igual que en a) )

d´|a y d´|b ! d´|d

! !

d´|a d´|b ! d´|  a +  b =d

Nºs primos y teorema de factorización

Decimos que p"Z / p>1, es primo sus únicos divisores son 1 y p.

En caso contrario decimos que es compuesto y podra expresarse como p=a·b con 1<a<p y 1<b<p

Decimos que 2 nºs son primos entre sí, cuando mcd(a,b)=1, (que implica 1=a+b)

Para todo m " Z, 3m+11 y 2m+7 son primos entre si.

Todo entero puede expresarse como 6k, 6k+1, 6k+2, 6k+3, 6k+4, ó 6k+5 (uned31)

Lema de Euclides uned31

Para a,b,c"Z, a,b,c>1, entonces si mcd(a,c)=1 y c|a·b ! c|b

O sea, si a,c son primos entre sí, y c|a·b, entonces c también divide a b.

Demostración : " x,y " Z tal que 1=ax+cy ! b=bax+byc, c|ab ! c|abx, trivialmente c|b y c, ! c|abx+byc=b

Corolario : Sea p " Z >1, p primo ! para cualquier entero a,b si p|ab ! p|a y p|b

Teorema fundamental de la aritmetica uned33

Sea n>1,n"Z, entonces : " nºs primos p1,...,pk / n=p1·p2·...·pk con p1"p2"..."pk

???: Esta factorización es única si n= q1·q2·...·qm con q1"q2"..."qm entonces k=m y pi=qi " i=1,2,..,k

O sea, todo entero>1 puede expresarse como un producto de primos. Además, este producto es único.

Demostración :

Reducción al absurdo, supondremos lo contrario: " S"" / S={a " Z,a>1/ a no es factorizable}

Puesto que todos sus elementos son positivos " un primer elemento b :

- si b es primo, para n=p1·p2·...·pk con p1"p2"..."pk tendremos b=b

- si b no es primo es que es compuesto(=expresable como producto de 2 nºs),

y por tanto b=u·v con 1<u<b y 1<v<b (pero no pueden ser >b, poque b ya es el 1er elemento de S)

O sea, que ni es primo ni no primo, por lo tanto no existe, y S=" .

Por consiguiente, (y sin acritud) cualquier nº"Z y >1 es factorizable.

Continua ... demostración unicidad en uned34

Corolario uned 35

Sea n " Z con |n|>1, entonces n tiene una factorización única de la forma n=±(p1)1 ... (pt)t donde t"1, los pi son primos distintos con p1<...<pt y i"1 para 1"i"t

Teorema : El nº de primos es infinito uned36

Demostración :

Supongamos P={p1,...,pt}, conjunto finito de nºs primos,

y hallemos la contradicción buscando un nº primo que no se halle en ese conjunto m=(p1·p2·...pt)+1 ,

vemos que m>1 por lo tanto m=q1·...qs donde los qi son primos (por el ta fundamental de la aritmetica)

? Y puesto que m MOD pi=1, ningún pi es factor primo de m.

Por lo que cada qi, en particular q1 son primos
P, que es una contradicción, y por tanto P es infinito.

Corolario : pn+1 " (p1·p2...pn)+1 (explicación en uned37)

Teorema uned38

Sea a"Z y >1, entonces si para todo primo p / p"
no se cumple p|a, a es primo

O sea, si todo primo " que la raiz cuadrada de a, no divide a a, entonces es que ese a es primo.

Demostración :

Si a no fuera primo, sería compuesto : a=b·c con 1<b<a, 1<c<a.

Podemos suponer que b"c, y entonces tendríamos que b2 " b·c y por tanto b "

Si b es primo ! contradicción!, porque por hipotesis a no es divisible por ningún primo p"

E idem si no lo es, porque b tiene factores primos y siendo p uno cualquiera de ellos : p<b y así p<b<

Contradicción en ambos casos, por lo que la suposición inicial (a no primo), es falsa : ¡ a es primo ! .

MCD a partir de la factorización de A y B (uned 41, hoja 39)

.........................................................................

Principio De Inducción Finita

Sea S un conjunto de naturales. Si cumple :

1) 1"S,

2) para cada k"1, si k"S ! k+1"S

entonces S=N.

Lo utilizaremos para demostrar que cierta propiedad P se satisface para todo nº natural n.

Demostración : (por reducción al absurdo)

- Supongamos que S satisface 1 y 2, pero S"N.

- Sea A=N-S"" ( aqui podemos aplicar PBO porque A=conj. de enteros positivos)

por el PBO existe un a"A menor elemento de A, que sera "1 (porque 1"S), y por lo tanto a"2 y 1" a-1<a

- (a-1)
A ( pq para a=2 daría 1) , entonces es que a-1"S y por la 2º condición :(a-1)+1"S ! a"S (a-1+1=a)

- ¿¿ a"S y a"A ?? contradicción basada en suponer que S"N, por lo tanto S=N ( porque o son = ó ")

Los pasos a seguir al aplicarlo son :

1) Definir el conjunto S={ n"N tales que P(n) es verdadera }

2) Probar que 1"S ( base )

3) Suponer que k"S para un k arbitrario / k"1 ( paso inductivo )

4) Demostrar que k+1"S

Corolario uned53

Es igual que el principio de inducción pero en vez de para" N, para un subconjunto propio suyo : [n0...")

Sea n0 un número fijo / n0 " Z, sea M={ n " Z, n"n0 } . Si para S"M, S cumple :

1) n0 " S

2) si k " S, k " n0 ! k+1 " S

entonces S=M

Corolario uned54

Parecido al anterior, esta vez en un subconj. propio de Z : [n0...")

Sea P(m) una propiedad con m"Z y n0"Z y fijo, que cumple :

1) P(n0) es cierta

2) Si P(k) con k"n0 , ! P(k+1) cierta

entonces P(m) cierta para " m"n0

Principio Fuerte De Inducción uned55

Es lo mismo que el de inducción finita pero además k<n

Sea S un conjunto de naturales. Si cumple :

1) 1"S

2) para todo n>1 y todo k / 1"k"n, si k"S ! n"S

entonces S=N

Demostración : (por reducción al absurdo) (Es casi la misma que la del otro)

- Supongamos que S satisface 1 y 2, pero S"N.

- Sea A=N-S"", por PBO " n0"A / n0>1 y n0=menor elemento de A. Además 1,2,...,n0-1"S

- Por 2) n0"S : contradicción!

Así pues, N-S=" y S=N.

Corolario uned58

lo mismo de antes

Sea P(n) una propiedad para los naturales. Si cumple :

1) P(1) cierta

2) para cada n0>1, P(k) cierta para todo k / 1"k"n0 ! P(n0) cierta

entonces P(n) se satisface para todo N

Corolario uned58

lo mismo para n0 en vez de 1

Sea n0 un número fijo / n0 " Z, sea M={ n"Z, n"n0 } . Si para S"M, S cumple :

1) n0 " S

2) para cada n>n0 y cada k / n0"k<n0, si k"S ! n"S

entonces S=M

Corolario uned58

lo mismo con n0...n1

Sea P(m) una propiedad con m"Z y n0"Z y fijo, que cumple :

1) P(n0) es cierta

2) para cada n1>n0 y cada k / n0"k<n1, si P(k) es cierta ! P(n1) es cierta

entonces P(n) cierta para " n"n0

Ejemplo 1.3-18 y 1.3-20

ECUACIONES DIOFANTICAS

Con este nombre se designan una amplia clase de ecuaciones algebraicas con más de una indeterminada en un particular sistema de números como son Z y Q.

Teorema

Para a,b,n"Z, tenemos que ax+by=n tiene solución entera x0, y0 ! " d=mcd(a,b) | n

Demostración :

`!'

`!' d=mcd(a,b) y por Bedut =a+b con ,"Z

n = d = a + b , x=, y=

Teorema Uned 65

Sea ax+by=n con d|n, y a,b,n enteros no nulos.

Entonces la solución particular de la ecuación ax+by=n tiene la forma

Teorema Uned 70

La ecuación diofántica x2-y2=n con n>0, tiene solución si y solo si n se puede factorizar como producto de dos números de la misma paridad, es decir ambos pares o ambos impares. Si existn, las soluciones de la ecuación tienen la forma
, donde a y b recorren todos los números de la misma paridad y tales que n=ab.

Algoritmo de factorización de Fermat Uned 72

Sea n un número natural impar. Si n es compuesto se tiene que n=ab donde a y b también han de ser impares, y podemos suponer que a"b>1. Por el teorema anterior se puede escribir

Luego estudiar si un número impar es compuesto es un problema equivalente a resolver la ecuación x2-y2=n , que puede escribirse x2-n=y2.

El primer paso es determinar el mínimo entero positivo q que satisfaga q2"n y posteriormente habra que estudiar si alguno de los números q2-n, (q+1)2-n, (q+2)2-n, ... es un cuadrado.

Este proceso no es indefinido ya que
.

Esta solución corresponde a la factorización trivial n=n1. Luego los únicos valores que hay que estudiar son aquellos números m que satisfacen q"m<
.

Si para ninguno de estos números m, m2-n es un cuadrado, entonces n sera primo.

Teorema Uned 74

Las soluciones de la ecuación pitagoprica x2+y2=z2 que satisfacen : mcd(x,y,z)=1, 2|x, con x,y,z>0

vienen dadas por las fórmulas x=2st

v=s2-t2 ,

z=s2+t2

para naturales s,t, s>t, con distinta paridad, tales que mcd(s,t)=1.

CONGRUENCIAS

Definición

Sea m>0. Dados a,b " Z 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 mod(m) ! m|(a-b) .

Propiedades

"m es una relación de equivalencia en Z

..........................................................................

Para a,b enteros, se cumple que a"b mod(m) ! a y b tienen el mismo resto al ser divididos por m. (Uned 90)

Si h|a, h|b, mcd (h,m)=1 y a"b mod(m), entonces

Si a"b mod(m) entonces ha"hb mod(m)

Teorema Uned 94

La ecuación ax"b mod(m) tiene solución ! d=mcd(a,m)|b. Ademas el número de soluciones no congruentes módulo m es exactamente d.

Teorema Chino del Resto Uned 96

El sistema de congruencias xai"bi mod(mi), i=1,2, ..., k donde mcd(mi , mj)=1 si i"j y mcd(ai , mj)=1 para 1"i"k , tiene una única solución x0 módulo m1m2...mk y las demas soluciones son de la forma x=x0+m1m2...mk, "Z.

Teorema de Euler Uned 102

Sean a y m dos números enteros con m"1, entonces si mcd(a,m)=1 se tiene que a(m)"1 mod(m).

Pequeño teorema de Fermat

Si p es un número primo que no divide al número a, entonces ap-1"1 mod(m).

Teorema de Wilson Uned 104 y ver ejemplo 1-5.31

Si p es un número primo, entonces (p-1)! " -1mod(p).

SISTEMAS DE NUMERACIÓN

En esta sección se estudian sistemas de numeración diferentes al usado convencionalemente, es decir, sistemas no decimales.

Terorema Uned 110

Sea b"2 un número natural llamado base. Todo número n"N tiene representación única en base b de la forma

n = akbk + ak-1bk-1 +...+ a1b + a0 ,

para algún k"0, con 0"ai<b, i=0,1,...,k, y con ak "0.

Teorema (esto es de congruencias pero se usa en el siguiente teorema) Uned 93

Supongamos que para 1 " i " n se tiene que ai"bi mod(m), entonces

.

Criterio de divisibilidad por k Uned 115

Sea n un número natural. Como n = at10t + at-110t-1 +...+ a110 + a0 , podemos escribir
.

Consideremos ahora losrestos de la división de 10i por k para i=0,1,...,t. Supongamos que son ro, r1, ..., rt, donde r0=1, ya que 100=1 y estamos suponiendo k"2.

Tenemos entonces,

100"r0 mod(k), 101"r1 mod(k),...,10t"rt mod(k).

En congruencias vimos que si a"b mod(m) entonces ha"hb mod(m), y por el teorema de arriba, se tiene que

luego n es divisible por k si y solo si
es divisible por k.