 # problem in understanding gcd

can anyone please explain how gcd(a,b)=gcd(b,a%b)

Do you know, how Euclidean Algorithm works? I mean, the method to find gcd of two numbers by repeated dividing? Which is taught in our primary schools. like, gcd(13,5)= gcd(5,3) [which is actually gcd(5,13%5)]. Just go through a dryrun. I hope you will get it.

1 Like

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.

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))).

Assume d = GCD(a,b). This means d|b and d|a.

Now consider GCD(b, a\%b). Here a\%b = a - b\lfloor\frac{a}{b}\rfloor. Because d|b and d|a 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 x|y and x|z then x|gcd(y,z) Hence d|GCD(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).

@debjitdj