Download D - Inicio

UNIDAD II
TEORÍA DE NÚMEROS
Cátedra: Matemática Discreta
Carreras: Lic. E Ing. Sistemas
TUDAW
Prof. Adjunta: Lic. Claudia Isaia
Ayudante 1º: Lic. Elizabeth Castro
Año 2013
Universidad Nacional de Chilecito
Contenidos Unidad 2
Cociente exacto.
Cociente entero.
División Euclídea.
Números primos y números compuestos.
Máximo común divisor. Mínimo común múltiplo.
Cociente Exacto
Cociente Exacto

Al dividir un número entero por otro también entero y
distinto de cero, puede ocurrir que el cociente obtenido sea
o no entero.

Por ejemplo: 16/2=8
11/2=5,5
Por lo tanto la división exacta exigen que el dividendo sea
múltiplo del divisor.
Cociente exacto

De lo explicado anteriormente se desprende que:
Se llama Cociente exacto de dos números naturales D
dividendo y d≠ 0 divisor, al número natural q cuyo
producto por el divisor reproduce el dividendo.
La operación realizada para calcular el cociente
exacto, se llama división exacta y se indica por D/d o
D:d.
Definiciones




Llamaremos múltiplos de un número entero “a” al producto
de “a” por 1,2,3,….
Por extensión se considera múltiplo de “a”, su producto por
0.
Decimos entonces que siendo “a” un número entero y r
cualquier valor entero 0,1,2,3…,la expresión general de los
múltiplos es: b=a.r
Se dice que “a” es divisor de b por que cabe una cantidad
exacta de veces.
Cociente Exacto
Si D es el dividendo y d el divisor entonces podremos decir:
• que D es divisible por d
O
• que d divide a D
O
• que d es un submúltiplo de D
O
• que d es un divisor de D
O
• que D es un múltiplo de d
Cociente Exacto

Este cociente tiene ciertas propiedades:
Si k  0, entonces:
D
Dk

d
dk
Llamando q al primer cociente, será D=dq, con lo que
resultará multiplicando ambos miembros por q,
Dk=dqk=(dk)q
es decir, el segundo cociente también es n.
Cociente Exacto
2.
Si d|D y d1|D1 ,entonces se cumple que:
D D1
DD1
.

d d1
dd1
De acuerdo con la hipótesis de partida y llamando q al
primer cociente será:
D=dq
DD1=dqd1q1=(dd1)(qq1)
D1=d1q1
lo que significa que (dd1)|(DD1)
Cociente Exacto
3.
Si d|D1 ,d|D2 … d|Dl entonces
D
D  D2  ...  Dl
D1 D2

 ...  l  1
d
d
d
d
Probaremos para la suma pero también es válido para la resta.
D1=dq1
D2=dq2
D1+D2+…Dl =d(q1 +q2+…+ql)
…
Dl=dql
Por lo tanto, d|(D1+D2+…+Dl) y su cociente será q1 +q+…+ql
Cociente Entero
Cociente entero
Sean D y d dos números naturales ≠ 0. En general
D no será múltiplo de d, es decir, no coincidirá con
ninguno de los números:
0  d, 1 d, 2d, qd, (q+1)d, …
Pero en la sucesión de múltiplos, existirán dos
consecutivos, por ejemplo, qd y (q+1)d entre los
que se encontrará D.

Cociente entero
Sean D, d dos números naturales, no nulos. Sea q otro
número natural tal que cumpla la relación:
qd <= D < (q+1) d
Entonces, q y q+1 reciben los nombres de cocientes
enteros por defecto y por exceso de la división de D,
dividendo, por d, divisor.
Cociente entero

Ejemplo: D=13 y d=3 entonces
qd < = D < (q+1)d
4  3 <= 13 < (4 + 1 ) 3
Cociente entero por defecto: 4
Cociente entero por exceso: 5
Cociente entero
Reciben los nombres de restos enteros por defecto y por
exceso, los números r y r’ definidos por las igualdades:
r= D-qd ,
r’=(q+1)d – D qd+d-D= d-r
Teniendo en cuenta el ejemplo anterior: D=13 y d=3
r=13-43
r’= (4+1) 3 – 13
r=1
r’= 15-13
r’=2
Cociente entero
Se denomina división entera de dos números naturales
D y d ≠ 0, aquella operación aritmética cuyo objetivo
es el cálculo de los cocientes y restos enteros.
Cociente Entero

Tiene las siguientes propiedades:
1.
La suma de los restos enteros por defecto o por exceso
es igual al divisor:
r=D-qd
r+r’=D-qd + qd+d-D=d
r’=(q+1)d-D
Cociente entero
Ejemplo:
D=19
r+r’=D-qd + qd+d-D=d
d=7
27 <=19< 3 7
r=D-qd
19 - 2  7
19 – 14
5
r’=(q+1)d-D
(2+1) 7-19
21 - 19
2
r+r’=d
5+2
7
Cociente entero
2.
En toda división entera por defecto, el dividendo
es el producto del divisor por el cociente, más el
resto.
r=D-qd
Se deduce que D= qd+r con r<d
Cociente entero
Si se multiplican dividendo y divisor por un mismo
número, el cociente permanece invariable y el resto
quedará multiplicado por ese número.
Sea h ese número. Entonces si:
D=qd+r,
r<d
se deduce Dh=qd  h+rh, rh<dh
Ej: D=7 d=2
h=3
La propiedad también se cumple cuando se divide por h.
3.
Cociente entero

En la división entera podemos definir la operación
"módulo". Dados dos números D y d naturales
llamaremos D MOD d al resto por defecto que
resulta al dividir D entre d.
División Euclídea
División Euclídea
Hasta el momento hemos considerado números positivos ahora
agregaremos negativos.
Dadas D y d con d ≠ 0. Utilizando la recta numérica es posible representar d
y todos sus múltiplos.
Dándose dos situaciones, cuando d>0 y d<0.

En ambos casos la distancia entre dos valores es |d|
División Euclídea

Si sobre la misma recta representamos D, se podrán
dar dos casos según D coincida o no con múltiplos de d.
 Entonces
cuando
D  d
será:
D=qd+r, r=0, q  Z es decir D=qd y q  Z
División Euclídea


También puede darse que no sean múltiplos en cuyo caso qd es el mayor
múltiplo de d menor que D, es decir el primer múltiplo de d a la izquierda de D.
Llamando r a la distancia entre qd y D tendremos:
D=qd+r
0<r<|d| con q Z
Esto constituye el principio de la división euclídea.
Casos que pueden darse:




para a y b positivos, cociente q1 y resto r1
para a positivo y b negativo, cociente - q1 y resto r1
para a y b negativos, cociente q1 y resto – r1
para a negativo y b positivo, cociente - q1 y resto – r1
a y b positivos, cociente q1 y resto r1
Sea D= 27
d=13
27=2  13 + 1
Será q=2 el cociente y r=1 el resto

a positivo y b negativo, cociente - q1 y resto r1
Sea D= 27
d=-13
27=(-2)  (-13) + 1
Será q=-2 el cociente y r=1 el resto

a y b negativos, cociente q1 y resto – r1
Sea D= -27
d=-13
-27=2  (-13) + (-1)
Pero r=-1 <0, lo que no es posible
Por ello se corrige:
-27=(2  (-13) – 13) + (13-1)
-27= -39 + 12
q= 3
r=12
por lo tanto -27= 3  (-13) + 12

a negativo y b positivo, cociente - q1 y resto – r1
Sea D= -27 d=13
-27=(-2)  13 + (-1)
pero q=-2 y r=-1 <0, lo que no es posible ya que no se satisface 0<=1<|13|.
Por ello se corrige restando y sumando |d|
-27=((-2)  13 – 13) + (13-1)
-27= -39 + 12
q= (-3)
r=12
por lo tanto -27= (-3)  13 + 12

Números Primos y Compuestos
Números Primos y Compuestos
Dado un entero p  N, con p>1 se dice que es un número
primo, si los únicos divisores que admite en N son 1 y p.
En caso contrario si admite otros divisores se denominan
Números Compuestos.
Ej.:
2,3,5,7,11,… son primos
4,6,8,..,21,.. no son primos.
Números primos y compuestos

Los números 2,3,5,7 y 11 son primos. Los restantes
comprendidos entre 2 y 11 son compuestos.
4=2  2
 2|4
6=2  3
 2|6 y 3|6
8=2  2  2  2|8
9=3  3
 3|9
10=2  5
 2|10 y 5|10
Números primos y compuestos


Una manera fácil de determinar si un número p>1 es primo:
consiste en dividir el número p por los números desde 2 hasta
p-1. Verificando que no admita ningún divisor.
Si p es divisible por 2 ya no hace falta comprobar el resto de
los divisores.
Números primos y compuestos
La sucesión de números primos es infinita.
Si queremos obtener todos los números primos entre 2 y un
número m un método es la Criba de Eratóstenes:
Números primos y compuestos
Si m es un entero compuesto, m tendrá un divisor primo menor
o igual a m
Ejemplos:
Para demostrar si son o no primos los números 101, 97 y 200.
Los nros. primos menores o iguales a 101 = 10,04…son 2,3,5,7.
Pero 101 no es divisible por ninguno de ellos, siendo 101 primo
Del mismo modo comprobamos que 97es primo ya que 97 =9,84…,
los números primos menores o iguales a ese valor son 2,3,5,7 y ninguno
de ellos es divisor de 97.
El nro. 200, no es primo. Dado que 200 = 14,14… y los números
primos con los que hay que probar son 2, 3, 5, 7, 11, 13. Como 2 es
divisor de 200 entonces 200 no es primo.

Algoritmo números primos
Inicio
prueba=0, m=0, parar=0, i=0: entero
Leer (m)
prueba=(m mod 2)
si (prueba <>0) entonces
i=3
fin si
// sqrt es función matemática que calcula raíz cuadrada//
parar= sqrt(m)
mientras (prueba<>0 ^ (i <=parar)) hacer
prueba= (m mod i)
si (prueba <>0) entonces
i=i+2
fin si
fin mientras
si (prueba=0) entonces
imprimir (“El número no es primo”)
sino
imprimir (“El número es primo”)
fin si
fin
Números primos y compuestos
Todo número compuesto m  N puede expresarse mediante
el producto de sus factores primos.
Por lo tanto:
m=p1 . p2 . p3… .pm
o si pi se repite varias veces ei
em
m  p1e1 . p2e2 . p3e3 ..... pm
La descomposición factorial de un número compuesto m  N
en factores primos es única.
Números primos y compuestos

Si queremos encontrar los factores primos de m se divide por los
posibles primos comenzando por los más pequeños hasta
obtener la unidad.
168 2
7007 7
84 2
1001 7
42 2
143 11
21 3
13 13
7 7
1
1
168=2 3 3 7
7007=7 2  11 13
Máximo Común Divisor
Máximo común divisor



Divisor: Se llama divisor de un número a aquel que
cabe en él una cantidad de veces exacta.
Dados varios números, sus divisores comunes no podrán
superar al menor de ellos.
El mayor de dichos divisores será el máximo común
divisor de los números dados.
Máximo común divisor



El mayor de dichos divisores será el máximo común divisor
de los números dados.
Si a= 15 y b=20, se verifica que 5|15 y 5|20. Por lo
tanto 5 es un divisor común de 15 y 20.
Con los datos se verifica que 2 no divide a 15 pero si a
20, por lo que 2 no es divisor común de 15 y 20.
Máximo común divisor
Los números 12 y 36 tienen varios divisores comunes 2|12 y 2|36;
3|12 y 3|36. Sin embargo 12|12 y 12|36, siendo este el último
y mayor de todos los divisores comunes. Por lo tanto,
mcd(12,36)=12.
El único divisor de 10 y 13 es 1, es decir, mcd(10,13)=1.
Máximo común divisor



El concepto anterior puede extenderse a más de dos números:
Los números enteros 36, 75, 251 son primos entre sí porque no
poseen divisor común excepto el 1, es decir, mcd(36,75,251)=1
Sin embargo, no son primos dos a dos ya que por ejemplo
mcd(36,75)=3
Máximo común divisor
¿Cómo obtener el mcd?
 Una manera es empleando el teorema que dice: que el máximo
común divisor de varios números es el producto de los factores
primos comunes a todos ellos, tomando cada uno con el menor
de los exponentes con los que figura.
 Por ejemplo: para encontrar el mcd(300,420,660) primero lo
descomponemos a cada uno en sus factores primos:
2
2
 300= 2 . 3 . 5
2
 420=2 . 3 . 5 . 7
mcd(300,420,660)= 22 . 3 . 5 =60
2
 660=2 . 3 . 5 . 11
Máximo común divisor
Otra manera de encontrar el mcd es mediante el algoritmo de Euclides que dice:
 Sean a y b dos números enteros no nulos, con a>b, los divisores comunes de ambos
son los comunes al menor de ellos y al resto r, por defecto o exceso de la división de
ambos.
 Los enteros a y b se suponen positivos y se definen qi y ri entonces:
a= bq1 + r1
con 0< r1 <b
b= r1q2 + r2
con 0< r2 < r1
r1= r2q3 + r3
con 0< r3 < r2
……………
……………
rn-3= rn-2qn-1 + r n-1
con 0< rn-1 < rn-2
rn-2= rn-1qn + r n
con 0< rn < rn-1
rn-1= rnqn+1 + 0
Siendo rn el último resto no nulo. Ese valor será el mcd(a,b)

Ejemplo Obtención mcd
Supongamos que deseamos calcular el mcd(250,111). En este
caso tendríamos:
250= 111 2 + 28
111 = 28  3 + 27
28 = 27  1 + 1
27 = 1  27 + 0
mcd(250,111)=1 lo que indica que los números dados son
primos relativos.
Máximo común divisor

De este algoritmo también hay una disposición
esquemática:
q1
q2
…….
qn
qn-1
rn-1
rn
.
a
b
r1
…….
.
r1
r2
r3
0
Máximo común divisor

Ahora veamos con el mismo ejemplo anterior siendo a=250
y b=111
2
3
1
27
250
111
28
27
1
28
27
1
0
mcd(250,111)=1
Máximo común divisor
Algoritmo Cálculo mcd
Inicio
a,b,r,aux: entera
Leer (a,b)
Si (a<b) entonces
aux=a
a=b
b=aux
fin si
mientras (b<>0) hacer
r = a mod b // mod= % resto división entera //
a =b
b=r
fin mientras
imprimir (“El mcd es:”, a)
fin
Máximo común divisor






Propiedades mcd
Cualquier divisor común de a y b es un divisor de mcd(a,b)
Ej.: sea a=18 y b=12 entonces mcd(18,12) = 2 . 3 = 6
Podemos decir que 2 es divisor de 6 y que 3 es divisor de 6
Considerando los números enteros Z y dado que los divisores de a también
son de –a, se cumplirá que mcd(a,b) = mcd(-a,b)
Se verifica que mcd(a,b) = mcd(a-b,b) = mcd(a+b,b)
Si mcd(a,b)=d, entonces mcd(ah, bh)=dh
Si mcd(a,b)=d y a y b son múltiplos de k, entonces mcd(a/k, b/k)=d/k
Si mcd(a,b)=d entonces mcd (a/d, b/d)=1
Mínimo común múltiplo