Intro to Euclid's division algorithm

so you want to learn how to find the HC F of two numbers using Euclid's division algorithm now to do that let me begin with the question do you know how to find the HC F of two numbers say thirty two and twelve now depending on which standard I was asked this question I had different methods in six standard I was taught how to count all the factors like a nice obedient child I would write one into 32 2 into 16 4 into 8 and so on do the same for 12 and then just count what the common factors are 1 2 4 and then picked the biggest one from them that's it that's my head CF the highest common factor and this is the most intuitive method but in 6 they used to give us all small numbers so this was easy to do but if the numbers become big this is really hard it's very long at least so then they taught me how to do prime factorization do you remember prime factorization that's just writing down this number in its prime factorize form and then picking the minimum powers of each of the prime factors and multiplying them that gives you the answer as well the same HCF 2 squared which is 4 but now it's time to learn a method that's a recipe rather because I've never I think about the word algorithm in my head that the word I have is a recipe to find the hit CF once again so you may be wondering why do I need to know more than one methods one argument is because it's useful especially when the number becomes really big these this method Euclid's algorithm works faster the other one is actually really beautiful if you notice what's happening here and if you really try to understand why this recipe works it gets really beautiful so but before doing that let's first see what the recipe is what is this recipe this recipe says ok so you want the head CF of these two numbers I don't know why you want it but you want it so 32 comma 12 this is one way of writing this big problem called how to find the head sieve of 32 and 12 hits EF of 32 comma well now what this recipe says is check if 32 is divisible by 12 if it is divisible you're done 12 is here it's EF now think about that that's actually obvious if one number is divisible by the other then the smaller number is the HCF right so do that here is 32 divisible by 12 and fortunately it's not we can't go home you're not done yet so then it says interesting so if this number is not divisible by this then what you do is forget about this question forget about finding the head safe of 32 in 12 but find this other head CF find the head CF of and watch closely over here the smaller number which is 12 and the remainder that you get if you divide the bigger number by the smaller number and what is that in this case if you divide 32 byte well they remainder that you get will be 12 will go twice 24 and then there'll be 8 remaining because these numbers are small we can do it in our head it says the recipe says find the set CF you're like okay I can find this achieved but why should I find it and then the recipe will tell you you find this because this set C F and this is TF will be exactly equal so if you find this it's as good as finding this now notice that the recipe is not yet told you why does have why this works it's just telling you he trust me the head CF of this number will be the same as the head TF sorry the head chef of these two numbers will be the same as the hit save of these two numbers right now we will look at why this works later but let's first see what's how to do how to use the a recipe so okay you say fine maybe this head CF and the set CF are the same but even then I started with the head CF problem I asked you to find the edge sieve of 32 and 12 now you give back another head see a problem finally itself to I Nate how much you how useful is that but notice that the numbers have become smaller and more beautifully you will not find the it safe over here you will do the same thing again because if this set save is equal to this one you can apply the same step again you will ask it's okay you want me to find the edge save of Tooele Nate it's twelve divisible by it if it is it would have been the petty F of 2 ln 8 but it's not so do the same thing this is equal to the head CF of once again the that's right the smaller number the smaller number and the remainder that you will get if you divide the bigger by the smaller number which in this case if you divide 12 by 8 you'll get a remainder of 4 because 8 will go once now once again you ask the same question yes 8 divisible by 4 and in this case the answer is yes 4 will be the HCF and if you actually think about it hits you have ADHD f of 8 in 4 is a really simple problem right you know that the answer to this is 4 because 8 is divisible by 4 but the beauty here actually want the food to be in red color but the beauty here is that it's not just the HC of a Radian 4 it's also the hits here 4 is also the HTF of 12 and 8 and 4 is also the hit CF of 32 and 12 which is the original problem that you began with so Euclid's division algorithm has given you the head CF of 32 and 12 without doing prime factorization without having to know what each of these factors are so now I've just learned a new recipe we haven't yet seen why this works but let's use the recipe a couple of times to cook a couple of new dishes and then learn why it works so let's pick some other two numbers not three don't well maybe something slightly bigger maybe we can pick let's see maybe 627 and 40 45 now I want you to pause the video and watch what happens as you use this algorithm now or the recipe now to find the head CF of these two numbers I'm gonna do it so hit CF I want the head CF of these two number six twenty seven and forty five six 27 and 45 now I don't think one is divisible by the other it may be but because these numbers are big I'm not gonna swear I'm just gonna do it and see 6 27 divided by 45 if I get a remainder 0 I'll go home very happily I don't think that's gonna happen though so I have 45 going once and I have a 7 over here and then 1 over 17 that's remaining and then I have 177 that's the remainder now 45 goes probably 3 times there and then I can find five threes or 15 and then for threes are 12 so 135 and then I can find my final remainder so 7 minus 5 is 2 7 minus 3 is 4 and that's it so it's 42 so it does not is not divisible so clearly 45 is not the HCF of these two numbers but Euclid's division algorithm says that's okay don't feel bad you can find the HCF of the smaller number 45 and the remainder when you divide the bigger number by the smaller number which you just did it's 42 so 45 and 42 now fine go and find the HCF of these two now once again you can do some other method now maybe because you feel the numbers are smaller but I'm just gonna use Euclid's division algorithm again because it's it's fun so now find the HCF of the smaller number now why am I not checking because clearly 45 is not divisible by 4 you do if it were 42 is my head CF but it's not so I'm gonna use the smaller number in this case that's 42 and the remainder that I will get if I divide 45 by 42 which is 3/4 it will go once and I'll get my remainder to be 3 so 3 and now I asked my classic question again it's 42 divisible by 3 and in this case it is 4 plus 2 is 6 so there's the sum of the digits is it's a multiple so it's divisible by 3 and there I have it the HTF is 3 and therefore I can jump all the way back and say the HCF of these two numbers is also 3 by the magic of Euclid's division algorithm