How often is $k, 2k, 3k...$ modulo $n$ less than or equal to $b$ before it hits $-1$? Let $n>0$ and $k\leq n$ 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$. Up to and including the moment it hits $-1$, how many integers will it visit in the range $1, \ldots, b$?
To be clear, if $-1$ itself is in the range $1, ..., b$, then that counts as a "hit", e.g. when $n=5, k=1, b=4$, the number of hits is $4$.
 A: I wasn't able to solve the problem completely, but I did find an interesting identity satisfied by the sequence.

Let $n>0$ and $k\leq n$ be coprime and let $1\leq b<n$. We'll write $g(n, b, k)$ for the number referred to in the question. By convention, we will take $g(1, 1, 1)=1$.

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:

*

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

*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$.
Overall, we have the following identities.

Theorem. When $b\equiv 0\mod k$:
$$g(n, b, k)=n_k^{-1}\frac bk$$
When $b\not\equiv 0\mod k$ and $b\not\equiv -1\mod k$:
$$g(n, b, k) = n^{-1}_k\lfloor \frac b k\rfloor + g(k, b, -n)$$
And when $b\equiv-1\mod k$:
$$g(n, b, k) = n^{-1}_k\lfloor \frac b k\rfloor + g(k, b, -n) - 1$$
where $n_k^{-1}$ is the inverse of $n$ modulo $k$, reduced to the range $1, ..., k$, and the arguments of $g$  on the right hand sides are taken modulo $k$, also 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.
These identities actually give us an efficient recursive algorithm for computing $g$. For example, here is the computation of $g(2001, 124, 55)$. The column inv represents $n_k^{-1}$, and value is the value added onto $g$ in the right hand side of the relevant identity at each stage. To obtain $g(2001, 124, 55)$, just add up the value column.
+------+-----+----+-----+---------+-------+
|  n   |  b  | k  | inv | b mod k | value |
+------+-----+----+-----+---------+-------+
| 2001 | 124 | 55 |  21 |    14   |   42  |
|  55  |  14 | 34 |  13 |    14   |   0   |
|  34  |  14 | 13 |  5  |    1    |   5   |
|  13  |  1  | 5  |  2  |    1    |   0   |
|  5   |  1  | 2  |  1  |    -1   |   -1  |
|  2   |  1  | 1  |  1  |    0    |   1   |
+------+-----+----+-----+---------+-------+

You will notice that the first column is basically a down-shifted version of the third. In fact, the third column can basically be generated according to the rule:
$$k_{i+1}\equiv -k_{i-1} \mod k_i$$
With $k_1$ and $k_2$ initialized to some pair of coprime numbers. Notice that if we got rid of the minus sign, the sequence $k_i$ would just be the sequence of remainders generated by the Euclidean algorithm.
