The Extended Euclidean Algorithm is an extension of the classical Euclidean Algorithm, which is primarily used for finding the greatest common divisor (GCD) of two integers. While the Euclidean Algorithm is efficient for determining the GCD, the Extended Euclidean Algorithm goes a step further by also finding the coefficients of Bézout's identity. These coefficients are