# How often is $k, 2k, 3k…$ modulo $n$ less than $b$ before it hits $-1$?

Let $n$ and $k$ be coprime, and let $1\leq b \leq n$. The sequence $k, 2k ,3k, \ldots$ reduced modulo $n$ to the range $1, \ldots, n$, will eventually run through every integer in the range $1, \ldots, n$, since $k\perp n$. In particular it will eventually hit $-1$. Before it hits $-1$, how many integers will it visit in the range $1, \ldots, b$?

• Technically, $-1$ is not in the range $1..n$ – Joffan Jul 27 '16 at 16:10
• If the inverse of $n-b$ in $\mathbb Z_n$ is $k$, then the sequence will hit $-1$ at the $k$-th index. – Elaqqad Jul 27 '16 at 16:11
• @Joffan $-1$ modulo $n$, of course. $n-1$, if you prefer. – Jack M Jul 27 '16 at 16:14
• Also the answer depends on the sizes of $b, k, n$ relative to each other, as this can determine whether a multiple of $k$ steps over the region $1..b-1$ or whether successive multiples can find target values before wrapping the modulus. – Joffan Jul 27 '16 at 16:16
• And there is no general expression for the inverse of $n-b$ modulu $n$. it can be anything. Finding the inverse $k=(n-b)^{-1}$ requires computing the inverse in $\mathbb{Z}_n$ which is equivalent to running the sequence $k,2k,....$ until it its $-1$ – Elaqqad Jul 27 '16 at 16:23

I wasn't able to solve the problem completely, but I did find an interesting identity satisfied by the sequence.

Let $n$ and $k$ be coprime and let $1\leq b<n$. We'll write $g(n, b, k)$ for the number referred to in the question.

Before I get to that, I'll need a formula for the following quantity:

We'll write $f(b, k, i)$ for the number of integers congruent to $i$ modulo $k$ in the range $1, ..., b$.

It's not hard to get a formula for $f$. The congruence classes modulo $k$ of the integers $1, 2, 3, ...$ form a periodic sequence of period $k$. The number of periods in the range $1, ..., b$ is exactly $\lfloor \frac b k \rfloor$, and each one will contain exactly one integer congruent to $i$. There will then generally be a partial period, which may or may not contain an extra integer congruent to $i$, depending on the value of $i$. Specifically:

If $b$ is a multiple of $k$, then there is no extra partial period, and we have $$f(b, k, i)=\frac b k$$ Otherwise, let $b_k$ and $i_k$ be the reductions modulo $k$ of $b$ and $i$ to the range $1, ..., k$. Then if $b_k\geq i_k$, there is an extra integer congruent to $i$ in the partial period, and $$f(b, k, i)=\lfloor\frac b k\rfloor+1$$ And if $b_k<i_k$ $$f(b, k, i)=\lfloor\frac b k\rfloor$$

Now let's look at $g$. The sequence $(ik)_i$ will begin by running through all of the multiples of $k$ in the range $1, ..., n$. Assuming it doesn't pass through $n-1$, it will then wrap around and end up at the value $-n$, reduced modulo $k$ to the range $1, ..., k$. It will then run through all values congruent to $-n$ modulo $k$, before wrapping around once more to the value $-2n$. It will wrap around some number $r$ times, finally reaching the value $-rn$, then run through all values congruent to $-rn$, the last of which will be $n-1$. From this it follows that the value of $r$ is $n^{-1} - 1$ modulo $k$, where $n^{-1}$ denotes the inverse of $n$ modulo $k$, and the value is taken in the range $1, ..., k$.

This description of the sequence $(ik)_i$ implies that

$$g(n, b, k) = \sum_{i=0}^r f(b, k, -in)$$

When $k$ divides $b$, this reduces to

$$g(n, b, k) = (r + 1)\frac b k = n^{-1}_k \frac b k$$

Where $n^{-1}_k$ denotes the inverse of $n$ modulo $k$, taken in the range $1, ... k$. When $k$ does not divide $b$, however, we obtain

$$g(n, b, k) = n^{-1}_k \lfloor\frac b k\rfloor + N$$

Where $N$ is the number of integers $i$ in the range $0, ..., r$ such that $(-in)_k\leq b_k$. But hang on... by construction, $r+1$ is the smallest value such that $-n(r+1)\equiv -1\mod k$. So $N$ is almost $g(k, b, -n)$. There are two problems:

1. We're running the sequence $(-n)i$ starting at $i=0$, but in the definition of $g$, we start at $i=1$. This is not such a big problem since for $i=0$, $-ni\equiv k$ modulo $k$, which will be less than or equal to $b$ precisely when $b_k=k$.
2. The sequence stops short of reaching $-1$ modulo $k$, whereas in the definition of $g$, if $k-1$ is less than or equal to $b_k$, it would be included in our count.

If $b_k=k$, these two effects cancel each other out, and $N=g(k, b, -n)$. The problem is when $b_k = k-1$. In that case, $N=g(k, b, -n) - 1$.

When $b$ is not a multiple of $k$, and $b\not\equiv -1\mod k$: $$g(n, b, k) = n^{-1}_k\lfloor \frac b k\rfloor + g(k, b, -n)$$ when $b$ is not a multiple of $k$, and $b\equiv-1\mod k$: $$g(n, b, k) = n^{-1}_k\lfloor \frac b k\rfloor + g(k, b, -n) - 1$$ where the arguments of $g$ on the right hand side are taken modulo $k$ in the range $1, ..., k$.

I've tested this identity by computer. It's possible there are some minor errors in the proof, but I'm confident the result is correct.

• The question and this answer remind me of Eisenstein's proof of quadratic reciprocity. I don't know whether this is a coincidence or there's a real connection. en.wikipedia.org/wiki/… – Ethan Bolker Oct 29 '16 at 15:04