You are not logged in. Please login at www.codechef.com 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

1★arpit728
6831765
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.

link

answered 25 May '16, 11:58

debjitdj's gravatar image

4★debjitdj
46519
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★

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.

link

answered 25 May '16, 22:47

rajarshi_basu's gravatar image

6★rajarshi_basu
6287
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)$.

link

answered 25 May '16, 23:39

vijayarsenal10's gravatar image

5★vijayarsenal10
161
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))).

link

answered 25 May '16, 23:01

ishpreet's gravatar image

4★ishpreet
9718
accept rate: 0%

edited 25 May '16, 23:03

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×2,595
×631
×319

question asked: 25 May '16, 08:31

question was seen: 2,173 times

last updated: 25 May '16, 23:39