Well known, to those who know it. a) the difference between successive convergents of a continued fraction is +-1/(product of the denominators). So 13/74 - 42/239 = +-1 / 74*239. The numerator of the difference is 13*239 - 42*74 = +-1, providing a handy inverse mod 239 for 42. b) A little more mysteriously, look at the continued fractions for 42/239 and 74/239: 42/239 => [ 0; 5, 1, 2, 4, 3 ] 74/239 => [ 0; 3, 4, 2, 1, 5 ] This reflection pattern is true for general A & 1/A (mod M), but needs a little fudging with the optional last term being L or L-1,1 to get the +- sign right. a & b have the virtue of working whenever gcd(A,M)=1, even if M is a composite without a primitive root. 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 prefectly reasonable to just scan for each reciprocal by counting. And then the only required number theory is knowing the reciprocal exists. Another cute low-memory algorithm for modular reciprocal: Divide A into M repeatedly, using the remainder for Anew on the next cycle. Stop when you get to remainder 1. Accumulate the product of the negative quotients (mod M); that's the answer. This is more efficient than scanning, and simpler than maintaining the details of an extended GCD. (Extended GCD wins on efficiency though.) It works because M = A Quot + Rem, so Rem/A = - Quot (mod M). The product of the -Quots telescopes, giving 1/A = (-Q1)(-Q2)... (mod M). Rich ---- Quoting Bill Gosper <billgosper@gmail.com>:

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

Out[1131]= {0, 1/5, 1/6, 3/17, 13/74, 42/239}

In[1132]:= Mod[74*42, 239]

Out[1132]= 1 --rwg _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun