4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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}

$\endgroup$
  • 1
    $\begingroup$ Beautiful use of everything here! $\endgroup$ – Simply Beautiful Art Feb 2 '17 at 23:33
  • $\begingroup$ 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)? $\endgroup$ – Carl Schildkraut Feb 2 '17 at 23:35
  • $\begingroup$ @CarlSchildkraut : Look at a few conrete examples. What if $m=3$ and $n=6\text{?}$ Then $R=1. \qquad$ $\endgroup$ – Michael Hardy Feb 3 '17 at 2:21
  • $\begingroup$ @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$? $\endgroup$ – Carl Schildkraut Feb 3 '17 at 4:49
  • $\begingroup$ @CarlSchildkraut : I'm not sure right now. Maybe I'll be back. $\endgroup$ – Michael Hardy Feb 3 '17 at 17:31

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.