Find the formula for calculating the number of integers congruent to n mod p between a and b inclusive where a,b are integers

Question

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.

Answer 1

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.

Answer 2

Given the range $[a,b]$ and the congruence $k \mod n$, then first, subtract $k$ from each of $a$ and $b$ to create a new range $[a-k,b-k]$.

This doesn't change the size of any of the congruence classes from using $n$.

We wish to find the size of each congruence classes for the residues $0,\dots,n-1$, and we start with $a-k \mod n$, this has $\lfloor\frac{b-k-(a-k)}{n}\rfloor+1=\lfloor\frac{b-a}{n}\rfloor+1$ elements in it.

The next residue we look at is $a-k+1 \mod n$, which has $\lfloor\frac{b-k-(a-k+1)}{n}\rfloor+1=\lfloor\frac{b-a-1}{n}\rfloor+1$ elements in it.

And continue through to residue $a-k+n-1 \mod n$, which has $\lfloor\frac{b-k-(a-k+n-1)}{n}\rfloor+1=\lfloor\frac{b-a-n+1}{n}\rfloor+1$ elements in it.

Answer 3

With the help of the answers you sent, I was able to find a form that seems rather simple to me. Then I'm not 100% sure it works all the time.

Let $S$ be the number of integers congruent to ${n}\pmod p$ in the interval $a$ inclusive and $b$ inclusive

$T=n-a+p\lfloor\frac{b-n}{p}\rfloor$

$S =\lfloor\frac{T}{p}\rfloor+1$

Answer 4

The number of multiples of $p$ in $[A,B]$ is easily shown to be $\Big\lfloor \frac{B}{p} \Big\rfloor-\Big\lceil \frac{A}{p} \Big\rceil+1$ (see for example Calculating the number of integers divisible by 8). Your problem is equivalent to finding number of multiples of $p$ in $[a-n,b-n]$, hence the answer is $$ \Bigg\lfloor \frac{b-n}{p} \Bigg\rfloor-\Bigg\lceil \frac{a-n}{p} \Bigg\rceil+1. $$ For $n=1$ there is also this special case How do I count all values that satisfy X mod N=1 in the range [A,B].

Alternatively we can write the above in terms of floor function only as $$ \Bigg\lfloor \frac{b-n}{p} \Bigg\rfloor-\Bigg\lfloor \frac{a-n-1}{p} \Bigg\rfloor. $$ (might be useful for programming where integer division is more common than division and ceiling)