Instituto Tecnológico de Costa Rica

Introducción Teoría de números

Se usa a\2 para dividir entre dos y a Mod 2 = 0 para detectar números pares. Cada renglón muestra el nuevo problema equivalente de MCD.

Algoritmo binario para el MCD

genera · sigue · verifica

a b

inicio: mcd(89, 44) 10 pasos resultado: 1

a\2 divide por 2 · a Mod 2 = 0 prueba paridad

Si ambos son impares, se reemplaza el mayor por |a − b|\2.

lista completa de problemas equivalentes

mcd(89, 44) = 1