3
$\begingroup$

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

Thank you,

  • 0
    Is it possible you've mixed it up with something else? Where did you hear about this formula?2011-04-25
  • 1
    @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.2011-04-25

1 Answers 1

5

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.

  • 0
    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.2011-04-25
  • 0
    Does anyone know a reference for Voronoi's paper? It does not appear to be in Dickson's History.2011-04-25
  • 0
    @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.2011-04-25