Download Descargar

LOGICA Y MATEMATICA
COMPUTACIONAL
Profesora Responsable:
Esp. Prof. Liliana Caputo
DIVISIBILIDAD
CONGRUENCIA MODULO n
ARITMETICA MODULAR
DEFINICION
Llamamos conjunto de números enteros, Z, a la unión del
conjunto de enteros no negativos (No) y el conjunto de
los opuestos de los números naturales. Es decir:
Si N- = {-n / n  N}, entonces: Z = No  NRecordemos las propiedades que cumplen la suma y la
multiplicación de números enteros:
1. Ley de cierre: a, bZ: a + b  Z  a.b  Z.
2. Propiedad asociativa:
a,b,cZ: (a+b)+c = a+(b+c)  (a.b).c = a.(b.c)
PROPIEDADES
3. Propiedad conmutativa:
a, b Z: a + b = b+ a  a.b = b.a
4. Existencia de elemento neutro:
a Z: a + 0 = a  a.1 = a
5. Existencia de opuesto para cada elemento:
a Z, - a Z / -a + a = 0
6. Propiedad distributiva del producto con respecto a la
suma: a,b,cZ: (a + b).c = a.c +b.c
ESTRUCTURA DE (Z, +, .)
Por cumplirse estas propiedades:
(Z, +) es grupo conmutativo o abeliano
(Z, +, .) es anillo conmutativo con
unidad.
Como, además, se cumple que:
a.b = 0  a = 0  b = 0
(Z, +, .) es dominio de integridad
DESARROLLO DECIMAL DE UN
NUMERO ENTERO
Todo número entero puede expresarse
como la suma de sus cifras por
potencias de 10:
an-1….a1ao= ao 10o+ a1.10 +…+an-110n-1
Ejemplos:
1342 = 2.10o + 4.101 + 3.102 + 1.103
- 1342 = -2.10o - 4.101 - 3.102 - 1.103
ALGORITMO DE DIVISION
ENUNCIADO:
Si a, b  Z y b  0, existen y son únicos q, r
 Z / a = b.q + r, donde 0  r < b.
q es el “cociente” y r es el “resto” de dividir
a por b. En cambio, a es el “dividendo” y b
es el “divisor”.
Ejemplos: 294 = 6.49 + 33 142 = -11(-12)+10
-213 = 71(-3) + 0 -152 = -40.4 + 8
DIVISIBILIDAD
Si a, b  Z y b  0, y el resto de dividir a
por b es cero, se dice que a es múltiplo
de b, que b es divisor de a o que b divide
a “a”.
En símbolos:
ab   qZ / a = q.b
PROPIEDADES
1.
2.
3.
4.
5.
6.
7.
aZ – {0}: aa  a-a
aZ : 1a  -1a
aZ : a0
a, b  Z  b  0  ba cZ: ba.c
a, b  Z - {0}, cZ / ba  ac bc
b  Z - {0}, cZ / ba  bc ba+c
aZ – {0}, nN: aan
NUMEROS PARES E IMPARES
x  Z es par   kZ / x = 2.k es decir,
si 2x
x  Z es impar  x  Z no es par 
 hZ / x = 2.h + r, con 0 < r < 2 es
decir, con r = 1 con lo cual se tiene que
si x es impar, x = 2.h + 1, para algún
hZ.
NUMEROS PRIMOS
Sea p Z. Decimos que p es primo si, y sólo
sí, p tiene exactamente 4 divisores:
1, -1, p y -p
Los números enteros que no son primos, se
llaman compuestos.
Ejemplos: Son primos 2, 3, 5, 7, 11,…
Son compuestos 0, 1, 4, 6, 8, 9, 10, 12,…
TEOREMA FUNDAMENTAL DE
LA ARITMETICA
ENUNCIADO: Todo número natural, mayor
que 1, se puede descomponer como el
producto de un número finito de factores
primos. Esta factorización es única, salvo por
el orden de los factores.
Ejemplos: 385 = 5.7.11
2520 = 23.32.5.7
CRITERIOS DE DIVISIBILIDAD
Un número de dos o más cifras es
múltiplo de 2 si la cifra de las unidades
es 0, 2, 4, 6 u 8.
2. Un número de dos o más cifras es
múltiplo de 3 si la suma de sus cifras es
un múltiplo de 3.
3. Un número de dos o más cifras es
múltiplo de 5 si la cifra de las unidades
es 0 ó 5.
1.
CRITERIOS DE DIVISIBILIDAD
Un número de dos o más cifras es
múltiplo de 7 si la diferencia entre el
número resultante de eliminar la cifra de
las unidades y el doble de ésta es un
múltiplo de 7.
5. Un número de dos o más cifras es
múltiplo de 11 si la diferencia entre las
sumas de las cifras que ocupan lugares
pares e impares es un múltiplo de 11.
4.
EJEMPLOS
¿254 y 553 son múltiplos de 7?
Vemos que 25 – 4.2 = 17 que no es
múltiplo de 7. 7 no es divisor de 254.
En cambio, 55 – 6 = 49, que sí es
múltiplo de 7. Luego 553 es múltiplo de
7.
EJEMPLOS
¿2532 y 1287 son múltiplos de 11?
2 5 3 2
4 3 2 1
(2 + 5) – (3 + 2) = 2, no es múltiplo de 11.
1 2 8 7
4 3 2 1
(7 + 2) – (8 + 1) = 0, que sí es múltiplo de 11.
MAXIMO COMUN DIVISOR
Sean a y b números enteros.
d  N es el máximo común divisor (mcd) de
a y b, si, y sólo sí, se cumple:
1. da  db
2. pa  pb  pd
Ejemplo: Los divisores naturales comunes
de 12 y 18 son: 1, 2, 3 y 6.
Luego: mcd(12,18) = 6
ALGORITMO DE EUCLIDES
Se usa para calcular el mcd de dos números. Si r0
y r1 Z / r1  0. Entonces:
r0 = q1r1 + r2, con 0 < r2 < r1
r1 = q2r2 + r3, con 0 < r3 < r2
r2 = q3r3 + r4, con 0 < r4 < r3
……………………………………………………………….
rn-2 = qn-1rn-1 + rn, con 0 < rn < rn-1
rn-1 = qnrn
con rn+1 = 0
rn-1es el último resto no nulo, luego:mcd(ro,r1) = rn-1
EJEMPLO
ro = 448 y r1 = 721. Entonces:
721 = 1.448 + 273
98 = 1.77 + 21
448 = 1.273 + 175
77 = 3.21 + 14
273 = 1.175 + 98
21 = 1.14 + 7
175 = 1.98 + 77
14 = 2.7
Como el último resto no nulo es 7, resulta
que mcd(448,721) = 7.
ENTEROS COPRIMOS
Dados dos enteros no nulos a y b, diremos
que a y b son coprimos ó primos entre sí, si su
máximo común divisor es 1.
Ejemplos: 2 y 3, al ser primos tienen a 1 y -1
como únicos divisores comunes. Luego, debe ser
mcd(2,3) = 1.
9 y 14 no son primos, pero sus únicos divisores
comunes son 1 y -1. Luego, mcd(9,14) = 1.
MINIMO COMUN MULTIPLO
Sean a y b números enteros.
m  N es el mínimo común múltiplo (mcm)
de a y b, si, y sólo sí, se cumple:
1. am  bm
2. an  bn  mn
Ejemplo: 4.5 = 20. Cualquier otro múltiplo
natural común de 4 y 5 (40, 60, 80…) será
divisible por 20. Luego: mcm(4,5) = 20.
CONGRUENCIA MODULO n
Sea n  N. Definimos en Z2 la relación
“congruencia módulo n”, como sigue:
a,bZ: a  b (mód n)  n a – b
Ejemplos:
73  88 (mód 3) porque 73 – 88 = -15  3-15
120-45 (mód5) pues 120 –(-45) = 165  5165
PROPIEDADES
Sean n N, a, b, c, d Z
1. a  a (mód n)
2. a  b (mód n) b  a (mód n)
3. a  b (mód n)  b  c (mód n)  a  c (mód n)
4. a  b (módn)d  c (módn) a +d b+c (módn)
5. a  b (mód n) p  Z: p.a  p.b (mód n)
CLASES MODULO n
Consideremos la siguiente relación en Z:
(a,b)  R  r(a,n) = r(b,n)
Por algoritmo de división, existen h, k  Z/
a = k.n + r(a,n) y b = h.n + r(b,n) .
Luego a – b = k.n + r(a,n) - h.n - r(b,n) =
= (k – h).n + [r(a,n) - r(b,n)] = (k – h).n pues si
(a,b)  R, r(a,n) = r(b,n). Luego: a  b(módn)
CLASES MODULO n
Recíprocamente, si a, b Z son tales que
a  b (módn), k  Z/ a – b = k.n. Luego;
a = kn + b. Por algoritmo de división, h  Z/
b = h.n + r(b,n), con 0  r(b,n) < n.
Luego a = k.n + h.n + r(b,n) = (k – h).n + r(b,n)
Por unicidad del cociente y el resto en la
división entera, debe ser r(a,n) = r(b,n).
ECUACIONES DE
CONGRUENCIAS
Dados n natural, a y b enteros, queremos
determinar si es posible hallar x  Z / ax  b
(mód n)
Es decir, que buscamos x  Z / ax – b = k.n, para
algún número entero k. De esta manera,
planteamos la ecuación diofántica ax – k.n = b.
Una ecuación diofántica es una ecuación lineal
de dos variables (x y k, en este caso), cuya
solución debe ser un par de números enteros.
ECUACIONES DIOFANTICAS
Dada la ecuación diofántica ax + by = c, con a, b
y c enteros, siendo d = mcd(a,b), entonces:
Si dc, no existe solución.
Si dc existen infinitas soluciones.
Sea (xo,yo) una solución particular, entonces, si k
 Z, las infinitas soluciones se obtienen
haciendo: x = xo + (b/d).k  y = yo + (a/d).k
EJEMPLOS
 9x 11 (mód 6). Entonces: 9x – 11 = 6y, con yZ.
Luego: 9x – 6y = 11; mcd(9,-3) = 3  311.
 La ecuación no tiene solución
 1218x (mód30). Luego: 12 -18x = 30y, con yZ.
De donde, 18x + 30y = 12; mcd(18,30) = 6  612.
Una solución particular es x = -1, y = 1. Luego:
x = -1 + n.30/6 = -1 + 5n  y = 1 + n.18/6 = 1 + 3n,
con n  Z