Matematica discreta universidad salesiana de bolivia ing. De sistemas



Descargar 2,9 Mb.
Página11/38
Fecha de conversión02.07.2017
Tamaño2,9 Mb.
1   ...   7   8   9   10   11   12   13   14   ...   38

Algunas otras sumatorios.-



























3.5 Algoritmo de la división
 

Definición.-

Dados enteros a, b con b 0 existen enteros q y r tales que


a = b q + r   y   0 r |b|

Al número a se le llama dividendo.


Al número b se le llama divisor.
Al número q se le llama cociente.
Al número r se le llama residuo.

En el caso particular que a y b sean enteros positivos, se trata de hallar el número de veces que el dividendo contiene al divisor. Este número se llama cociente, y lo que queda se llama residuo.


Ejemplo:

Si queremos hallar el resultado de dividir 19 entre 5 tenemos: 19=5x3+4, es decir, que el cociente es 3 y el residuo 4. Se puede observar que el residuo 4 es mayor que 0 y menor que 5 que es el divisor.


Ejemplo:

Si queremos hallar el resultado de dividir 23 entre 7 tenemos: 23=7x3+2, lo que quiere decir que el cociente es 3 y el residuo es 2.

Cuando el residuo es cero, se dice que la división es exacta y en este caso se cumple que el dividendo es igual al divisor por el cociente.

Si la división es exacta, se dice que el divisor b divide al dividendo a, y esto se simboliza de la manera siguiente b|a. Lo anterior motiva la siguiente definición.


3.6 Divisibilidad

Definición.- Un entero a es divisible por un entero b, o b es divisor de a cuando el residuo es cero. Por tanto existe c Z tal que a=bxc.
Ejemplo:

7 es divisor de 35 porque: 35 = 5 veces 7.

Se dice entonces que 7|35.

Ejemplo:

9 es divisor de 27 porque: 27 = 3 veces 9.

Se dice entonces que 9|27.

Cuando un entero b no es divisor de un entero a se dice que b no divide a a o que b no es divisor de a y se denota por ba.


Teorema.

Todo entero que es divisor de otros es divisor de la suma de ellos.


 Ejemplo:

Sea 7 que divide a 35, 42 y 56. Luego: 35 = 5 veces 7, 42 = 6 veces 7 y 56 = 8 veces 7.

Sumando ordenadamente resulta: 133 = (5 + 6 + 8) veces 7.

Luego 133 = 19 veces 7. Se concluye que 7 divide a 133.

El teorema se demuestra generalizando este resultado. Sea d divisor de A, B, C y sean a, b, c sus cocientes respectivos.

Luego: A = ad, B = bd y C =cd

Se concluye: A + B + C= (a + b + c) d

Lo anterior se puede reescribir de la forma siguiente: Sí dï A, dï B, dï C entonces dï (A + B + C).


Teorema. Todo entero que es divisor de otro es también divisor de los múltiplos de ese otro.
Ejemplo:

Como 2 divide a 6, luego 2 dividirá a 4x6 = 24.

En efecto: 24 = 6 + 6 + 6 + 6.

Ahora bien: 2 divide a 6, luego dividirá a 4 veces 6, es decir, a 24.

Generalizando, si d|A entonces d|nA con nZ.

Teorema. Todo entero que es divisor de otros dos, es divisor de su diferencia.
Ejemplo:

Sea 3 que divide a 27 y a 18. Se tiene: 27 = 9 veces 3 y 18 = 6 veces 3. Restando ordenadamente tenemos: 27 - 18 = (9 - 6) veces 3. Luego 9 = 3 veces 3.

Generalizando, si d es divisor de A y B tal que a y b son sus cocientes respectivos, entonces: A = ad y B = bd. Restando ordenadamente se tiene: A - B = (a - b) d.

Lo anterior se puede reescribir en la forma siguiente:

d|A y d|B, luego d|(A - B).

Teorema. Todo entero que divide a otros dos, divide al residuo de la división de éstos.
Ejemplo:

Sea 7 que divide a un dividendo 49 y a un divisor 35. Como el residuo de dividir 49 entre 35 es 14, luego 7 divide a 14.

Generalizando este resultado se tiene:

Sea la división de A entre B con cociente q y residuo r y sea d un entero que es divisor de A y de B, es decir: A = B q + r con 0 r IBI. Luego A = B q + r, por el algoritmo de la división.

Entonces, r = AB q. Como d divide a B, dividirá a B q. Si divide a A y B q divide también a su diferencia AB q. Luego d divide a r.
Teorema. Si dos enteros divididos por un tercero dan residuos iguales, la diferencia de estos dos números es divisible por el tercero.

Demostración

Sean a y b dos números que divididos por d dan residuo r y cocientes q y q´ respectivamente, o sea:

a = d q + r y b = d q´+ r.

Restando ordenadamente se tiene a - b = d (q - q´). Luego d divide a la diferencia entre a y b.

Este teorema tiene gran importancia cuando se estudia una teoría llamada teoría de congruencias.

El recíproco de este teorema también se cumple, es decir: Si la diferencia de dos números es divisible por un tercero entonces estos números divididos por el tercero dan residuos iguales.


Ejemplo:

Usando el algoritmo de la división, demuestre que cada entero impar es de la forma 4k+1 o 4k+3 con kZ

Cualquier entero al ser dividido por cuatro deja residuo 0 o 1 o 2 o 3. Es decir, todo entero es de una de estas formas: 4k, 4k+1, 4k+2, 4k+3.

De lo anterior se tiene que cualquier número impar es de la forma: 4k+1 o 4k+3.


Ejemplo:
 Usando el algoritmo de la división, demuestre que todo número entero se puede escribir en una de las formas 3s, 3s+1, 3s+2.

Sea n un entero cualquiera. Luego al ser dividido por 3 se obtiene residuo 0 o 1 o 2. Entonces se cumple alguno de los tres casos:

n = 3s
n = 3s+1    donde s es el cociente entero de dividir n por 3.
n = 3s+2
 

Ejemplo:

Muestre con un contraejemplo que si a|(b + c) no necesariamente a|b o a|c.

Sea a = 4; b = 5; c = 3. Se cumple 4|(5 + 3) pero 45 y 43
Ejemplo:

Muestre que si a es un entero arbitrario luego 2|a(a + 1).

Si a es par, entonces a(a + 1) es par.

Por tanto a(a + 1) = 2s, luego 2|a(a+1).

Si a es impar luego a + 1 es par, o sea que a(a + 1) es par.

Por tanto a(a + 1) = 2k, luego 2|a(a+1).


3.7 Máximo Común Divisor

Definición.- Se llama común divisor de dos enteros a un entero que los divida.

Ejemplo:

2, 3 y 6 son divisores comunes de 18 y 24.



Definición.- Se llama máximo común divisor de dos enteros, al menos uno de ellos diferente de cero, al mayor entero que los divide exactamente.

De la definición anterior es claro que el máximo común divisor de dos enteros es siempre un entero positivo.



Ejemplo:

Sean a = 24, b = 27. Escribamos el conjunto de todos los divisores comunes positivos de 27 y 24. Sea S este conjunto: S = {1, 3}. Luego el máximo común divisor de 24 y 27 es 3.



Ejemplo:

Halle el máximo común divisor de 32 y 48.

Sea S el conjunto de los divisores comunes positivos, entonces, S= {1,2, 4, 8, 16}.

Luego el máximo común divisor de 32 y 48 es 16.

Si d es el máximo común divisor de dos números a y b se escribe: d = M.C.D.(a,b).

Teorema. Dados los enteros a y b no ambos cero, existen enteros x y y tales que M.C.D.(a, b) = ax + by.

Ejemplo:

Como M.C.D.(24, 27) = 3. Entonces se cumple 3 = 27x(1) + 24x(-1).

En este caso x = 1 y y = -1.

Más adelante se estudiará un método expedito para hallar x y y.



Definición.- Dos enteros a y b no ambos cero se llaman primos relativos si M.C.D.(a, b) = 1.

Ejemplo:

Sea a = 28, sus divisores positivos son {1, 2, 4, 7, 14}. b = 25, sus divisores positivos son {1, 5}.

El único divisor común es 1. Luego 25 y 28 son primos relativos.

Teorema. Dados dos enteros a y b no ambos cero; a y b son primos relativos sí y sólo sí existen enteros x e y tales que 1 = ax + by.

Demostración: Si a y b son primos relativos entonces M.C.D.(a, b) = 1. Luego por teorema 2.3.3 1 = ax + by.

Ahora, sea d = M.C.D.(a, b), luego d|a y d|b y por teoremas 2.2.2 y 2.2.3 se tiene que d|ax + by, o sea que d1. Necesariamente d = 1.



Corolario. Si M.C.D.(a, b) = d, entonces se tiene que M.C.D..
Recíprocamente, si d|a, d|b y M.C.D. entonces M.C.D.(a,b) = d.

Ejemplo:

Como M.C.D.(24, 27) = 3, entonces se cumple que:

M.C.D. = M.C.D.(8, 9) = 1.

Teorema. Sean a, b, c enteros. Sí a|c y b|c y M.C.D.(a, b) = 1, entonces ab|c.

Demostración. Como: a|c,c = ar para algún r. b|c,c = bs para algún s.

Sea d = M.C.D. (a, b). Entonces d = 1, entonces existen enteros x, y tales que 1 =ax + by.

Multiplicando por c: c = acx +bcy. Implica que c = a(bs)x + b(ar)y = ab(sx + ry), o sea que ab|c.

3.7.1 Lema de Euclides.a|bc y M.C.D.(a, b) = 1, entonces a|c.

Demostración

Como M.C.D.(a, b) = 1, luego 1 = ax + by para algún par de enteros x e y. Luego c = (ac)x + (bc)y.

Además a|ac.

a|bc por hipótesis.

Se sigue entonces: a|(ac)x + (bc)y; de donde .

Se concluye que a|c.

Ejemplo:

Si a y b no son relativamente primos, el resultado es falso. Así por ejemplo, sean a = 12, b= 9, c = 8.

Se tiene 12|9x8, sin embargo 129 y 128, y esto no se cumple porque M.C.D.(12, 9) = 3 ¹ 1.

Teorema. Sean a y b enteros no ambos cero. Si se cumple que d = M.C.D.(a, b), entonces:
a) d|a y d|b.

b) Sí c|a y c|b entonces c|d.


1   ...   7   8   9   10   11   12   13   14   ...   38


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal