If I know the values of a mod m, b mod m, ..., k mod m, what is the concatenated number abcdefghijk mod m? In this example I stop at k but can be arbitrarily long, just know the value of each digit mod m.
Answer
Well, even if your numbers are not single digits, but are $a_{1}, \dots, a_{t}$, where $a_{i}$ has $d_{i}$ decimal digits, then your concatenation $a_{1} a_{2} \dots a_{t}$ is
\begin{equation}
a_{t} + 10^{d_{t}}(a_{t-1} + 10^{d_{t-1}} (a_{t-2} + \dots ))),
\end{equation}
so to compute this modulo $m$ you will need to compute some powers of $10$ modulo $m$.
No comments:
Post a Comment