Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

4.2 Euclidean algorithm and Bezout's algorithm

  • Page ID
    7534
  • [ "stage:draft", "article:topic", "authorname:thangarajahp", "Euclidean algorithm", "Bezout\'s algorithm" ]

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    Definition: Euclidean Algorithm

    The Euclidean Algorithm is an efficient way of computing the GCD of two integers.  It was discovered by the Greek mathematician Euclid, who determined that if n goes into x and y, it must go into x-y.  Therefore, we can subtract the smaller integer from the larger integer until the remainder is less than the smaller integer.  We continue using this process until the remainder is 0, thus leaving us with our GCD.

    Example \(\PageIndex{1}\)

    Find the GCD of 30 and 650 using the Euclidean Algorithm.
        650 / 30 = 21 R 20.  Now take the remainder and divide that into the original divisor.
        30 / 20 = 1 R 10.  Now take the remainder and divide that into the previous divisor.
        20 / 10 = 2 R 0.  Since we have a remainder of 0, we know that the divisor is our GCD.
    Therefore, the GCD of 30 and 650 is 10.

    Example \(\PageIndex{2}\): 

    Find  \(\gcd(2420, 230)\).

    Note:  Work from right to left to follow the steps shown in the image below.

    Euclidean1.png

    Hence,   \(\gcd(2420,230) =10\).

    Example \(\PageIndex{3}\): 

    Find  \(\gcd(3915, 825)\).
    Note:  Work from right to left to follow the steps shown in the image below.

    Euclidean2.png

    Hence,  \(\gcd(3915, 825 )=15\).

    Example \(\PageIndex{4}\): Geometric GCD

    We want to tile an a ft by b ft (a, b \(\in \mathbb{Z}\)) floor with identical square tiles.  What is the largest square tile we can use? \(\gcd(a, b)\).

    Consider the following example where \(a=100\) and \(b=44\).

    geometricgcd.png

    The largest square tile we can use to completely tile a 100 ft by 44 ft floor is a \(4\) ft by \(4\) ft tile.

    BEZOUT'S IDENTITY

    For integers a and b, let d be the greatest common divisor, d = GCD (a, b).  Then there exists integers x and y such that ax+by=d.  Any integer that is of the form ax+by, is a multiple of d.

    Bezout Algorithm

     Use the Euclidean Algorithm to determine the GCD, then work backwards using substitution.  WHEN DOING SUBSTITUTION BE VERY CAREFUL OF THE POSITIVES AND NEGATIVES.

    Example \(\PageIndex{5}\)

    Find the Bezout Identity for a=34 and b=19.

    Solution

    First, find the gcd(34, 19).
        34 = 19(1) + 15.
        19 = 15(1) + 4.
        15 = 4(3) + 3.
           4 = 3(1) + 1.
           3 = 1(3) + 0.
    Thus, the gcd(34, 19) = 1.

    Next, work backwards to find x and y.
        1    = 4 - 1(3).
               = 4 - 1(15 - 4(3)) = 4(4) - 1(15).
               = 4(19 - 15(1)) -1(15) = 4(19) - 5(15).
               = 4(19) - 5(34 - 19(1)) = 9(19) - 5(34).

    Thus Bezout's Identity for a=34 and b=19 is 1 = 34(-5) + 19(9).

    Example \(\PageIndex{6}\): Tabular Method, yielding GCD and Bezout's Coefficients

     

    Find Bezout's Identity for a = 237 and b = 13.

    Solution:

     

    (1) Set up the initial table.

    This step is always the same regardless of which numbers you are trying to find the GCD of.

    Iteration

     

    Remainder

     

    Quotient

     

    Coefficients of Bezout’s

    i

    r

    q

    s

    t

    0

     

     

    1

    0

    1

     

     

    0

    1

    2

     

     

     

     

     

    (2) Insert numerator into R0C1

    (3) Insert denominator into R1C1

    (4) Integer divide R0C1 by R1C1 and place result into R1C2

    (5) Place remainder from (4) into R2C1

     

    Table at right shows completed steps 1 - 5 of GCD(237,13).  Note: 237/13 = 18 R 3

    i

    r

    q

    s

    t

    0

    237

     

    1

    0

    1

    13

    18

    0

    1

    2

    3

     

     

     

     

    (6) add new line to table, increment i.

    (7) RiC2 is integer division Ri-1C1/RiC1

    (8) Place remainder from (7) into Ri+1C1

    Note: 13/3 = 4 R 1

    (9) RiC3 is Ri-2C3 - (Ri-1C2 * R i-1C3)

    (10) RiC4 is Ri-2C4 - (Ri-1C2 * R i-1C4)

    i

    r

    q

    s

    t

    0

    237

     

    1

    0

    1

    13

    18

    0

    1

    2

    3

    4

    1

    -18

    3

    1

     

     

     

     

    Repeat steps 6 - 10 until RiC1 = 0

    Completed table for GCD(237,13) at right.

     

    GCD (237,13) = 1 = first non zero remainder.

    Write answer as:

    GCD(237,13) = 1

            = -4(237) + 73(13)

     

    Where -4=s and 73=t.  The GCD = 1 indicates that the numbers are relatively prime.

    Iteration

    Remainder

    Quotient

    Coefficients of Bezout’s 

    i

    r

    q

    s

    t

    0

    237

     

    1

    0

    1

    13

    18

    0

    1

    2

    3

    4

    1

    -18

    3

    1

    3

    -4

    73

    4

    0

     

     

     

    Thus, the Bezout's Identity for a=237 and b=13 is 1 = -4(237) + 73(13).

    Example \(\PageIndex{7}\):

    Find the GCD of 149553 and 177741:

    First, use the Euclidean Algorithm to determine the GCD.
        177741/149553 = 1 R 28188
        149553/28188 = 5 R 8613
        28188/8613 = 3 R 2349
        8613/2349 = 3 R 1566
        2349/1566 = 1 R 783
        1566/783 = 2 R 0
    Because we have a remainder of 0 we have now determined that 783 is the GCD.

    Next, find \(x, y  \in \mathbb{Z}\) such that 783=149553(x)+177741(y).
        Using the answers from the division in Euclidean Algorithm, work backwards.
            783= 2349+1566(-1).
            1566=8613+2349(-3).
            2349=28188+8613(-3).
            8613=149553+28188(-5).
            28188=177741+149553(-1).
        Now substitute in,
            783   =2349+1566(-1).
                        =2349 +(8613 + 2349(-3))(-1)
                        =2349 +(8613(-1)+2349(3)
                        =2349(4)+8613(-1)
                        =(28188+8613(-3))(4)+8613(-1)
                        =28188(4)+8613(-13)
                        =28188(4)+(149553+28188(-5))(-13)
                        =28188(69)+149553(-13)
                        =(177741+149553(-1))(69)+149553(-13)
                        =177741(69)+149553(-82)
        Thus, Bezout's Identity is 783=177741(69)+149553(-82).

    Example \(\PageIndex{8}\):

    Let \(a,b \in \mathbb{Z}\).  If \(ax+by=12\) for some integers \(x\) and \(y\).  Then what are the possible values for \(\gcd(a, b)\).  For these values find possible values for \(a, b, x\) and \(y\).