# The Euclidean Algorithm (GCD or GCF)

(male) Hey there, it’s Mr. Marcos and we are going to learn about the Euclidean Algorithm. Euclid was a man that you may or may not have heard of. We’ll learn about him later maybe in a video and an algorithm is a process or a way of doing things over and over again. And this is a process to find

the GCD of some numbers… the greatest common divisor or

also known as the greatest common factor. and again for a different video we can go more into depth about what, what that means. But for now, if you know you wanna find the GCD of some numbers you can use the Euclidean Algorithm. So what you do is you take the large number and you put it inside the dividend and you divide them. So 12 goes into 30 and you go 2.

So it’s 24 and you get 6 remaining. Now what you do is you take the remainder and divide it into the divisor. So we take the 12 down here. 6 goes into 12 two times. And you get 12, zero remainder. And when you get zero, you stop and the final divisor is your answer. So there is our GCD of 12 and 30. Pretty simple. Let’s do another one. GCD of 216 and 594. OK So we take 594 and we divide it by 216. And it goes in… let’s see… 216 twice is 432. So it looks like it’s gonna go 2 times. 432… you get 2, 6, 1 left over. Now you take the 216 and you divide that by the 162 remainder. And it’s going to go one time. You get 54. I need a lttle bit of room so I’m gonna just get this whole thing shifted a little bit. OK, now I’m going to divide 54 into 162,

which is the divisor. 54 goes in… exactly three times. We got to zero. Therefore our answer is 54.

So the GCD of 216 and 594 is 54. Pretty simple. Pretty cool.

Thank you.

thanks! that is so cool!

thats pretty awesome! Thanks!

Why the hell did my school even teach me the slow ways if Euclid had worked out a fast way millennia earlier?

Thanks from Kazakhstan! Keep it up!

thankyou for the help!

Thanks!

thanks a lot for the help 🙂

what if you have more then two numbers? do you find the gcd of the two numbers then use the algorithm on the third number and gdc of the first two?

This is truly genius, thanks for the explanation.

haaaa thanks a lot…

I love the way my professor teaches it but you just broke it down in simple steps….

Dude awesome! <3 :]

That means that my 1965 computer is an ancient egyptian ? 😛

gcd(m, n) = gcd(n, m mod n )

So polite, xD

wow. your explanation is so easy and clear! thanks a lot

Well… I'm a teacher. 🙂

Because you are sitting In front of your computer in comfort and relaxing and actually seeking out knowledge rather than attending class and sitting and forcing yourself to learn!

…and this guy is good

and because of this i will now save over $700 wooooo. ty

This is the weirdest symbolism i 've ever seen, i am a 3rd grade University IT engineer and i 've never seen this :S

thank you so much, this really saved me grade:)

Thank you, I wish my college professor taught me this before. I will subscribe to your channel.

Thanks, very simple

Thank you for your time!

What application where you using here to do your writing? Seems pretty cool.

awesome

thanks

Thank you…ur better than my teacher☺️

Thanks, needed a brush up on this for my computational complexity class, and it was faster than finding it in the book.

actually I was dum in math but u teach me well no I've go a hing grade in math

Wow – so easy !! Thank you for this clip.

thanks!

This is an extremely good explanation. Thank you.

wow what a good explanation

thanks

THE BEST (;

if A=0 GCD(0,B)=B and if B=0 GCD(A,0)=A can you explain why the answer in first case is B and in next case it is A.

What do you do when lets say its gcd(30,12)

30 cannot go into 12

special thanks for you

Thank you.

THANK YOU SOOOO MUCH

This is grade one math, really . You just need a calculator for large numbers.

Thank you

Thankyou 😃

Its awesome thanku for uploading

Made easy

I’m literally in middle school and I have figured it out 😛

Pretty sure it’s the computer method of division. It’s fast and easy.

what if their remainder doesn't end up being 0? like what's the GCD (6,9)

Edit: guess its remainder will be the GCD in this case.

What to do in more than two numbers?

Really thank you sir so much ❤

by this way the GCD ( 16 , 26 ) =4 , and 26/4=6.5 ,,, then how ????

https://www.youtube.com/watch?v=f7Z-9TCJJmc

How does one use this algorithm if you have to find gcd of three numbers?