Matemática discreta

Teoría de números. Algoritmos división y Euclides. Primos. Aritmética. Ecuaciones diofánticas. Congruencias. Grafos eulerianos y hamiltonianos. Mapas

  • Enviado por: El remitente no desea revelar su nombre
  • Idioma: castellano
  • País: España España
  • 12 páginas
publicidad
publicidad

Apuntes de Matemática discreta.

Algoritmos de División y Euclides.

Si a divide a b, lo representamos así: aøb.

Algunas propiedades útiles:

a<>0 y aøb, entonces aøbx, para todo entero x

aøb y bøc, entonces aøc.

aøb y aøc, entonces aø(bx+cy), para todos los enteros x, y.

Si a y b son positivos, entonces aøb implica a£b.

Si a y b son distintos de 0, entonces si aøb y bøa, entonces a=b o a=-b.

Valor absoluto.

øa+bø£ øaø+øbø

Si a y b son distintos de 0, y aøb, entonces øaø£øbø

Algoritmo de la división.

Corolario del algoritmo:

Dados a,b y b<>0, existen q y r tales que a=bq+r, y 0£r<øbø

Módulo:

Dado el corolario anterior para a y b, a MOD b=r.

Propiedades:

Si aMODm=cMODm y bMODm=dMODm

entonces:

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

(ab)MOD m= (cd)MOD m

Máximo común divisor.

Dados a1,a2,….an, su mcd.(a1,a2,…an) es el divisor común d>0 al que cualquier otro divisor común divide.

Propiedades:

Si a y b son enteros distintos de 0, existe un sólo d divisor común y además es el entero positivo más pequeño que puede expresarse como ax+by, siendo x e y enteros.

El m.c.d (a,b)=1 sí y sólo si existen enteros s y t que hacen as+bt=1.

Si a y b son enteros distintos de 0:

Sus divisores comunes son divisores del resto r de la división de a por b.

Los divisores comunes de b y r son divisores de a.

El m.c.d del dividendo y del divisor es el mismo que el m.c.d del divisor y del resto.

Algoritmo de Euclides:

Para calcular el m.c.d de dos números a y b.

Sea a el mayor de los números. Se divide entre b y se obtiene el resto r1. Si r1=0, entonces es b el m.c.d. Si no, se divide b entre el resto r1. Si el resto r2=0, entonces es r1 el m.c.d. Si no, se divide r1 entre r2, y así sucesivamente hasta hasta que salga un resto igual a 0.

Propiedades:

Si k>0, entonces m.c.d(ka,kb)=k*m.c.d(a,b)

Para k<>0, m.c.d.(ka,kb)= økøm.c.d(a,b)

Números primos y Teorema fundamental de Aritmética

Números primos:

p>1 es primo si sus divisores son sólo 1 y p. Si no es primo, es compuesto.

a1,a2…,an son primos entre sí si su m.c.d es 1.

Lema de Euclides:

Sean a,b,c números enteros. Si a y c son primos entre sí y cøab, entonces cøb.

Corolarios:

Sea p>1, entonces:

p es primo sí y sólo si, dados cualquier par a y b de enteros, si pøab, entonces pøa ó pøb.

Si p es número primo y pøa1….an, entonces pøai para algún i.

Teorema fundamental de la aritmética:

Dado cualquier entero mayor que 1, se puede exprear como un producto de números primos, y además, esa expresión es única si se representan los números primos ordenados en el producto de menor a mayor (Puede haber números primos repetidos)

Corolario:

Dado cualquier entero n, y ønø>1, entonces hay una factorización única:

n=±p1a1…..ptat, donde los pi son primos distintos y los ai³1

Propiedades:

Si pn es el primo n-ésimo, entonces, pn£

Vídeos relacionados