Find the greatest common divisor of 314 and 520 by using the

Find the greatest common divisor of 314 and 520 by using the Euclidean Algorithm.

Solution

In Euclidean algorithm, we divide greater number from smaller number always and each last divisor is divided by remaining of each step. This process continues till we get the last remainder zero.

So here on dividing 520 by 314, it goes 1 time and we get remainder 206

314) 520( 1

       314

-------------- On subtracting

        206 ) 314 ( 1                       Now 314 is divided by remainder 206 that goes 1 time and we get remainder 108

              - 206

             -----------

               108 ) 206 ( 1               Now we divide 206 by remainder 108 that goes 1 time and remainder is 98

                     - 108

                     ---------

                         98 ) 108 ( 1        On dividing divisor 108 by remainder 98, we again get remainder 10

                               -98

                             ---------

                                10 ) 98 ( 9         On continueing the same procedure

                                     -90

                                     --------

                                       8 )10 ( 1

                                         - 8

                                        -------

                                           2 ) 8 ( 4

                                              - 8

                                           ----------

                                               0

So as when remainder is zero, our last divisor is 2, that means that 2 is the greatest common divisor of 314 and 520.

So last answer is 2.