Basic and Extended Euclidean algorithms - GeeksforGeeks
Extended Euclidean Algorithm:
Extended Euclidean algorithm also finds integer coefficients x and y such that:
ax + by = gcd(a, b)
Read full article from Basic and Extended Euclidean algorithms - GeeksforGeeks