Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download
62 views
Tweet
Share
Share

The extended Euclidean Algorithm

This function computes the gcd of 2 integers a,ba,b using the Extended Euclidean Algorithm (EEA), outputting the triple (g,u,v)(g,u,v) where g=gcd⁡(a,b)=au+bvg=\gcd(a,b)=au+bv, and (by default) showing the working. 
def EEA(a,b,show_working=True):
    x1=1; y1=0; x2=0; y2=1; a1=a; a2=b;
    if show_working: print("r\tq\tx\ty\n%s\t%s\t%s\t%s" % (a1,' ',x1,y1))
    while a2!=0:
        a3=a1%a2; q=(a1-a3)//a2;
        x3=x1+q*x2; y3=y1+q*y2;
        if show_working: print("%s\t%s\t%s\t%s" %(a2,q,x2,y2))
        a1=a2; a2=a3; x1=x2; x2=x3; y1=y2; y2=y3
    if show_working: print("%s\t%s\t%s\t%s\n" % (a2,' ',x2,y2))
    if a*x1-b*y1>0:
        g,u,v = (a1,x1,-y1)
    else:
        g,u,v = (a1,-x1,y1)
    assert g==a*u+b*v
    return g,u,v
By default, the working is shown: 
EEA(355,113)
r q x y 355 1 0 113 3 0 1 16 7 1 3 1 16 7 22 0 113 355 (1, -7, 22)
-- but it can be turned off: 
EEA(355,113, show_working=False)
(1, -7, 22)
Consecutive Fibonacci numbers are coprime, and the Euclidean algorithm recreates the sequence in reverse, with all quotients being 1: 
list(fibonacci_sequence(23))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711] 
EEA(6765,10946)
r q x y 6765 1 0 10946 0 0 1 6765 1 1 0 4181 1 1 1 2584 1 2 1 1597 1 3 2 987 1 5 3 610 1 8 5 377 1 13 8 233 1 21 13 144 1 34 21 89 1 55 34 55 1 89 55 34 1 144 89 21 1 233 144 13 1 377 233 8 1 610 377 5 1 987 610 3 1 1597 987 2 1 2584 1597 1 2 4181 2584 0 10946 6765 (1, 4181, -2584)
π\pi 


EEA(833719,265381)
r q x y 833719 1 0 265381 3 0 1 37576 7 1 3 2349 15 7 22 2341 1 106 333 8 292 113 355 5 1 33102 103993 3 1 33215 104348 2 1 66317 208341 1 2 99532 312689 0 265381 833719 (1, -99532, 312689)