Hay varias formas, pero me quedo con el algoritmo Euclid, ya que es decentemente rápido. Describiré las 3 formas (principales) en Python:
Existe la forma normal, la forma extendida y la forma binaria extendida:
Ok la forma normal:
def mcd (a, b):
si a == 0 o b == 0: devuelve max (abs (a), abs (b))
si a == 1 o b == 1: devuelve 1
z1 = abs (a)
z2 = abs (b)
mientras que no (z1% z2 == 0 o z2% z1 == 0):
# a% b da el recordatorio de a dividido por b
tz1 = z1
z1 = max (z1, z2)% min (z1, z2) si z1 == max (z1, z2) más z1
z2 = max (tz1, z2)% min (tz1, z2) si z2 == max (tz1, z2) más z2
retorno min (z1, z2)
- X e y son dos números naturales, si x ^ 2 + y ^ 2 es divisible por 21, ¿cuáles son los restos cuando x e y se dividen por 21 respectivamente?
- ¿Son los problemas básicos de matemáticas comunes dados a los estudiantes de primaria similares a los problemas dados a los estudiantes de matemáticas que estudian la teoría de números?
- ¿Cuál es el resto cuando (5 ^ 97) se divide por 52?
- Cómo demostrar que solo hay un número finito de soluciones enteras positivas para: [matemáticas] (n + 1) ^ k-1 = n! [/ Matemáticas]
- Dada una k particular, ¿existen técnicas especiales para mostrar si existe una n, de modo que 2 ^ n * k + 1 y 2 ^ n * k-1 sean primos?
Que hay la versión extendida.
Por lo tanto, una pequeña teoría de números: si a y b son enteros, no 0, entonces hay enteros u y v tales que [math] u \ times a + v \ times b = \ operatorname {gcd} (a, b) [/ math ]
Ahora la versión extendida nos dará u y v como bonificación
def gcde (a, b):
A = [max (abs (a), abs (b)), 1, 0]
B = [min (abs (a), abs (b)), 0, 1]
mientras que no A [0]% B [0] == 0:
q = int (A [0] / B [0])
C = B
B = [A [r] -q * C [r] para r en el rango (len (A))]
A = C
u = -B [1] si a <0 más B [1]
v = -B [2] si b <0 más B [2]
devuelve B [0], u, v
Algoritmo binario extendido (aprovecha algunas propiedades del sistema binario, pero como se describe es solo para enteros positivos):
def gcdeb (a, b):
si a <0 o b <0: devuelve "¡Usa otro algoritmo!"
e = 0
mientras que a% 2 == 0 y b% 2 == 0:
a, b, e = a // 2, b // 2, e + 1
A = [a, 1, 0]
B = [b, 0, 1]
primero = verdadero
mientras que primero o (no A [0] == B [0]):
si primero:
primero = falso
más:
si A [0]> B [0]:
temp = A
A = [temp [i] -B [i] para i en rango (len (temp))]
mientras que A [0]% 2 == 0:
A [0] = A [0] // 2
si A [1]% 2 == 0 y A [2]% 2 == 0:
A [1], A [2] = A [1] // 2, A [2] // 2
elif A [1]> 0:
A [1] = (A [1] -b) // 2
A [2] = (A [2] + a) // 2
más:
A [1] = (A [1] + b) // 2
A [2] = (A [2] -a) // 2
más:
temp2 = B
B = [temp2 [j] -A [j] para j en rango (len (temp2))]
mientras que B [0]% 2 == 0:
B [0] = B [0] // 2
si B [1]% 2 == 0 y B [2]% 2 == 0:
B [1], B [2] = B [1] // 2, B [2] // 2
elif B [1]> 0:
B [1] = (B [1] -a) // 2
B [2] = (B [2] + b) // 2
más:
B [1] = (B [1] + a) // 2
B [2] = (B [2] -b) // 2
devuelve B [0] * (2 ** e), B [1], B [2] # B [1] es u y B [2] v
Las propiedades sobre las que se reúne este algoritmo son:
[matemáticas] \ operatorname {gcd} (a, b) = \ begin {cases} 2 \ times \ operatorname {gcd} \ left (\ frac {a} {2}, \ frac {b} {2} \ right) && \ text {si ayb son pares} \\ \ operatorname {gcd} \ left (\ frac {a} {2}, b \ right) && \ text {si a es par y b es impar} \\ \ operatorname {gcd} \ left (a, \ frac {b} {2} \ right) && \ text {si a es impar yb es par} \\ \ operatorname {gcd} \ left (\ frac {ab} {2 }, b \ right) && \ text {si a y b son impares y} a \ gt b \\ \ operatorname {gcd} \ left (a, \ frac {ba} {2} \ right) && \ text {if a y b son impares y} a \ lt b \ end {cases} [/ math]