Algebra Den

Successive Division Method (HCF / GCD)

Calculating HCF / GCD by Prime Factorisation Method is long and more time-consuming, and due to these disadvantages new method was evolved by Mathematician namely, Successive Division Method

Under Successive Division Method, HCF / GCD = The Last Divisor of the given numbers .

Following examples can guide you How to calculate HCF / GCD by Successive Division Method ?

Example = 1 By using Successive Division Method, find the HCF of 24 & 18 ?
Answer = Steps and the way of finding HCF by Successive Division Method is as :-
            
18 | 24 | 1                 Step 1 = Divide the larger number 24 by the smaller number 18. And this division will give remainder 6.
       18             
         6 | 18 | 3          Step 2 = Now, divide 18 (divisior of step 1) with 6 (remainder of step 1)
              18
                0               Step 3 = Division in Step 2 give us remainder 0(Zero). And The Last Divisor is the HCF of 24 & 18.
Hence, HCF = 6

Example = 2 Find the GCD of 20, 30,& 40 by Successive Division Method ?
Answer = As here three numbers are given, so it involves Two Phases.
                Phase 1 - Find the GCD of 20 & 30 :-
            
20 | 30 | 1                 Step 1 = Divide the larger number 30 by the smaller number 20. And this division will give remainder 10.
       20             
       10 | 20 | 2          Step 2 = Now, divide 20 (divisior of step 1) with 10 (remainder of step 1)
              20
                0               Step 3 = Division in Step 2 give us remainder 0(Zero). And The Last Divisor is the GCD of 20 & 30 = 10

                Phase 2 - Find the GCD of 10(GCD of 20 & 30) & 40(given number) :-
            
10 | 40 | 4                 Step 1 = Divide the remaining given number 40 by the GCD of 20 & 30 i.e.20.
       40
          0           Step 2 = Division in Step 2 give us remainder 0(Zero). And The Last Divisor is the GCD of 10 & 40 = 10
From Phase 1 & Phase 2, we concluded, GCD of 20, 30 & 40 = 10