CMP.2:5.2 - A subproblem obtained by a transformation

To compute gcd(48,18), replace the pair by (18,12), then (12,6), then (6,0), and return 6. The equality gcd(a,b)=gcd(b,a mod b) follows because a common divisor of either pair divides both entries of the other pair. The remainder operation and decreasing second component turn that equality into a returning procedure.

If the next use also needs coefficients u,v with u*a+v*b=gcd(a,b), the returned number alone is insufficient. Suppose the smaller call supplies d=u'*b+v'*r, with r=a-q*b. Substitution gives d=v'*a+(u'-q*v')*b; return the updated coefficients too. For the original pair, 6=(-1)*48+3*18. The same recursive decomposition supports a stronger output through a changed join.