Euclidean algorithm
The integer exists because of the assumption that and are coprime. It can be constructed using the extended Euclidean algorithm. The extended Euclidean algorithm efficiently determines integers and that satisfy Bézout's identity: