## ParthKohli 4 years ago Please explain me the Euclidean Algorithm. Help appreciated.

1. KingGeorge

First step, look at an example. I'll color things to make it easy to see what I'm doing.

2. ParthKohli

Okay - I follow.

3. KingGeorge

Look at $$a=572$$ and $$b=165$$. The euclidean algorithm will give us the gcd of these two numbers. Here's how you would find it $572=\color{red}{165}\cdot3+\color{green}{77}$$\color{red}{165}=\color{green}{77}\cdot2+\color{blue}{11}$$\color{green}{77}=\color{blue}{11}\cdot7+0$Now that that last number is 0, look at the remainder above it. In this case, that's 11. Hence, $$\gcd(572,165)=11.$$

4. KingGeorge

The last number in each of those lines is called the "remainder" and the black numbers (3,2,7) are the quotients. In general, given any two numbers $$a,b$$, they can be written as $a=b\cdot q +r$where q=quotient and r=remainder.

5. ParthKohli

So the point is that we must repeat it again and again till we get the remainder 0? That does make sense.

6. ParthKohli

May I have a practice problem?

7. KingGeorge

Try it out on $$a=342$$ and $$b=295$$.

8. KingGeorge

One more thing, make sure $$0\leq r<b$$ in the equation $$a=b\cdot q+r$$.

9. asnaseer

@KingGeorge - wonderful explanation! :)

10. ParthKohli

I wish that the Chrome Aw Snap didn't exist.

11. anonymous

OMG I never knew it's called euclidean algorithm. I love this method. lol

12. ParthKohli

$342= 295\cdot 1 + 47$$295 = 47 \cdot 6+13$$47 = 13\cdot 3+8$$13 = 8\cdot 1 + 5$$8 = 5 \cdot 1 + 3$$5 = 3 \cdot 1 + 2$$3 = 2 \cdot 1 + 1$$2 = 1 \cdot 2 + 0$

13. ParthKohli

So, they are co-prime!

14. ParthKohli

Thank you :)

15. ParthKohli

Let me return back to that CRT question. Okay.

16. KingGeorge

You're welcome. If you want a proof of the algorithm, I could probably type that up as well.

17. ParthKohli

Haha no :P