Published by Dimitris Kougioumtzis · Updated
Use Bézout coefficients to find x such that value × x ≡ 1 modulo modulus, when the GCD is one.
Use a Bezout coefficient from extended Euclid as the inverse when the GCD is one.
When to use Modular inverse (extended Euclidean)
Modular division under coprimality.
Choosing an alternative
Exponentiation-based inverse formulas need additional modulus assumptions.
Worked example: input and state changes
Example input
17,3120
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ 3120, 17, 0, 1 ], "active": [] }Step 1: Euclidean quotient 183; state: remainder, next remainder, coefficient, next coefficient.
State at this checkpoint
{ "values": [ 17, 9, 1, -183 ], "active": [ 0, 1, 2, 3 ] }Step 3: Euclidean quotient 1; state: remainder, next remainder, coefficient, next coefficient.
State at this checkpoint
{ "values": [ 8, 1, 184, -367 ], "active": [ 0, 1, 2, 3 ] }Step 4: Euclidean quotient 8; state: remainder, next remainder, coefficient, next coefficient.
State at this checkpoint
{ "values": [ 1, 0, -367, 3120 ], "active": [ 0, 1, 2, 3 ] }Step 5: Modular inverse = 2753.
State at this checkpoint
{ "values": [ 1, 0, -367, 3120 ], "active": [], "result": 2753 }
Expected final state
Modular inverse = 2753.
Complexity and input bounds
Family: Number theory. Time complexity: O(log modulus).
Space complexity: O(1) iterative state.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
value,modulus; value 0–9999 and modulus 2–9999.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Not every value has an inverse; confirm gcd equals one before normalizing the coefficient.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 | // value 0–9999 and modulus 2–9999. Returns the unique inverse in 0..modulus-1, or -1 when none exists. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(value, modulus) { let r = modulus; let nextR = value % modulus; let t = 0; let nextT = 1; while (nextR != 0) { let q = Math.floor(r / nextR); let tempR = r - q * nextR; let tempT = t - q * nextT; r = nextR; nextR = tempR; t = nextT; nextT = tempT; } if (r != 1) { return -1; } return ((t % modulus) + modulus) % modulus; } |
Source
No original paper has been verified for this entry. This source is a reference text or teaching reference, not an asserted original publication.
- The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd edition)
Donald E. Knuth (1997). Reference book.