Necesita ayuda para entender el algoritmo de Euclides para encontrar el Divisor común más grande

Question

Yo no soy la comprensión de cómo los siguientes formularios obras

http://en.wikipedia.org/wiki/Greatest_common_divisor#Using_Euclid.27s_algorithm

En realidad lo que hice (para mi la programación de la tarea fue bucle a través de los max de 2 números hasta que yo llegue a 1 que divide a ambos números dados sin un resto). Fuerza bruta, por lo que no es ideal. Así que quiero entender más acerca de esta formularios en lugar de utilizar.

public static int gcd(int a, int b) {
  /**
   * Get max of both numbers
   * Loop down max number and test if its divisible by both numbers
   * if yes, thats the answer, else continue
   * if no answer, return 0
   */
  int max = Math.max(a, b);
  for (int i = max; i > 0; i--) {
    if (a % i == 0 && b % i ==0) {
      return i;
    }
  }
  return 0;
}

Answer 1

La idea básica es esta: si usted quiere mcd($a$, $b$) y $a>b$, por el contrario, podemos calcular mcd($b, a \bmod b$) y hemos hecho progresos. Es progreso, porque al $a>b$, sabemos $a \bmod b$ es menor que $b$, es un resto después de todo. Y si hemos de hacer aportaciones positivas pequeños, y, finalmente, debemos terminar.

La verdadera pregunta es: ¿por qué es mcd($a$, $b$) el mismo que gcd($b, a \bmod b$)?

Bien, vamos a responder a una pregunta más fácil. En lugar de tratar de envolver su cabeza en torno a $a \bmod b$, vamos a repetir el problema. ¿Por qué es mcd($a$, $b$) el mismo que gcd($b, a-b$)? Esta pregunta es casi el mismo, pero estamos utilizando menos en lugar de mod porque es más fácil de entender cuando este material es nuevo para usted. Y el mod es sólo una aplicación repetida de menos de todos modos, ¿verdad?

Así que vamos a probar el "más fácil" de la versión. Bueno, si algún divisor $d$ entra uniformemente en $a$$b$,, entonces debe ir a su diferencia $a-b$, ¿verdad? Para ser más matemático, si $a = kd$$b=jd$, $a-b = kd-jd = (k-j)d$ y claramente $d$ entra uniformemente en $(k-j)d$. También, si $d$ entra uniformemente en $(a-b)$ cualquier $d$ dividiendo $a$ debe dividir $b$, así que hemos terminado.

Si esto todavía no está claro, dibuja una recta numérica y convencerse de que dos múltiplos de 3 (por ejemplo) son siempre un múltiplo de 3 aparte. Luego de convencerse de que cualquier múltiplo de 3 más un múltiplo de 3 también debe ser un múltiplo de 3.

A continuación, tratar de para otros números de 3.

Answer 2

$a{\rm\ mod\ }b$ es el resto cuando se divide $a$$b$, por lo que podemos decir dos cosas acerca de ella: es $a-bq$ para algunos entero $q$, y es entre el $0$$b-1$, inclusive.

Quiero mostrar a $\gcd(a,b)=\gcd(b,a{\rm\ mod\ }b)$.

Deje $d=\gcd(a,b)$. A continuación, $d$ divide tanto a a$a$$b$. Así que divide tanto a a$a-bq$$b$. Por lo que se divide $\gcd(b,a{\rm\ mod\ }b)$.

Por el contrario, vamos a $e=\gcd(b,a{\rm\ mod\ }b)$. A continuación, $e$ divide tanto a a$b$$a-bq$. Así que divide tanto a a$a$$b$. por lo que se divide $\gcd(a,b)$, y hemos terminado.

Ahora la única pregunta que queda sobre la fórmula es la razón por la que siempre da una respuesta, que es, ¿por qué no puede seguir para siempre. Bien, suponiendo $a\gt b$, y la comparación de $\gcd(a,b)$$\gcd(b,a{\rm\ mod\ }b)$, hemos reducido tanto los argumentos (que es, en sustitución de $a$$b$, y la sustitución de $b$$a{\rm\ mod\ }b$, hemos sustituido tanto con las cosas que son más pequeños). La forma en que el (positivo) enteros de trabajo, que no puede durar para siempre. Esto tiene que terminar en algún momento. Pero la única forma en que se puede detener es al $b=0$ (ya que si $b\gt0$ siempre se puede seguir adelante), y, a continuación, $\gcd(a,0)=a$ tiros.

Answer 3

Si$\rm\:d\:|\:b\:$ entonces$\rm\:d\:|\:a\: \iff\: d\ |\ a-n\:b\:.\:$ Así $\rm\ a,b\ $% y$\rm\ a-n\:b,\:b\ $ tienen los mismos divisores comunes, por lo tanto, el mismo máximo común divisor. Finalmente$\rm\ a-n\:b\ =\ a\ mod\ b\ $ para algunos$\rm\:n\in \mathbb Z\:.$

Answer 4

Todo se basa en un simple hecho. Si$b = aq + r$ y$b, q, a, r\in \mathbb{Z}$, entonces$\gcd(a,b) = \gcd(a,r)$. Solo demuestre que un entero divide$a$ y$b$ iff divide$a$% y$r$ y listo.