If two numbers, a and b, are relatively prime (which means they have no common factors) there exists x and y such that ax + by = 1.

This is one of the steps involved in using a theorem called the 'Chinese Remainder Theorem'. Using some pseudocode I found at Wikipedia, and converting it to Javascript, I've created a function which finds the x and y for any two numbers. If x and y do not exist, it returns 0,1 or 1,0. However you can test for yourself that a*x + b*y = 1 otherwise.

Try it out here.

• David Wees's blog
• Add new comment