Un medio rápido para determinar si dos números enteros son primos entre sí es el algoritmo de Euclides.

Question

Estoy confundido acerca de cómo hacer el algoritmo extendido. Por ejemplo, aquí está el mcd parte gcd(8000,7001)

$$\begin{align}8000 &= 7001\cdot1 + 999\\ 7001&=999\cdot 7+8\\ 999&=8\cdot 124+7\\ 8&=7\cdot 1+1\\ 7&=1\cdot 7+0\\ \gcd(8000,7001)&=1\end{align}$$

Ahora, el algoritmo extendido

$$\begin{align}1 &= 8 - 1\cdot7\\ &= 8 - 1\cdot(999 - 8\cdot124)\\ &= -1\cdot999 + 8\cdot125\end{align}$$

¿Cómo se obtiene este 8*125 de la línea anterior?

Answer 1

$\begin{eqnarray}\!\text{By the distributive law}\ \ && \,8\, -\, 1\cdot(999-8\cdot 124)\\ &=&\ 8\cdot\color{#c00}1\, -\, 999\, +\, 8\cdot\color{#c00}{124}\\ &=&\ 8\cdot\color{#0a0}{ 125} - 999\ \ \,{\rm by}\ \ \color{#c00}{124 + 1} = \color{#0a0}{125}\end{eqnarray}$

Este "back-método de sustitución" de la extensión de la mcd es muy propenso a errores. Más simple de calcular y más fácil de recordar es el método que se describe aquí. Eso de ejecutar el algoritmo de rendimientos

$$\begin{array}{rrr} 8000 & 1 & 0\\ 7001 & 0 & 1\\ 999 & 1 & -1\\ 8 & -7& 8\\ -1 & \!\!\color{#c00}{876} & \!\!\!\color{#0a0}{-1001}\end{array}$$

donde cada línea de $\,\ a\ \ b\ \ c\ \,$ significa que $\ a = 8000\, b + 7001\, c.\ $ por lo Tanto

$$ 1 = -\color{#c00}{876}\cdot 8000 + \color{#0a0}{1001}\cdot 7001$$

El post vinculado describe el algoritmo en gran detalle, de una manera que es fácil de recordar.

Aquí hay otro ejemplo de computación $\rm\ gcd(141,19),\,$ con las ecuaciones escritas explícitamente

$$\rm\begin{eqnarray}(1)\quad \color{#C00}{141}\!\ &=&\,\ \ \ 1&\cdot& 141\, +\ 0&\cdot& 19 \\ (2)\quad\ \color{#C00}{19}\ &=&\,\ \ \ 0&\cdot& 141\, +\ 1&\cdot& 19 \\ \color{#940}{(1)-7\,(2)}\, \rightarrow\, (3)\quad\ \ \ \color{#C00}{ 8}\ &=&\,\ \ \ 1&\cdot& 141\, -\ 7&\cdot& 19 \\ \color{#940}{(2)-2\,(3)}\,\rightarrow\,(4)\quad\ \ \ \color{#C00}{3}\ &=&\, {-}2&\cdot& 141\, + 15&\cdot& 19 \\ \color{#940}{(3)-3\,(4)}\,\rightarrow\,(5)\quad \color{#C00}{{-}1}\ &=&\,\ \ \ 7&\cdot& 141\, -\color{#0A0}{ 52}&\cdot& \color{#0A0}{19} \end{eqnarray}\qquad$$

Answer 2

$$ \begin{align} 8000&=7001\cdot1+999\\ 7001&=999\cdot7+8\\ 999&=8\cdot124+7\\ 8&=7\cdot1+1\\[12pt] 1 &=8-7\cdot1\\ &=8-1(999-8\cdot124)\\ &=8\cdot125-1\cdot999\\ &=125(7001-7\cdot999)-1(8000-7001\cdot1)\\ &=126\cdot7001-1\cdot8000-875\cdot999\\ &=126\cdot7001-1\cdot8000-875\cdot(8000-7001)\\ &=1001\cdot7001-876\cdot8000 \end{align} $$ Como Bill Dubuque menciona, el método de sustitución es difícil de seguir, y por lo tanto, propensos a errores. También hay Euclides-Wallis versión del Algoritmo de Euclides Extendido: $$ \begin{array}{r} &&1&7&124&1&7\\\hline \color{#C00000}{1}&0&1&-7&869&\color{#C00000}{-876}&7001\\ 0&\color{#00A000}{1}&-1&8&-993&\color{#00A000}{1001}&-8000\\ \color{#C00000}{8000}&\color{#00A000}{7001}&999&8&7&\color{#0000FF}{1}&0\\ \end{array} $$ Que da $1001\cdot7001-876\cdot8000=1$