Welcome to MathOverflow

Question

1

$P(n)$ and $D(n)$ are two large integers.
Suppose $R(n) = \frac{P(n)}{D(n)}$ is an integer.
I want to compute $R(n)\bmod m$.
$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.
For example, how to compute $S(x,k) = \sum_{k=0}^{n}x^k\mod m$ for a large $n$?
$S(x,n) = \frac{x^{n+1}-1}{x-1}$
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?
Thanks in advance

Philippe

edited Oct 18 at 6:12

asked Oct 17 at 16:51

Philippe_Chessa
23●3

There is no solution on this level of generality: if you know just $P(n)\bmod m$ and $D(n)\bmod m$, this does not uniquely determine $R(n)\bmod m$. In fact, $P(n)/D(n)=mP(n)/mD(n)$, hence you can as well assume without loss of generality that $P(n)=D(n)=0\pmod m$, in which case the input data give you no information at all. – Emil Jeřábek Oct 17 at 16:59

1

Well, in your specific example, it does not hurt if $n$ is large, since the sequence of $x^k\pmod{m}$ (after a preperiod) becomes periodic. – Peter Mueller Oct 17 at 17:14

Thanks for pinpointing the typo. – Philippe_Chessa Oct 18 at 6:13

Igor Rivin · Accepted Answer · 2012-10-17 19:59:32Z UTC

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".

Computing the ratio of two large integers modulo m

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.