0
$\begingroup$

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.

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

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, because your $f(10^k) = 10^k \bmod m$. $\endgroup$ – vonbrand Feb 5 '13 at 16:11
  • $\begingroup$ 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)$ $\endgroup$ – Amr Feb 5 '13 at 16:21
  • $\begingroup$ My point was only that the $f()$ isn't some hyper-mysterious function. $\endgroup$ – vonbrand Feb 5 '13 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.