# How to evaluate an infinite sum involving remainders

I've been trying to evaluate the sum

$$\sum_{k=0}^\infty \frac{m^k\bmod n}{m^k}$$

where $m$ and $n$ are positive integers greater than $1$ and $a\bmod b$ is the remainder when $a$ is divided by $b$. This came up in a combinatorics problem I was doing, and I know how to evaluate it given $m$ and $n$ (the numerators repeat, so it ends up just being geometric), but I'm not sure how to evaluate it generally.

Any ideas?

The numerators must repeat because only finitely many possible remainders exist. Suppose the repeating part starts after the first $K$ terms, so you have \begin{align} & \sum_{k=1}^K \frac{m^k\bmod n}{m^k} + \sum_{k=K+1}^\infty \frac{m^k\bmod n}{m^k} \\[10pt] = {} & \sum_{k=1}^K + \sum_{k=K+1}^{K+R} + \sum_{k=K+R+1}^{K+2R} + \sum_{k=K+2R+1}^{K+3R} + \cdots \\ & \text{where $R$ is the length of the repeating part} \\[10pt] = {} & \sum_{k=1}^K + \left(\sum_{k=K+1}^{K+R}\right)\left( 1 + \frac 1 {m^R} + \frac 1 {m^{2R}} + \frac 1 {m^{3R}} + \cdots \right) \\[10pt] = {} & \sum_{k=1}^K + \left(\sum_{k=K+1}^{K+R}\right)\left( \frac 1 {1- \dfrac 1 {m^R}} \right) \end{align}
• Thanks! Is it possible to find $K$ and $R$ in closed form (I'm pretty sure we can assume $R=\phi(m)$ - is that correct)? – Carl Schildkraut Feb 2 '17 at 23:35
• @CarlSchildkraut : Look at a few conrete examples. What if $m=3$ and $n=6\text{?}$ Then $R=1. \qquad$ – Michael Hardy Feb 3 '17 at 2:21
• @MichaelHardy So is there a way to find $K$ and $R$ in closed form that you know of? I know that for many cases (such as when $n|m$, for example) $R=1$, and for some other cases (like when $m$ is a primitive root mod $n$), $R=\phi(n)$. So, since the period divides $\phi(n)$, I think we can take $R$ to be $\phi(n)$ (am I right?). However, is there a nice formula for $K$? – Carl Schildkraut Feb 3 '17 at 4:49