1.6: El Algoritmo Euclidiana
- Page ID
- 115030
En esta sección describimos un método sistemático que determina el mayor divisor común de dos enteros. Este método se llama el algoritmo euclidiano.
[lem1] Si\(a\) y\(b\) son dos enteros y\(a=bq+r\) donde también\(q\) y\(r\) son enteros, entonces\((a,b)=(r,b)\).
Tenga en cuenta que por teorema 8, tenemos\((bq+r,b)=(b,r)\).
El lema anterior conducirá a una versión más general del mismo. Presentamos ahora el algoritmo euclidiano en su forma general. Afirma que el mayor divisor común de dos enteros es el último resto distinto de cero de la división sucesiva.
Dejar\(a=r_0\) y\(b=r_1\) ser dos enteros positivos donde\(a\geq b\). Si aplicamos el algoritmo de división sucesivamente para obtener eso\[r_j=r_{j+1}q_{j+1}+r_{j+2} \ \ \mbox{where} \ \ 0\leq r_{j+2}<r_{j+1}\] para todos\(j=0,1,...,n-2\) y\[r_{n+1}=0.\] Entonces\((a,b)=r_{n}\).
Al aplicar el algoritmo de división, vemos que\[\begin{aligned} r_0&=&r_1q_1+r_2 \ \ \ \ \ 0\leq r_2<r_1, \\ r_1&=&r_2q_2+r_3 \ \ \ \ \ 0\leq r_3<r_2, \\ &.& \\ &.& \\ &.& \\ r_{n-2}&=&r_{n-1}q_{n-1}+r_{n} \ \ \ \ \ 0\leq r_{n}<r_{n-1}, \\ r_{n-1}&=&r_{n}q_{n}.\end{aligned}\] Note que, tendremos un resto de\(0\) eventualmente ya que todos los restos son enteros y cada resto en el siguiente paso es menor que el resto en el anterior. Por Lemma [lem1], vemos que\[(a,b)=(b,r_2)=(r_2,r_3)=...=(r_n,0)=r_n.\]
Encontraremos el mayor divisor común de\(4147\) y\(10672\):
Tenga en cuenta que\[\begin{aligned} 10672&=&4147\cdot 2+2378,\\ 4147&=&2378\cdot 1+1769,\\ 2378&=&1769\cdot 1+609,\\ 1769&=&609\cdot 2 +551,\\ 609&=& 551\cdot 1+58, \\ 551&=&58\cdot 9+ 29,\\ 58&=&29\cdot 2,\\\end{aligned}\] De ahí\((4147,10672)=29.\)
Ahora usamos los pasos del algoritmo euclidiano para escribir el mayor divisor común de dos enteros como una combinación lineal de los dos enteros. El siguiente ejemplo determinará realmente las variables\(m\) y\(n\) se describen en Teorema [thm9]. El siguiente algoritmo puede ser descrito por una forma general pero en aras de la simplicidad de las expresiones presentaremos un ejemplo que muestra los pasos para obtener el mayor divisor común de dos enteros como una combinación lineal de los dos enteros.
Express 29 como una combinación lineal de\(4147\) y\(10672\):
\[\begin{aligned} 29&=&551-9\cdot 58,\\ &=& 551-9(609-551\cdot 1),\\ &=& 10.551-9.609,\\ &=& 10\cdot (1769-609\cdot 2)-9\cdot 609,\\ &=& 10\cdot 1769-29\cdot 609,\\ &=& 10\cdot 1769-29(2378-1769\cdot 1),\\ &=& 39\cdot 1769-29\cdot 2378,\\ &=& 39(4147-2378\cdot 1)-29\cdot 2378,\\ &=& 39\cdot 4147-68\cdot 2378,\\ &=& 39\cdot 4147-68(10672-4147\cdot 2),\\ &=& 175\cdot 4147-68\cdot 10672,\end{aligned}\]
En consecuencia, eso lo vemos\(29=175\cdot 4147-68\cdot 10672\).
Ejercicios
- Utilice el algoritmo euclidiano para encontrar el mayor divisor común de 412 y 32 y expresarlo en términos de los dos enteros.
- Utilice el algoritmo euclidiano para encontrar el mayor divisor común de 780 y 150 y expresarlo en términos de los dos enteros.
- Encuentra el mayor divisor común de\(70,98, 108\).
- Dejar\(a\) y\(b\) ser dos enteros pares positivos. Demostrar que\((a,b)=2(a/2,b/2).\)
- Mostrar que si\(a\) y\(b\) son enteros positivos donde\(a\) es par y\(b\) es impar, entonces\((a,b)=(a/2,b).\)