# What is the Voronoi's formula to calculate the inverse modulo m $ax \equiv 1 \pmod{m}$

I searched a bit using google but I found nothing :( ! Any information would be greatly appreciated.

Thank you,

-
Is it possible you've mixed it up with something else? Where did you hear about this formula? –  Zev Chonoles Apr 25 '11 at 5:20
@Zev Chonoles: It was from my lecture notes. My teacher said there were 3 methods to calculate the inverse, first one is extended Euclidean, second one is $a^{\phi(m) - 1 } \pmod{m}$, and third one is Voronoi. –  Chan Apr 25 '11 at 5:22

## 1 Answer

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.

-
It is definitely helpful ;), great thanks! By the way, in my opinion, Euclidean's algorithm is the fastest one among these three because doing multiplication with large number is always very time consuming. –  Chan Apr 25 '11 at 5:51
Does anyone know a reference for Voronoi's paper? It does not appear to be in Dickson's History. –  Bill Dubuque Apr 25 '11 at 15:42
@Bill: I don't know his paper, I just happened to have seen it in Tattersall's Elementary Number Theory in Nine Chapters a while back. –  mixedmath Apr 25 '11 at 16:29