As you read in the title, the goal is to find a formula that gives a number of integers congruent to n mod p between a and b.
For example, if $(a,b)=(0,100)$, there are $51$ congruent integers $0$ mod $2$ between $0$ and $100$ inclusive.
If $(a,b)=(32,456)$, there are $106$ congruent integers $2$ mod $4$ between $32$ and $456$ inclusive.
Is there already a formula? And if so, what is that formula?
With a little research, we can find for integers at 0,1 mod 2, for integers at 0,1,2 mod 3, etc… But it must certainly have a pattern to find a formula.
Best Answer
I'm going to write a formula $H(a, b, n, p)$ for the number of items congruent to $n$, modulo $p$, in the interval $a \le k < b$. If you want to apply it to get the answer to the question you've asked, you need to evaluate $H(a, b+1, n, p)$ to get the sum to be inclusive on both ends. I'm assuming here that $b \ge a$.
Furthermore, I'm going to use the computer-scientist's convention that $$ (x, y) \mapsto x \bmod y $$ is a function defined on pairs of integers, where $y$ must be positive, and that the value of this function is the number in the range $0, 1, \ldots, y-1$ that is congruent to $x$, modulo $y$.
Observe that for any $a, b, n, p$, and $s$ we have $$ H(a, b, n, p) = H(a-s, b-s, n-s, p), $$ so picking $s = a$, we can simply compute our answer by computing $$ H(a-a, b-a, n-a, p) = H(0, b-a, n-a, p). $$ Next observe that if we adjust $n-a$ by some multiple of $p$, the answer remains the same, so if we say $n' = (n-a) \bmod p$, then we only need to compute $$ H(0, b-a, n', p) $$ and now $n'$ is a number between $0$ and $p-1$. To simplify a little more, let's write $b' = b-a$, so we seek to compute $$ H(0, b', n', p). $$ In any span of $p$ sequential integers, there's ONE that's congruent to $n'$, so let's look at how many such spans there are, starting at $0$, and stopping while still less than $b'$. That's exactly $$ U(b', p) = \lfloor \frac{b'}{p} \rfloor. $$ What's left over is a sequence of fewer than $p$ numbers from $pU(b', p)$ to $b'$, in which there might or might not be a number congruent to $n'$. Taken $\bmod p$, this sequence looks like $$ 0, 1, 2, \ldots, (b'-1) \bmod p $$ and we need to add one to our tally exactly if one of those numbers is $n'$. In short, we get $$ H(0, b', n', p) = U(b', p) + \begin{cases} 1 & n' < (b' \bmod p) \\ 0 & n' \ge (b' \bmod p) \end{cases}. $$
Replacing this with the original values, we get $$ H(a, b, n, p) = \lfloor \frac{b-a}{p} \rfloor + \begin{cases} 1 & (n \bmod p) < ((b-a) \bmod p) \\ 0 & (n \bmod p) \ge ((b-a) \bmod p) \end{cases}. $$
It's possible that there's some nice way to simplify this a little bit, but...I think I've said enough.