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).
I have not asked anything, I have given you the answer -_- . Go and ogle for ‘Euclidean Algorithm’. This is the process which is used by primary school students to find gcd of two numbers.
suppose a>=b and a=bq+r. Let, gcd(a,b)=g and gcd(b,r)=d.
Now, g divides (a-bq) that means g divides r. So, g divides b and r both. But d is gcd of b and r. So, g divides d.
Similarly, d divides (bq+r), so, d divides a. So d divides both a and b. But gcd of a and b is g. So, d divides g.
(d divides g) and (g divides d) => g=d. So, gcd(a,b)=gcd(b,a%b)=gcd(b,r).