Re: [math-fun] build table of multiplicative inverses without dying of embarrassment

rwg wrote:

...

HUH? The inverse of 42 mod 239: In[1131]:= Convergents[42/239] [etc.]

rcs wrote:

I think Warren's comment was more about code complexity, and not wanting to wade through more number theory than necessary. For small P, <10K or so, it's perfectly reasonable to just scan for each reciprocal by counting. And then the only required number theory is knowing the reciprocal exists.

The algorithm Warren describes is for computing *all* the reciprocals. It's much more efficient for that purpose than applying the continued fraction algorithm (equivalently, Euclid's algorithm) individually for each number coprime to N. -- g