The Euclidean Algorithm and Bezout’s Theorem

Purpose
The Euclidean Algorithm and Bezout’s Theorem are essential for determining units and solving systems of modular equations, the purpose of this page is to give additional practice problems to help build your fluency when computing the greatest common divisor or integers u and v such that d=ua+vb.

The Euclidean Algorithm: Let a,b \in \mathbb{N} with b<a and b \nmid a. Then there exists n \in \mathbb{N}, q_1,\dots,q_{n+1} \in \mathbb{N} and r_1,\dots,r_n \in \mathbb{N} such that

    \begin{align*}a&=q_1b+r_1 &&\text{with }0<r_1<b \\b&=q_2r_1+r_2 &&\text{with } 0<r_2<r_1 \\r_1&=q_3r_2+r_3 && \text{with } 0<r_3<r_2 \\&&\vdots\hspace{35pt}&\\r_{n-3}&=q_{n-1}r_{n-2}+r_{n-1} && \text{with } 0<r_{n-1}<r_{n-2} \\r_{n-2}&=q_{n}r_{n-1}+r_{n} && \text{with } 0<r_{n}<r_{n-1} \\r_{n-1}&=q_{n+1}r_{n}\end{align*}


Then, r_n = \gcd(a,b).

Exercises

For the following problems, try to complete them by yourself. To check your solution, click the arrow at the beginning of the problem statement.
Compute \gcd(5,18) using the Euclidean Algorithm.

Solution:

    \begin{align*} 18 &= 5\cdot 3 + 3 \\ 5 &= 3\cdot 1 + 2 \\ 3 &= 2\cdot 1 + 1 \\ 2 &= 1\cdot 2 \end{align*}

Therefore, \gcd(5,18)=1.

Compute \gcd(21,6) using the Euclidean Algorithm.

Solution:

    \begin{align*} 21 &= 6\cdot 3 + 3 \\ 6 &= 3\cdot 2 \end{align*}

Therefore, \gcd(21,6)=3.

Compute \gcd(101,13) using the Euclidean Algorithm.

Solution:

    \begin{align*} 101 &= 13\cdot 7 + 10 \\ 13 &= 10\cdot 1 + 3 \\ 10 &= 3 \cdot 3 + 1 \\ 3 &= 1 \cdot 3 \end{align*}

Therefore, \gcd(101,13)=1.

Compute \gcd(1235,27) using the Euclidean Algorithm.

Solution:

    \begin{align*} 1235 &= 27\cdot 45 + 20 \\ 27 &= 20\cdot 1 + 7 \\ 20 &= 7 \cdot 2 + 6 \\ 7 &= 6 \cdot 1 + 1 \\ 6 &= 1 \cdot 6 \end{align*}

Therefore, \gcd(1235,27)=1.

Bezout’s Theorem: Let a,b,n,r_1,\dots,r_n,q_1,\dots,q_{n+1} \in \mathbb{N} be as in the Euclidean Algorithm. Then, there exists u,v \in \mathbb{Z} such that

    \[\gcd(a,b)=ua+vb\]


More precisely, if we set u_0:=0, v_0:=1, u_1:=1, and v_1:=-q_1 and define recursively,

    \[u_i:=u_{i-2}-q_iu_{i-1} \text{ and } v_i:=v_{i-2}-q_iv_{i-1}\]


for i=2,\dots,n, then r_i=u_ia+v_ib for all i=1,\dots,n. In other words,

    \[\gcd(a,b)=r_n=u_na+v_nb\]

Exercises

For the following problems, try to complete them by yourself. To check your solution, click the arrow at the beginning of the problem statement.
Using Bezout’s Theorem, find u,v \in \mathbb{Z} such that \gcd(5,18)=18u+5v.

Solution:

    \[\begin{array}{rcccc} &&q_i&u_i&v_i \\ i=0: &&& 0 & 1 \\ i=1: & 18=5\cdot 3+3 & 3 & 1 &-3 \\ i=2: & 5=3\cdot 1 + 2 & 1 & -1 & 4 \\ i=3: & 3 = 2\cdot 1 + 1 & 1 & \textcolor{blue}{2} &\textcolor{red}{-7} \\ i=4: & 2 = 1\cdot 2 \end{array}\]

Therefore, \gcd(5,18)=18\cdot(\textcolor{blue}{2}) + 5\cdot(\textcolor{red}{-7}).


Using Bezout’s Theorem, find u,v \in \mathbb{Z} such that \gcd(21,6)=21u+6v.

Solution:

    \[\begin{array}{rcccc} &&q_i&u_i&v_i \\ i=0: &&& 0 & 1 \\ i=1: & 21=6\cdot 3+3 & 3 & \textcolor{blue}{1} &\textcolor{red}{-3} \\ i=2: & 6 = 3\cdot 2 \end{array}\]

Therefore, \gcd(21,6)=21\cdot(\textcolor{blue}{1}) + 6\cdot(\textcolor{red}{-3}).


Using Bezout’s Theorem, find u,v \in \mathbb{Z} such that \gcd(101,13)=101u+13v.

Solution:

    \[\begin{array}{rcccc} &&q_i&u_i&v_i \\ i=0: &&& 0 & 1 \\ i=1: & 101=13\cdot 7+10 & 7 & 1 &-7 \\ i=2: & 13=10\cdot 1 + 3 & 1 & -1 & 8 \\ i=3: & 10 = 3\cdot 3 + 1 & 3 & \textcolor{blue}{4} &\textcolor{red}{-31} \\ i=4: & 3 = 1\cdot 3 \end{array}\]

Therefore, \gcd(101,13)=101(\cdot\textcolor{blue}{4}) + 13\cdot(\textcolor{red}{-31}).


Using Bezout’s Theorem, find u,v \in \mathbb{Z} such that \gcd(1235,27)=1235u+27v.

Solution:

    \[\begin{array}{rcccc} &&q_i&u_i&v_i \\ i=0: &&& 0 & 1 \\ i=1: & 1235=27\cdot 45+20 & 45 & 1 &-45 \\ i=2: & 27=20\cdot 1 + 7 & 1 & -1 & 46 \\ i=3: & 20 = 7\cdot 2 + 6 & 2 & 3 &-137 \\ i=4: & 7 = 6\cdot 1 + 1 & 1 & \textcolor{blue}{-4} & \textcolor{red}{183} \\ i=5: & 6 = 1 \cdot 6 \end{array}\]

Therefore, \gcd(1235,27)=1235\cdot(\textcolor{blue}{-4}) + 27\cdot(\textcolor{red}{183}).