Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Thank you,

share|improve this question
    
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
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. –  Chan Apr 25 '11 at 5:22

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.