How to "undo" mpz_invert()

[Saverio Trioni]

As the word suggests, making the "inverse" of an integer modulo p has 
two properties:

1) it is an inverse, so the inverse of the inverse should be the 
original number.

2) it is modulo p, so it cannod tell between x and x+p.

So what?
Well, the inverse modulo 13 of 2 is 7 (2*7=14) and the inverse of 7 is 
2. But the inverse of 15 is 7 too. You cannot retrieve 15.
 From the manual:
"If the inverse exists, the return value is non-zero and rop will
satisfy 0 <= rop < op2."
You can retrieve the original number if it was already less than the 
"modulo". In this case you have just to re-invert your result!

Bye.


> 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.
> 
> Thanks,
> James
> 
>