most recent 30 from http://mathoverflow.net 2013-05-22T05:52:23Z http://mathoverflow.net/feeds/question/109927 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109927/computing-the-ratio-of-two-large-integers-modulo-m Philippe_Chessa 2012-10-17T16:51:23Z 2012-10-18T06:12:21Z

<p>$P(n)$ and $D(n)$ are two large integers.<br> Suppose $R(n) = \frac{P(n)}{D(n)}$ is an integer.<br> I want to compute $R(n)\bmod m$.<br> $P(n)$ and $D(n)$ are too large to be computed but $P(n)\bmod m$ and $D(n)\bmod m$ can easily be computed.<br> For example, how to compute $S(x,k) = \sum_{k=0}^{n}x^k\mod m$ for a large $n$?<br> $S(x,n) = \frac{x^{n+1}-1}{x-1}$<br> I know how to do if $x-1$ and $m$ are coprime, using the modular inverse of $x-1$, but what if they are not coprime?<br> Thanks in advance </p> <p>Philippe</p>

http://mathoverflow.net/questions/109927/computing-the-ratio-of-two-large-integers-modulo-m/109942#109942 Igor Rivin 2012-10-17T19:59:32Z 2012-10-17T19:59:32Z

<p>As pointed out in the comments, the problem cannot be solved in the generality you state it in, but the magic words are "chinese remainder theorem". If you have an estimate on the sizes of $P$ and $Q$ you can compute them modulo $m_1, \dotsc, m_k, $ where the $m_i$ are pairwise relatively prime (or just prime), and the product of the $m_i$ is bigger than $\max P, Q.$ From this you can reconstitute $P/Q,$ but if you do the "reconstitution step" mod $m$ you will get what you want. For more details, just google for "Chinese remainder algorithm".</p>