Suppose you have such that . Then such that , so . Now apply the extended Euclidean algorithm to and :

.

Hence is a solution.

This method holds more generally. If , then such that if and only if . If this is the case, then the same method works.