Concatenated number mod m

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.

• Do you know the basic modular arithmetic ? – Amr Feb 5 '13 at 8:34
• Basic yes, but having trouble here – The 29th Saltshaker Feb 5 '13 at 8:45
• Just to clarify, you are speaking of digits. So your $a, b, c, \dots$ are decimal digits? – Andreas Caranti Feb 5 '13 at 8:56
• integers yes. I assumed I could just add the values all mod m but am unsure – The 29th Saltshaker Feb 5 '13 at 9:01
• Just to understand, one case could be $a = 12$, $b = 345$, and then the concatenation would be $12345$? – Andreas Caranti Feb 5 '13 at 9:11

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$.
Define a function $f:\mathbb{Z}\rightarrow\{0,1,..,m-1\}$ such that $f$ sends $x$ to $x\mod\,m$.
$(abc...k)\mod\,m=(f(10^{10})f(a)+f(10^{9})f(b)+...+f(10)j+k)\mod\,m$
There are good ways to evaluate $f(10^i)$ efficiently.
• Yes, because your $f(10^k) = 10^k \bmod m$. – vonbrand Feb 5 '13 at 16:11
• Sure, but there are more efficent ways for example, if $\gcd(m,10)=1$, then $10^i\equiv 10^{i\,mod\,\phi(m)}\,(mod\,m)$ – Amr Feb 5 '13 at 16:21
• My point was only that the $f()$ isn't some hyper-mysterious function. – vonbrand Feb 5 '13 at 18:14