problem in understanding gcd

gcd
medium
number-theory

#1

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


#2

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.


#3

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.


#4

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


#5

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


#6

@debjitdj

you have asked the same question which I asked.


#7

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.


#8

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