Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Do you know the basic modular arithmetic ? –  Amr Feb 5 '13 at 8:34
    
Basic yes, but having trouble here –  user54089 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 –  user54089 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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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