You are not logged in. Please login at to post your questions!


problem in understanding gcd

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

asked 25 May '16, 08:31

arpit728's gravatar image

accept rate: 10%

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.


answered 25 May '16, 11:58

debjitdj's gravatar image

accept rate: 31%


you have asked the same question which I asked.

(25 May '16, 15:59) arpit7281★

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.

(25 May '16, 19:11) debjitdj4★

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

(25 May '16, 19:50) debjitdj4★

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

rajarshi_basu's gravatar image

accept rate: 10%

edited 25 May '16, 22:50

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


answered 25 May '16, 23:39

vijayarsenal10's gravatar image

accept rate: 100%

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

ishpreet's gravatar image

accept rate: 0%

edited 25 May '16, 23:03

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 25 May '16, 08:31

question was seen: 2,173 times

last updated: 25 May '16, 23:39