MAD: Algoritmo de la división y máximo común divisor

Comenzamos explicando El algoritmo de la división, que intenta dar consistencia al procedimiento habitual de división entre números enteros, recordando que esta no existe como tal, ya que la división no siempre existe. Sin embargo podemos dar un resultado que nos ayuda a comprender que entendemos por división en los números enteros.

Teorema: Dados dos números enteros $a$ y $b$, con $a$ no nulo, la división euclídea asocia un cociente $q\in\mathbb{Z}$ y un resto $r\in\mathbb{Z}$, únicos, que verifican: $$b=q\,a+r,\quad 0\leq r<|a|$$

Colorario:[Propiedad arquimediana] Dados dos números enteros $a$ y $b$, con $b>a>0$, entonces existe un $q\in\mathbb{Z}$ talque $$a(q-1)< b < aq$$

Veamos una algoritmo para obtener el cociente y el resto de la división entera: Sean $a,b\in\mathbb{Z}$, con $b>a>0$ y sea $q_0\in\mathbb{Z}$ talque $r_0=b-aq_0>a$, calculamos

$b$ $a$
$r_0=b-aq_0$ $q_0$
$r_1=r_0-aq_1$ $q_1$
$r_2=r_1-aq_2$ $q_2$
$\vdots$ $\vdots$
$r_n=r_{n-1}-aq_n$ $q_n$

mientras $r_n>a$. Entonces, $b=a\left(\sum_{i=0}^nq_i\right)+r_n$.

Si quisiéramos realizar un programa que lo calcule sobraría con asignar $q_i=1\forall i$ y obtendríamos lo que buscamos:
$$\begin{array}{l}
i=1;\\
r[i]=b-a; \\
while(r[i]>a) \\
\qquad r[i++]=r[i]-a; \\
endwhile \\
print(‘Cociente =\%d’,i-\,-))\\
print(‘resto =\%d’,r[i-\,-]))\\
\end{array}
$$

máximo común divisor

Consideremos dos números enteros Si $a$ y $b$ distintos de cero, decimos que $c$ es un divisor común de $a$ y $b$ si $c|a$ y $c|b$. Cuando existen, únicamente, como divisores comunes 1 y -1 de los números $a$ y $b$ , estos se llaman coprimos o números primos entre sí.

Un número entero $d$ se llama máximo común divisor de los números $a$ y $b$, $d=mcd(a,b)$, cuando:

  1. d es divisor común de los números $a$ y $b$ y
  2. $c$ es divisor de $a$ y $b$, entonces $c|d$.

Teorema:[Bezout] Si $d=mcd(a,b)$, entonces
$$\exists x,y\in\mathbb{Z};\, ax+by=d.$$

En la próxima sesión veremos el algoritmo de Euclides como método para calcular el mcd().

 

Ejercicio: ¿Qué afirmación es cierta? Para todo $a,b,c\in\mathbb{Z}$
    1. a) Si $a|c$ y $b|c$, entonces $(ab)|c$
    1. b) Si $a|b$ y $a|c$, entonces $a|(bc)$
    1. c) Si $a|b$ y $b|c$, entonces $(ab)|c$
    1. d) Ninguna de las anteriores.
This entry was written by admin , posted on lunes febrero 03 2020at 08:02 am , filed under Matemática Discreta . Bookmark the permalink . Post a comment below or leave a trackback: Trackback URL.

Comments are closed.