text: To adapt the extended Euclidean algorithm to this problem, one should remark that the Bézout coefficient of  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  provided by the algorithm satisfies . That is, if , one must add  to it at the end. This results in the pseudocode, in which the input n is an integer larger than 1.
  function inverse(a, n)
  t := 0;     newt := 1
  r := n;     newr := a
  while newr ≠ 0 do
  quotient := r div newr
  (t, newt) := (newt, t − quotient × newt)
  (r, newr) := (newr, r − quotient × newr)
  if r > 1 then
  return "a is not invertible"
  if t < 0 then
  t := t + n
  return t
  Simple algebraic field extensions
  The extended Euclidean algorithm is also the main tool for computing multiplicative inverses in simple algebraic field extensions. An important case, widely used in cryptography and coding theory, is that of finite fields of non-prime order. In fact, if  is a prime number, and , the field of order  is a simple algebraic extension of the prime field of  elements, generated by a root of an irreducible polynomial of degree .