10
Oct

# 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.

• tonite says:

thanks! that is so cool!

• Phostings1 says:

thats pretty awesome! Thanks!

• Mamish Demamish says:

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

• abekmuratov says:

Thanks from Kazakhstan! Keep it up!

• Nafil Lukman Saad says:

thankyou for the help!

• Videoarsfulll says:

Thanks!

• Rebin Abdullah says:

thanks a lot for the help 🙂

• thedv8ed1 says:

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?

• strickenchord says:

This is truly genius, thanks for the explanation.

• Epoxy Magic says:

haaaa thanks a lot…

• Epoxy Magic says:

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

• Antonio Sanchez says:

Dude awesome! <3 :]

• George Nikolaou says:

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

• U3DART says:

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

• EliotLeo says:

So polite, xD

• nwind27 says:

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

• mathtrain says:

Well… I'm a teacher. 🙂

• manz92 says:

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!

• manz92 says:

…and this guy is good

• michael ackroyd says:

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

• George Pan says:

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

• Braily Glenn says:

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

• José A. Lopez says:

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

• BenThomas33 says:

Thanks, very simple

• Атанас Добрев says:

Thank you for your time!

• drewtube8181 says:

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

• shapour shapouri says:

awesome

• Tanis Phongphisantham says:

thanks

• mabic balajadia says:

Thank you…ur better than my teacher☺️

• The Eclectic Dyslexic says:

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

• Raina Gardaya says:

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

• Regina Ciambrone says:

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

• Joe Kim says:

thanks!

• Hentai404 says:

This is an extremely good explanation. Thank you.

• Sohail Nawab says:

wow what a good explanation

• Gladys Datita says:

thanks

• Muhammed Javed says:

THE BEST (;

• Toshika Lata says:

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.

• jacob hazen says:

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

• Mahmoud Akram says:

special thanks for you

• Saravanan M K says:

Thank you.

• Drawing Doodles says:

THANK YOU SOOOO MUCH

• Senada Pasic says:

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

• Gleny Rebello says:

Thank you

• Kristy Burton says:

Thankyou 😃

• hajji munir says:

• Pink fluffy Kangaroo says:

• Solomon says:

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.

• BTW says:

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.

• Halima Rehman says:

What to do in more than two numbers?

• Moaz El-sawaf says:

Really thank you sir so much ❤

• ahmed ehab says:

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

• Harish Vijayan says: