Here's the question you clicked on:
ParthKohli
Please explain me the Euclidean Algorithm. Help appreciated.
First step, look at an example. I'll color things to make it easy to see what I'm doing.
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.\)
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.
So the point is that we must repeat it again and again till we get the remainder 0? That does make sense.
May I have a practice problem?
Try it out on \(a=342\) and \(b=295\).
One more thing, make sure \(0\leq r<b\) in the equation \(a=b\cdot q+r\).
@KingGeorge - wonderful explanation! :)
I wish that the Chrome Aw Snap didn't exist.
OMG I never knew it's called euclidean algorithm. I love this method. lol
\[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 \]
So, they are co-prime!
Let me return back to that CRT question. Okay.
You're welcome. If you want a proof of the algorithm, I could probably type that up as well.