Necesito ayuda con esta ecuación: $$100x - 23y = -19.$$ When I plug this into Wolfram|Alpha, one of the integer solutions is $x = 23n + 12$ where $$ n es un subconjunto de todos los enteros, pero me parece que no puede averiguar cómo llegaron a la respuesta.
Respuestas
¿Demasiados anuncios?
Anthony Shaw
Puntos
858
El uso de la de Euclides-Wallis (algoritmo se describe a continuación) $$ \begin{array}{r} &&4&2&1&7\\\hline 1&0&1&-2&3&-23\\ 0&1&-4&9&-13&100\\ 100&23&8&7&1&0\\ &&&&{\uparrow}&{\star} \end{array} $$ lookng debajo de la horizotal línea, en la fila superior los tiempos de $100$, más de la mitad de la fila veces $23$ es igual a la fila inferior. Por lo tanto, la flecha de la columna que dice $$ 3\cdot100-13\cdot23=1 $$ Además, la parte superior y media de los números en cada columna son relativamente primos. Por lo tanto, la estrella de la columna da la combinación más pequeña de $100$ $23$ que es igual a $0$. Agregar arbitraria múltiplos de la estrella de la columna a un determinado múltiplo de la flecha de la columna para obtener todas las soluciones para un determinado problema. Ya que queremos un resultado de $-19$, agregar arbitraria múltiplos de la estrella de la columna de a $-19$ veces la flecha de la columna: $$ \begin{align} -19&=(-19\cdot3-23k)100+(-19\cdot-13+100k)23\\ &=(-57-23k)100+(247+100k)23 \end{align} $$ Esto le da a todos el entero de las soluciones. Por lo tanto, $x=-57-23k=12-23(k+3)=12+23n$ donde $n=-k-3$.
Euclides-Wallis Algoritmo
Este algoritmo calcula $\gcd(m,n)$, resuelve la ecuación de Diophantine $mx + ny = \gcd(m,n)$, y los rendimientos de la continuación de la fracción de $m/n$.
Empezar con las dos columnas $$ \begin{array}{r} 1&0\\ 0&1\\ m&n\\ \end{array}\etiqueta{1} $$ Por encima de cada una de las sucesivas columna anote el piso del cociente de la base de la columna anterior dividido en la base de la columna antes de que, a continuación, calcular la columna siguiente al restar ese número de veces la columna anterior de la columna antes de que.
Trabajemos un ejemplo; $m = 17, n = 23$: $$ \newcommand{\nextq}[2]{\leftarrow\lfloor\color{##00A000}{#1}/\color{##0000FF}{#2}\rfloor} \newcommand{\euclid}[3]{{\leftarrow}\color{##00A000}{#1}-\color{orange}{#3}\cdot\color{##0000FF}{#2}} \begin{array}{rcl} \begin{array}{l} \color{#C00000}{\text{Above each successive column}}\\ \text{write down the floor of the}\\ \text{quotient of }\color{#0000FF}{\text{the base of the}}\\ \color{#0000FF}{\text{previous column}}\text{ divided into }\color{#00A000}{\text{the}}\\ \color{#00A000}{\text{base of the column before that}} \end{array} && \begin{array}{l} \text{Compute }\color{#C00000}{\text{the next column}}\text{ by}\\ \text{subtracting }\color{orange}{\text{that number}}\text{ times}\\ \color{#0000FF}{\text{the previous column}}\text{ from }\color{#00A000}{\text{the}}\\ \color{#00A000}{\text{column before that}}\\ \text{} \end{de la matriz}\\ \begin{array}{rrrl} & & \color{#C00000}{0} & \nextq{17}{23}\\ \hline 1 & 0 \\ 0 & 1 \\ \color{#00A000}{17} & \color{#0000FF}{23} \end{array} &\rightarrow& \begin{array}{rrrl} & & \color{orange}{0}\\ \hline \color{#00A000}{1} & \color{#0000FF}{0} & \color{#C00000}{1} & \euclid{1}{0}{0} \\ \color{#00A000}{0} & \color{#0000FF}{1} & \color{#C00000}{0} & \euclid{0}{1}{0} \\ \color{#00A000}{17} & \color{#0000FF}{23} & \color{#C00000}{17} & \euclid{17}{23}{0} \end{de la matriz}\\ &\swarrow&\\ \begin{array}{rrrrl} & & 0 & \color{#C00000}{1} & \nextq{23}{17} \\ \hline 1 & 0 & 1 \\ 0 & 1 & 0 \\ 17 & \color{#00A000}{23} & \color{#0000FF}{17} \end{array} &\rightarrow& \begin{array}{rrrrl} & & 0 & \color{orange}{1} \\ \hline 1 & \color{#00A000}{0} & \color{#0000FF}{1} & \color{#C00000}{-1} & \euclid{0}{1}{1} \\ 0 & \color{#00A000}{1} & \color{#0000FF}{0} & \color{#C00000}{1} & \euclid{1}{0}{1} \\ 17 & \color{#00A000}{23} & \color{#0000FF}{17} & \color{#C00000}{6} & \euclid{23}{17}{1} \end{de la matriz}\\ &\swarrow&\\ \begin{array}{rrrrrl} & & 0 & 1 & \color{#C00000}{2} &\nextq{17}{6} \\ \hline 1 & 0 & 1 & -1 \\ 0 & 1 & 0 & 1 \\ 17 & 23 & \color{#00A000}{17} & \color{#0000FF}{6} \end{array} &\rightarrow& \begin{array}{rrrrrl} & & 0 & 1 & \color{orange}{2} \\ \hline 1 & 0 & \color{#00A000}{1} & \color{#0000FF}{-1} & \color{#C00000}{3} & \euclid{1}{-1}{2} \\ 0 & 1 & \color{#00A000}{0} & \color{#0000FF}{1} & \color{#C00000}{-2} & \euclid{0}{1}{2} \\ 17 & 23 & \color{#00A000}{17} & \color{#0000FF}{6} & \color{#C00000}{5} & \euclid{17}{6}{2} \end{array} \end{array}\\ \vdots $$ $$ \begin{array}{rrrrrrr} &&\color{orange}{0}&\color{orange}{1}&\color{orange}{2}&\color{orange}{1}&\color{orange}{5}\\ \hline \color{#00A000}{1}&\color{#00A000}{0}& 1&-1& 3&\color{#C00000}{-4}&\color{#0000FF}{23}\\ \color{#00A000}{0}& \color{#00A000}{1}& 0&1&-2&\color{#C00000}{3}&\color{#0000FF}{-17}\\ \color{#00A000}{17}&\color{#00A000}{23}&17& 6& 5& \color{#C00000}{1}&\color{#0000FF}{0} \end{array}\etiqueta{2} $$ El rojo de la columna (anterior a la de azul con $0$ en su base) ha $\gcd(m,n)$ en su base. También, $m$ veces la fila superior plus $n$ veces la fila del medio es igual a la fila inferior. Así, el rojo de la columna (con $\gcd(m,n)$ en su base) tiene los coeficientes de la $mx + ny = \gcd(m,n)$ en las dos filas superiores.
También, el azul de la columna (con $0$ en su base) tiene el más pequeño distinto de cero solución a $mx + ny = 0$. Múltiplos de esta solución puede ser agregado a una solución particular de $mx + ny = k$ para obtener todas las soluciones.
La naranja cocientes por encima de las columnas de rendimiento de la continuación de la fracción de $m/n$.
Por lo tanto, $$\gcd(\color{#00A000}{17},\color{#00A000}{23}) = \color{#C00000}{1}\\ (\color{#C00000}{-4}\color{#0000FF}{+23}k)\color{#00A000}{17} + (\color{#C00000}{3}\color{#0000FF}{-17}k)\color{#00A000}{23} = \color{#C00000}{1}$$ y la continuación de la fracción de $\color{#00A000}{17}/\color{#00A000}{23}$$[\color{orange}{0},\color{orange}{1},\color{orange}{2},\color{orange}{1},\color{orange}{5}]$.
Algoritmo de euclides (plus contabilidad)
El algoritmo anterior es simplemente el algoritmo de Euclides en las filas superior e inferior, con algunos de la contabilidad en las dos filas del medio. Los coeficientes están en la fila superior y el resto (que, según lo dictado por el Algoritmo de Euclides, que más tarde se convertiría divisores y, a continuación, dividendos) están en la fila inferior.
En $(2)$, el primer dividendo se $17$ y el primer divisor es $23$. El primer cociente es $0$ y el resto es $17$. En el paso siguiente, el dividendo es $23$ (que fue el anterior divisor) y el divisor es $17$ (que fue el anterior resto). El segundo cociente es $1$ y el resto es $6$. En el tercer paso el dividendo es $17$ y el divisor es $6$, lo que produce un cociente de $2$ y un resto de $5$. Esto continúa hasta que un resto de $0$ aparece. El algoritmo tiene que parar aquí desde el siguiente divisor sería $0$.
La teneduría de libros en el medio de las dos filas imita el cálculo realizado en la fila inferior. Es decir, por debajo de la línea, la tercera columna es la primera columna menos el $0$ los tiempos de la segunda columna. La cuarta columna es la segunda columna menos el $1$ los tiempos de la tercera columna. La quinta columna es la tercera columna de menos de dos veces a la cuarta columna. Esta contabilidad se asegura de que la primera fila debajo de la línea de tiempos $17$ además de la segunda fila veces $23$ es igual a la fila inferior. Esto nos permite de nuevo el algoritmo de Euclides, al mismo tiempo, estamos llevando a cabo.
$100x -23y = -19$ si y sólo si $23y = 100x+19$, si y sólo si $100x+19$ es divisible por $23$. Usando aritmética modular, usted tiene $$\begin{align*} 100x + 19\equiv 0\pmod{23}&\Longleftrightarrow 100x\equiv -19\pmod{23}\\ &\Longleftrightarrow 8x \equiv 4\pmod{23}\\ &\Longleftrightarrow 2x\equiv 1\pmod{23}\\ &\Longleftrightarrow x\equiv 12\pmod{23}. \end{align*}$$ por lo $x=12+23n$ para algunos entero $n$.
David HAust
Puntos
2696
Shabaz
Puntos
403
Si se toma la ecuación de mod $23$, encontrará $8x \equiv 4 \pmod{23}$ y por la inspección, esto es satisfecho por $x \equiv 12 \pmod{23}$. Para encontrar esto, puede usar el algoritmo de Euclides Extendido
Steven Gregory
Puntos
3326
Me parece que esta versión de la de Euclides-Wallis Algoritmn un poco más amigable para el usuario. robjohn hizo un gran trabajo de explicar cómo funciona por lo tanto, ofrezco este con ninguna otra explicación. Por favor, tenga en cuenta que puse el multiplicador junto a la fila que se multiplica por. También tenga en cuenta que yo se multiplican y, a continuación, añadir, así que mi multiplicadores tienen un signo diferente al de su. Es realmente la misma cosa, acabo de pensar de esta manera es un poco más transparente. También he omitido el $``0"$ fila. No creo que el esfuerzo vale la pena utilizado para calcularlo.
|100 1 0
-4 | 23 0 1
-3 | 8 1 -4
| -1 -3 13
| 1 3 -13
y llegamos a la conclusión de que 3(100)-13(23) = 1
