Siguiente: Teorema chino del residuo Un nivel arriba: Nociones de divisibilidad Anterior: Nociones de divisibilidad

Algoritmo de Euclides

Este algoritmo permite calcular el máximo común divisor de dos números dados. Dados $x,y\in Z\!\!\!Z$ existen $q,r\in Z\!\!\!Z:x=qy+r,\ 0\leq r<y.$ De hecho, la división común en los enteros da el cociente q y el residuo r, es decir, $q=x\mbox{\rm div }y,\ r=x\mbox{\rm mod }y.$


El m.c.d, de x,y se calcula como sigue: Sean x₀=x, x₁=y y $\forall i\geq 2: x_i=x_{i-1}\mbox{\rm mod }x_{i-2}$. Se tiene que $\{x_i\}_i$ es una sucesión de enteros no-negativos estrictamente decreciente. Por tanto, $\exists i_0: x_{i_0}=0$. El penúltimo elemento de la sucesión x_i0-1 es precisamente el m.c.d. de x,y. En efecto, como x_i0=0 se tiene que x_i0-1|x_i0-2. Inductivamente se ve que $x_{i_0-1}\vert x_{i_0-j},j=i_0-2,\ldots,1,0.$ Ahora, si w dividiese a x y a y entonces ha de dividir a x₀ y a x₁, luego divide también a x₂ y consecutivamente ha de dividir a x_i0-1. Para expresar a x_i0-1 como una combinación lineal de x₀,x₁ escribamos

$$x_{i_0-1}=a_jx_j-b_jx_{j+1},\ j=i_0-2,\ldots,1,0.$$

Entonces, necesariamente

$$\begin{array}{lclclcl} a_{i_0-2}&=& 0 &\ \ & b_{i_0-2}&=& -1... ...eft(a_{1}+b_{1}(x_{0}\mbox{\rm div }x_{1})\right) \end{array}$$

Ejemplos. Consideremos dos ejemplos. 1. Para x=17711 e y=10946 el algoritmo de Euclides se desarrolla como se ve en la tabla 3.1.

  

Table 3.1: Algoritmo de Euclides para calcular (10946,17711)=1.

De ahí, se obtiene que $1=4181\cdot 17711 -6765\cdot 10946$. En este ejemplo los números dados son dos términos consecutivos de la sucesión de Fibonacci. Es en estos casos que se obtiene los desarrollos ``más largos'' del algoritmo de Euclides.

2. Para x=7524482450817 e y=499267608506 el algoritmo de Euclides se desarrolla como se ve en la tabla 3.2.

  

Table 3.2: Algoritmo de Euclides para calcular (7524482450817,499267608506)=1.

De ahí, se obtiene que $1=185066460993\cdot 7524482450817 -2789144166880\cdot 499267608506$.


Alternativamente, (x,y) se puede calcular factorizando a los argumentos como productos de números primos: Si $x=\prod\{p^{\mbox{\scriptsize\it exp}(x,p)}\vert p\in\mbox{\rm Primos}\}$ e $y=\prod\{p^{\mbox{\scriptsize\it exp}(y,p)}\vert p\in\mbox{\rm Primos}\}$ entonces $(x,y)=\prod\{p^{z_p}\vert p\in\mbox{\rm Primos}\}$ donde $\forall p : z_p=\mathop{\rm Min}\{\mbox{\it exp}(x,p),\mbox{\it exp}(y,p)\}.$ Pasemos ahora a considerar algunas propiedades del máximo común divisor, visto éste como una operación binaria en $Z\!\!\!Z^2$.

Proposición 3.1 (Operación mcd)   La operación $(\cdot,\cdot):Z\!\!\!Z^2 \rightarrow z$, $(x,y) \mapsto \mbox{\rm m.c.d.}(x,y)$ es

$$\begin{eqnarray*}\mbox{\it conmutativa} &:& (x,y)=(y,x) \\ \mbox{\it asociativ... ... (x,x)=x \\ \mbox{\it posee un elemento anulador} &:& (1,x)=1 \end{eqnarray*}$$

Esta operación no posee elementos neutros ni inversos.

Dos números se dicen ser primos relativos si (x,y)=1. Es decir, si x e y no poseen factores comunes no-triviales.

Proposición 3.2   La ecuación

$$ax\equiv b\mbox{\rm mod }n$$

tiene solución para todo b en $Z\!\!\!Z_n$ si y sólo si a y n son primos relativos, es decir, (a,n)=1.

Demostración: $\Rightarrow$) Sea x₁ una solución para b=1. Entonces

$$\begin{array}{rlc} & ax_0 \equiv1\mbox{\rm mod }n &\Rightar... ...\\ &ax_0 -ny = 1 &\Rightarrow \\ & (a,n) = 1 & \end{array}$$

$\Leftarrow$) Supongamos (a,n)=1. Entonces $\exists x_0, y_0:ax_0-ny_0=1$. Multiplicando por b: a(x₀b)-n(y₀b)=b. Sea x_b=x₀b. Entonces $ax_b\equiv b\mbox{\rm mod }n$.


Ejemplo. Ilustraremos aquí el efecto de la acción $x\mapsto a x$ para un n en particular y todos los posibles a. Para n=10, en la tabla 3.3 se muestran los valores de la homotecia $x\mapsto a x,\ a,x\in Z\!\!\!Z_{10}$.

  

Table: Productos ax en $Z\!\!\!Z_{10}$.

En su parte superior aparecen las ``pendientes'' a que no son primos relativos con 10. Vemos que para ellos, la homotecia no es suprayectiva y por tanto para algunos $b\in Z\!\!\!Z_{10}$ no hay solución a la ecuación $a x\equiv b\mbox{\rm mod }10$. En la parte de abajo aparecen las ``pendientes'' a que sí son primos relativos con 10, se tiene como resultado, en cada renglón, una permutación de $Z\!\!\!Z_{10}$ y por tanto la ecuación mencionada siempre tiene solución.

Proposición 3.3   Si (m,n)=1 entonces

$$\forall x:\ \ (m\vert x)\land(n\vert x)\;\Rightarrow\;mn\vert x.$$

El recíproco se cumple, naturalmente, para cualquier pareja de números.

Demostración: Sea x tal que $(m\vert x)\land(n\vert x)$. Entonces

$$\begin{array}{ccc}x=x_1m &\ \&\ & x=x_2n \end{array}.$$

Luego,

$$\begin{array}{lcl} (m,n)=1 & \Rightarrow& \exists a,b: am-... ...1mn =(ax_2-bx_1)mn \\ &\Rightarrow & mn \vert x \end{array}$$

Corolario 3.1   Si (m,n)=1 entonces

$$(x\equiv a\mbox{\rm mod }m)\land(x\equiv a\mbox{\rm mod }n)\;\Rightarrow\;(x\equiv a\mbox{\rm mod }(mn)).$$

Proposición 3.4   La siguientes dos condiciones son equivalentes

• (m,n)=1
• $\forall x:\ \ (m\vert xn)\;\Rightarrow\;m\vert x.$

Demostración: Supongamos (m,n)=1. Para algunos $a,b\in Z\!\!\!Z: am-bn=1$. Luego, para cualquier x: axm-bxn=x. Así pues, si m|xn entonces también m|x pues m divide a cada uno de los dos sumandos axm,bxn. Recíprocamente, supongamos que $\forall x:\ \ (m\vert xn)\;\Rightarrow\;m\vert x.$ Escribamos d=(m,n). Entonces $\exists e_1, e_2: m=e_1d\;\land\;n=e_2d$. Consecuentemente,

e₁n=e₁(e₂d)=e₂(e₁d)=e₂m,

o sea m|e₁n y por tanto m|e₁. Esto es posible sólo si d=1.
Siguiente: Teorema chino del residuo Un nivel arriba: Nociones de divisibilidad Anterior: Nociones de divisibilidad