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

×

# problem in understanding gcd

 0 can anyone please explain how gcd(a,b)=gcd(b,a%b) asked 25 May '16, 08:31 1★arpit728 683●17●65 accept rate: 10%

 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. answered 25 May '16, 11:58 4★debjitdj 465●1●9 accept rate: 31% @debjitdj 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★
 0 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 628●7 accept rate: 10%
 0 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 16●1 accept rate: 100%
 0 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 4★ishpreet 97●1●8 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×2,595
×631
×319

question asked: 25 May '16, 08:31

question was seen: 2,173 times

last updated: 25 May '16, 23:39