Teoria De Numeros

UNIVERSIDAD DEL QUINDÍO
PROGRAMA DE INGENIERÍA DE SISTEMAS Y COMPUTACIÓN
GUÍA EDUCATIVA Nº 08

CURSO: Matemáticas Discretas I
UNIDAD: III y IV – Teoría de Números y Algoritmos en la Teoría de Números
TEMAS: 3.3. Congruencia, 4.1. MCD y MCM

OBJETIVOS:
1. Comprender qué es el Mínimo Común Múltiplo, cuál es su importancia y realizar la aplicación algorítmica de su procedimiento deresolución
2. Comprender el concepto de congruencia y estudiar su aplicación en problemas matemáticos.

El Mínimo Común Múltiplo:
Si a, b y k pertenecen a Z+, y a | k, b | k, se dice que k es múltiplo común de a y b. A la k más pequeña de éstas, la cual se llamará c, se la denomina MÍNIMO COMÚN MÚLTIPLO o MCM, de a y b, y se escribe c = MCM(a,b) ó también como [a,b].
El siguiente teoremamuestra que se puede obtener el mínimo común múltiplo a partir del máximo común divisor, por lo cual no se necesita un procedimiento aparte para determinarlo.

Teorema Número 6: Si a y b son enteros positivos, entonces MCD(a,b) . MCM (a,b) = a.b.

Demostración: Sean p1, p2,…, pk todos los factores primos de a o de b, entonces se puede escribir:
a = p1a1 . p2a2 . … . pkak
y
b = p1b1 . p2b2 .… . pkbk

En donde algunos de los ai y bi pueden ser cero (0). Se desprende entonces que:

MCD(a,b) = p1min(a1,b1) . p2min(a2,b2). … . pkmin(ak,bk)
y
MCM(a,b) = p1max(a1,b1) . p2max(a2,b2) . … . pkmax(ak,bk)

Por tanto,
MCD(a,b) . MCM(a,b) = p1a1+b1 . p2a2+b2 . … . pkak+bk
= (p1a1 . p2a2 . … pkak). (p1b1 . p2b2 . … pkbk)
= a.b
Ejemplo 1: Sean a = 540 y b = 504. Factorizando a y ben primos se obtiene:

a = 540 = 22 . 33 . 5 y b = 504 = 23 . 32 . 7

En conclusión, todos los números primos que son factores de a o b son p1 = 2, p2 = 3, p3 = 5 y p4 = 7. Entonces a = 22 . 33 . 51 . 70 y b = 23 . 32 . 50 . 71. Entonces se tiene

MCD(540,504) = 2min(2,3) . 3min(3,2) . 5min(1,0) . 7min(0,1) = 22 . 32 . 50 . 70 = 4 . 9 = 36

También

MCM (540,504) = 2max(2,3) .3max(3,2) . 5max(1,0) . 7max(0,1) = 23 . 33 . 51 . 71 = 8 . 27 . 5 . 7 = 7560

Entonces:
MCD(540,504) . MCM(540,504) = 36 . 7560 = 272160 que es igual a 540 . 504 = 272160. Para verificar, también puede calcularse el MCD(540,504) por el Algoritmo Euclidiano y obtenerse el mismo resultado.

Ejemplo 2: Sean a = 168 y b = 225. Factorizando a y b en primos se obtiene:

a = 168 = 23 . 3 . 7 y b =225 = 32 . 52

En conclusión, todos los números primos que son factores de a o b son p1 = 2, p2 = 3, p3 = 5 y p4 = 7. Entonces a = 23 . 31 . 50 . 71 y b = 20 . 32 . 52 . 70. Entonces se tiene

MCD(168, 225) = 2min(3,0) . 3min(1,2) . 5min(0,2) . 7min(1,0) = 20 . 31 . 50 . 70 = 3

También

MCM (168,225) = 2max(3,0) . 3max(1,2) . 5max(0,2) . 7max(1,0) = 23 . 32 . 52 . 71 = 8 . 9 . 25. 7 = 12600

Entonces:
MCD(168,225) . MCM(168,225) = 3 . 12600 = 37800 que es igual a 168 . 225 = 37800.

Congruencia (Los enteros módulo n)
El residuo de una división entera es considerado el módulo, siendo este r = m – qn.

Ejemplo 3:
El módulo de la división de 17 entre 5 es 2 ya que 2 = 17 – 5(3)
El módulo de la división de 107 entre 10 es 7 ya que 7 = 107 – 10(10)
El módulo dela división de 53 entre 8 es 5 ya que 5 = 53 – 8(6)
En algunos lenguajes de programación como C++, Java y otros, la operación a % b obtiene el módulo o residuo de la división entera de a entre b. De este modo si se ejecuta la instrucción “c = a % b”, en la variable c quedaría almacenado el módulo de a entre b

Ejemplo 4:
Hallar el resultado de las siguientes operaciones:
5 % 3 => 5 % 3 = 2usando el algoritmo de la división 5 = 3(1) + 2 donde r = 2
18%6 => 18 % 6 = 0 usando el algoritmo de la división 18 = 6(3) + 0 donde r = 0
13%12 => 13 % 12 = 1 usando el algoritmo de la división 13 = 12(1) + 1 donde r = 1
5 % 7 => 5 % 7 = 5 usando el algoritmo de la división 5 = 7(0) + 5 donde r = 5

Ejemplo 5:
Si ahora marca el reloj las 4 en punto, ¿Qué hora será 101 horas después?...