Editing Extended Euclidean algorithm (section)

===Modular integers===
{{main|Modular arithmetic}}
If {{math|''n''}} is a positive integer, the [[Ring_(mathematics)|ring]] {{math|[[Z/nZ|'''Z'''/''n'''''Z''']]}} may be identified with the set {{math|{0, 1, ..., ''n''-1}{{void}}}} of the remainders of [[Euclidean division]] by {{math|''n''}}, the addition  and the multiplication consisting in taking the remainder by {{math|''n''}} of the result of the addition and the multiplication of integers. An element {{math|''a''}} of {{math|'''Z'''/''n'''''Z'''}} has a multiplicative inverse (that is, it is a [[unit (ring theory)|unit]]) if it is [[coprime]] to {{math|''n''}}. In particular, if {{math|''n''}} is [[prime number|prime]], {{math|''a''}} has a multiplicative inverse if it is not zero (modulo {{math|''n''}}). Thus {{math|'''Z'''/''n'''''Z'''}} is a field if and only if {{math|''n''}} is prime.

Bézout's identity asserts that {{math|''a''}} and {{math|''n''}} are coprime if and only if there exist integers {{math|''s''}} and {{math|''t''}} such that 
:<math>ns+at=1</math>
Reducing this identity modulo {{math|''n''}} gives 
:<math>at \equiv 1 \mod n.</math>
Thus {{math|''t''}}, or, more exactly, the remainder of the division of {{math|''t''}} by {{math|''n''}}, is the multiplicative inverse of {{math|''a''}} modulo {{math|''n''}}.

To adapt the extended Euclidean algorithm to this problem, one should remark that the Bézout coefficient of {{math|''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 {{math|''t''}} provided by the algorithm satisfies {{math|{{!}}''t''{{!}} < ''n''}}. That is, if {{math|''t'' < 0}}, one must add {{math|''n''}} 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