Euclid’s Algorithm for Finding gcd

 

Motivation:

 

                     While dealing with two very large numbers,  is there any quick way to find their greatest common divisor ( gcd ) without doing prime factorization ? Prime factorization for very large numbers is very time consuming.  Especially, finding a large prime itself is a big problem, not to mention to try that prime to do factorization. Euclid’s algorithm can handle this kind of questions.

 

 

Theorem ( Euclid’s Algorithm )

                Let  a, b be two natural numbers and  a > b .

                If   a = bq + r , where q , r  are positive integers and r < b,  then

                            

                                   gcd ( a, b ) = gcd ( b, r )

 

          Proof:

 

                                 Let g= gcd(a,b )  and d = gcd ( b,r ) .

                            Thus,   g | a   and  g | b

                                 g | (a-bq)

                                 g | r

 

                           So,  g is a common divisor of  b and r

                              g  d ( d is the greatest common divisor of b and r )

 

                       On the other hand,   d | b and  d | r

                              d | (bq+r)

                               d | a

 

                           So,  d is a common divisor of a and b

                                d  g ( g is the greatest common divisor of a and b )

 

                       We have   g  d  and  d  g ,  that means

                                             g = d

                             i.e.,     gcd ( a, b ) =  gcd ( b,r )

 

 

                       Using this result repeatedly,  we will be able to get  the gcd of the original two numbers.

 

 

 

 

 

Example:  Find gcd ( 57321, 15343) .

 

                   Let’s use the theorem repeatedly:

 

                        57321 =  15343  3  +  11292

                  So, 

                            gcd( 57321, 15343) = gcd ( 15343, 11292 )

 

               Similarly,      15343 = 11292  1 +  4051

                              gcd ( 15343, 11292 ) = gcd ( 11292, 4051 )

 

                  11292 = 4051  2 +  3190

                              gcd( 11292, 4051 ) = gcd ( 4051, 3190 )

 

                   4051 = 3190  1 +  861

                              gcd( 4051, 3190 ) = gcd ( 3190, 861 )

 

                  3190 = 861  3 + 607

                              gcd ( 3190, 861 ) = gcd ( 861, 607 )

 

                  861 = 607   1 +  254

                              gcd( 861, 607 ) = gcd( 607, 254 )

 

                  607 = 254  2 + 99

                              gcd( 607, 254 ) = gcd( 254, 99)

 

                  254 = 99  2 +  56

                              gcd( 254, 99) = gcd( 99, 56 )

 

                  99 = 56  1 + 43

                              gcd( 99, 56) = gcd( 56, 43)

 

                  56 = 43  1 + 13

                              gcd( 56, 43) = gcd( 43, 13)

 

                  43 = 13  1 + 4

                              gcd(43, 13) = gcd ( 13, 4)

 

                  13= 4  3 + 1

                              gcd(13,4) = gcd( 4,1 ) = 1

 

                 

 

                  So,  the gcd of the original two numbers is 1, i.e.,

                                gcd( 57321, 15343) = 1 .

 

 

                  The  whole process can be compressed via the following arrangement:

 

 

 

                                3 |       57321    |      15343   |  1

                                   |       46029    |      11292   |

                                   |   -----------   |     ---------  |

                               2  |       11292    |        4051   |  1

                                   |         8102    |        3190   |

                                   |   -----------   |     ---------  |

                              3   |         3190    |          861   | 1

                                   |         2583    |          607   |

                                   | -------------  |     ---------  |

                               2  |           607    |           254  |

                                   |           508    |           198  |

                                   |   -----------   |    ----------  |

                               1  |              99   |              56 | 1

                                   |              56   |              43 |

                                   |   ------------  |    ---------- |

                                3 |              43   |              13 | 3

                                   |              39   |              12 |

                                   |   -----------   |     ---------- |

                                   |                4   |                 1|