Maths WorkshopMaths problems with full solutions
Exercise 748Number theory › Divisibility and gcdHigh schoolAdded 2 Nov 2026

The Euclidean algorithm and Bézout identity

#Euclidean algorithm#Bézout identity#divisibility computation

Statement

Compute \divisibility(8303,2717)\divisibility(8303,2717) using the Euclidean algorithm, and find integers u,vu,v such that
8303u+2717v=\divisibility(8303,2717).8303u+2717v=\divisibility(8303,2717).

Hint

Perform successive Euclidean divisions and back-substitute.

Show solutionHide solution

Solution

Euclidean algorithm.
\begin{align*}
8303 &= 3\cdot2717+152,\\
2717 &= 17\cdot152+133,\\
152 &= 1\cdot133+19,\\
133 &= 7\cdot19+0.
\end{align*}
The last nonzero remainder is 1919, so \divisibility(8303,2717)=19\divisibility(8303,2717)=19.

Back-substitution.
\begin{align*}
19 &= 152-133\\
&=152-(2717-17\cdot152)=18\cdot152-2717\\
&=18(8303-3\cdot2717)-2717\\
&=18\cdot8303-55\cdot2717.
\end{align*}
So u=18u=18, v=−55v=-55.

Remark. This is the corrected exercise from Université Lyon 1.