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 using the Euclidean algorithm, and find integers such that
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 , so .
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 , .
Remark. This is the corrected exercise from Université Lyon 1.