Método binario para calcular el MCD, por Hannu Hinkka

Antes de continuar, debería leer este tutorial de Totton:

• Encontrar el MCD y el MCM de dos números

El presente, es un método alternativo para calcular el máximo común divisor MCD(a,b) de dos números a y b. Necesitaremos algunas reglas simples:

1. Si a y b son ambos pares, entonces 2 es un factor común; divida a y b or 2.
2. Si a o b es par (pero no ambos), divida el número par por 2.
3. Si a y b son ambos impares, reste el número menor del mayor y divida el resultado por 2.
4. Continúe hasta que sea a = b. Entonces el valor encontrado es MCD(a,b)

Si, tras el cálculo a = b =1 y 2 no es un factor común, no hay MCD(a,b)

Por ejemplo, calcular MCD( 207,92)

      a           b
0000207000000000092 : Planteamiento
      a           b
0000207000000000046 : 92/2=46
      a           b
0000207000000000023 : 46/2=23
      a           b
0000092000000000023 : (207-23)/2=92
      a           b
0000046000000000023 : 92/2=46
      a           b
0000023000000000023  : 46/2=23, ahora a=b=23, por lo tanto MCD(207,92)=23

Por ejemplo, calcular MCD( 198,75)

       a          b
0000019800000000075 : Planteamiento
       a          b
0000009900000000075 : 198/2=99
       a          b
0000001200000000075 : (99-75)/2=12
       a          b
0000000600000000075 : 12/2=6
       a          b
0000003000000000075 : 6/2=3
       a          b
0000003000000000036 : (75-3)/2=36
       a          b
0000003000000000018 : 36/2=18
       a          b
0000003000000000009 : 18/2=9
       a          b
0000003000000000003 : (9-3)/2=3. Ahora a=b=3, por lo tanto MCD(198,75)=3

Nota: si 2 es un factor común de a y b las cosas son un poco diferentes.

Por ejemplo, calcular MCD(18,12)

x     a           b
0000018000000000012 : Planteamiento.
x     a           b
2000009000000000006 : 18/2=9, 12/2=6, 2 es un factor común. anótelo en la columna x.
x     a           b
2000009000000000003 : 6/2=3
x     a           b
2000003000000000003 : (9-3)/2=3. Ahora, 2 y 3 son factores comunes, por lo tanto MCD(18,12) es 2*3=6.

-Hannu Hinkka

http://tinyurl.com/q6j0zzruy