A JavaScript Extended Euclidian Algorithm Implementation


Nick Appleton


October 22, 2023

Below is an implementation of the Extended Euclidian Algorithm in JavaScript. It uses Michael Mclaughlin’s bignumber.js library to permit large inputs. Given two distinct and positive quantities \(A\) and \(B\), their greatest common divisor, the coefficients of Bézout’s identity and the positive Modular Multiplicative Inverse of \(A\) will be output (when they exist).

The quantities for \(A\) and \(B\) can be given in decimal or hexadecimal (by using a “0x” prefix). If the output base is specified as “Auto”, the output values will be in hexadecimal if either input is.

No interesting story for this post. It is just a calculator. I wrote it because I periodically want to find the modulo multiplicative inverse of some number and most other online calculators I have found do not handle numbers greater than 32-bit. If you found it useful, star the bignumber.js repository - it made writing this tool an absolute breeze.