ParthKohli Group Title Please explain me the Euclidean Algorithm. Help appreciated. 2 years ago 2 years ago

1. KingGeorge Group Title

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

2. ParthKohli Group Title

Okay - I follow.

3. KingGeorge Group Title

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 Group Title

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 Group Title

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

6. ParthKohli Group Title

May I have a practice problem?

7. KingGeorge Group Title

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

8. KingGeorge Group Title

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

9. asnaseer Group Title

@KingGeorge - wonderful explanation! :)

10. ParthKohli Group Title

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

11. Ishaan94 Group Title

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

12. ParthKohli Group Title

$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 Group Title

So, they are co-prime!

14. ParthKohli Group Title

Thank you :)

15. ParthKohli Group Title

Let me return back to that CRT question. Okay.

16. KingGeorge Group Title

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

17. ParthKohli Group Title

Haha no :P