[CRYPTOHACK] MODULAR ARITHMETIC

Greatest Common Divisor

def gcd(m, n):
    if m < n:
        m,n = n, m
    if n == 0:
        return m
    if m % n == 0:
        return n
    else:
        return gcd(n, m%n)

def main():
    print(gcd(66528, 52920))   
    
if __name__ == "__main__":
	main()

def gcd(m,n):
    while n != 0:
       r = m%n
       (m,n) = (n,r)
    return abs(m)

def main():
    print(gcd(66528, 52920))   
    
if __name__ == "__main__":
	main()

1512

 

 

MODULAR ARITHMETIC

def extended_gcd(a, b):
    if b > a:
        a, b = b, a
    if b == 0:
        return 0, 1  
    r = a % b
    print("a:{}, b:{}, r:{}".format(a, b, r))      
    v, u = extended_gcd(r, b)
    print("exit - a:{}, b:{}, v:{}, u:{}, r:{}".format(a, b, v, u, r))  
    return u - (a//b) * v, v


def main():  
    u, v = extended_gcd(26513, 32321)
    print("{}, {}".format(u, v))
    
if __name__ == "__main__":
	main()

-8404