can anyone please explain how gcd(a,b)=gcd(b,a%b) asked 25 May '16, 08:31

It is basically the way we are taught hcf/gcd at school by ' the long division ' method.I hope you are familiar with it.For Example: gcd(15,10)=5. here, gcd(15,10)=gcd(10,{15%10=5}) This process is done recursively. As said above,it is formally known as the Euclidean Algorithm in number theory. debjitdj also gave an accurate description,though it is more formal. answered 25 May '16, 22:47

Assume $d = GCD(a,b)$. This means $db$ and $da$. Now consider $GCD(b, a\%b)$. Here $a\%b = a  b\lfloor\frac{a}{b}\rfloor$. Because $db$ and $da$ $d$ also divides these two terms separately and hence the difference also. Hence $d(a\%b)$. We also know that if for $x,y,z$ $xy$ and $xz$ then $xgcd(y,z)$ Hence $dGCD(b,a\%b)$. Substituting $d = GCD(a,b)$ we get $GCD(a,b)GCD(b,a\%b)$. We can similarly prove the other side also, that is, $GCD(b,a\%b)GCD(a,b)$. Hence $GCD(a,b) = GCD(b,a\%b)$. answered 25 May '16, 23:39

Euclid’s Algorithm: Idea behind Euclid’s Algorithm is GCD(A, B) = GCD(B, A % B). The algorithm will recurse until A % B = 0. Let A = 16, B = 10. GCD(16, 10) = GCD(10, 16 % 10) = GCD(10, 6) GCD(10, 6) = GCD(6, 10 % 6) = GCD(6, 4) GCD(6, 4) = GCD(4, 6 % 4) = GCD(4, 2) GCD(4, 2) = GCD(2, 4 % 2) = GCD(2, 0) Since B = 0 so GCD(2, 0) will return 2. The time complexity of Euclid’s Algorithm is O(log(max(A, B))). answered 25 May '16, 23:01
