Question

Please explain me the Euclidean Algorithm.
Help appreciated.

Answer 1

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

Answer 2

Okay - I follow.

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

May I have a practice problem?

Answer 7

Try it out on \(a=342\) and \(b=295\).

Answer 8

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

Answer 9

@KingGeorge - wonderful explanation! :)

Answer 10

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

Answer 11

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

Answer 12

\[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 \]

Answer 13

So, they are co-prime!

Answer 14

Thank you :)

Answer 15

Let me return back to that CRT question. Okay.

Answer 16

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

Answer 17

Haha no :P