How to "undo" mpz_invert()

James Buchanan james at
Wed Dec 1 16:19:22 CET 2004

Once mpz_invert has been applied to find an inverse modulo, is there 
some way to "undo" it?

Say I have p which I want to be the inverse modulo, if it exists (assume 
it does).  And I have x and n (n is the number for which gcd(x, n) = 1 
is true.)

Knowing only p and n, how to find x?  Apparently px + sn = 1, if p 
exists.  I have no idea what s is supposed to be or how to find it.  I'm 
not a mathematician, as you can see... ;-) If that's true, then I can 
find x:

px + sn = 1
px +sn - sn = 1 - sn
px = 1 - sn
px/p = (1-sn)/p
x = (1-sn)/p

But what is s and where does it come from/how do I get it with only p and n?

It's been a long time since I studied algebra.


More information about the gmp-discuss mailing list