Extended Euclidean algorithm
Modular integers

If n is a positive integer, the ring Z / n Z may be identified with the set {0, 1,..., n -1} of the remainders of Euclidean division by n, the addition and the multiplication consisting in taking the remainder by n of the result of the addition and the multiplication of integers. An element a of Z / n Z has a multiplicative inverse (that is, it is a unit) if it is coprime to n. In particular, if n is prime, a has a multiplicative inverse if it is not zero (modulo n). Thus Z / n Z is a field if and only if n is prime.

Bézout's identity asserts that a and n are coprime if and only if there exist integers s and t such that

Reducing this identity modulo n gives

Thus t, or, more exactly, the remainder of the division of t by n, is the multiplicative inverse of a modulo n.

To adapt the extended Euclidean algorithm to this problem, one should remark that the Bézout coefficient of n is not needed, and thus does not need to be computed. Also, for getting a result which is positive and lower than n, one may use the fact that the integer t provided by the algorithm satisfies | t | < n. That is, if t < 0, one must add n to it at the end. This results in the pseudocode, in which the input n is an integer larger than 1.
keywords:forbidden_words