Skip to main content
Mathematics LibreTexts

4.2: Euclidean algorithm and Bezout's algorithm

  • Page ID
    7534
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

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

    \( \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}}\)

    \( \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}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    \( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

    \( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

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

    \( \newcommand{\vectorC}[1]{\textbf{#1}} \)

    \( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

    \( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

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

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

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

    \(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)

    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.

    If \(a,b \in \mathbb{Z} \setminus \{0\}\), then by using division algorithm iteratively, we obtain

    \begin{eqnarray*}a &=bq_0+r_0 \\ b &=r_0 q_1+r_1 \\  r_0 &=r_1q_2+r_2\\ \vdots \\ r_{n-2} &=r_{n-1}q_{n}+r_n \\ r_{n}&=r_nq_{n+1}+0 \\ \end{eqnarray*}

    Notice that, the last non-zero remainder is \(r_{n}\), such an \(r_n\) exists, since \(|b|>|r_0|>|r_1| \cdots >|r_n|.\) The \(r_n=\gcd(a,b)\).

    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.

    Note

    This condition will be a necessary and sufficient condition in the case of \(d=1\). We will prof this result in section 4.4, Relatively Prime numbers.

    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\).

    Answer
    a b x y d=gcd(a,b)
             
             
             
             

     

     

     


    This page titled 4.2: Euclidean algorithm and Bezout's algorithm is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Pamini Thangarajah.