Given a positive integer $n$, consider the number $y=10^{n}+10^{n-1}+$$...+ 10^{1}+10^{0}$. I need to find the remainder when $y$ is divided by a natural number $x$.
e.g.
$111111$ $\%$ $2123$ = $715$
$1111$ $\%$ $7$ = $5$
How do I approach this problem?
Update: $n$ can be as large as $10^{20}$
You can find the order of 10 (mod x). To do this, you just find the least k such that $10^k=1$ (mod x), $k>0$. Then $10^{r+k}=10^r$, and you know the remainder of $10^n$, $10^{n-1}$ etc so you can just add them up.
Update: If you have such large modulus relative to n, then using order will not help. $ord_{2123}(10)=192$, so unless $n>192$ you won't save any time using order (but with such a small n compared to the modulus, it shouldn't take very much time anyways). However, if you want to find $\frac{10^{21}-1}{9}$ mod 7, then it will save you a lot of time: $10=3$ (mod 7), & $3^1=3, 3^2=2, 3^3=6,3^4=4,3^5=5,3^6=1$, so $ord_7(3)=6$. This means that if $n=3$ (mod 6), $10^n=6$ (mod 7). The powers of 10 between 0 and 17 sum to 63, $10^{18}=1, 10^{19}=3, 10^{20}=2$ so desire quantity is 69 (mod 7)=6.
With large modulus that are products of small primes, you can use the Chinese remainder theorem, but this wouldn't work with 2123=11*193.