I searched a bit using google but I found nothing :( ! Any information would be greatly appreciated.
Thank you,
I searched a bit using google but I found nothing :( ! Any information would be greatly appreciated.
Thank you,
Voronoi's formula is named after Georgi Voronoi. It goes a bit like this:
If we have $ax \equiv 1 \pmod m$ and we have that $\gcd(a,m) = 1$ (as otherwise we know that there is no solution), then the solution is given by $ x \equiv \left(3 - 2a + 6 \sum\limits_{k=1}^{a-1} \left\lfloor \frac{mk}{a} \right\rfloor^2 \right) \pmod m$
You can quickly see that this is impractical in many cases, but for large m and small a, it works quickly. I should also note that in general, Euclid's algorithm is much faster. I hope this helps.