Prove that $S$ is the number of integers congruent to $n$ mod $p$ between $a$ and $b$ inclusive where $a,b$ are integers

Question

This question has already been answered on another question although the answers are not correct. However, thanks to the comments, I was able to find a formula. Here it is:

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

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

So we have to prove how $S$ is this formula.

Thank you for your help!

Answer 1

The proof isn't as hard as it looks.

Let $kp+n$ , where $k,n,p$ are integers, the first integer in the interval $a,b$ congruent to ${n}\pmod p$ and $sp+n$, where $s$ is also integer,the last integer in the interval. There is $s-k+1$ integers in the interval $a,b$ congruent to ${n}\pmod p$.

Let's go on :

$(k-1)p+n\lt a\le kp+n\Rightarrow (k-1)p\lt a-n\le kp\Rightarrow k-1\lt \frac{a-n}{p}\le k$

$\Rightarrow -k+1\gt \frac{n-a}{p}\ge -k$

However $-k$ is an integer so $\lfloor \frac{n-a}{p}\rfloor = -k$

Let's continue with $b$ :

$sp+n\le b\lt (s+1)p+n\Rightarrow sp\le b-n\lt (s+1)p\Rightarrow s\le \frac{b-n}{p}\lt s+1$

However $s$ is an integer so $\lfloor \frac{b-n}{p}\rfloor = s$

But we know there is $s-k+1$ integers in the interval $a,b$ congruent to ${n}\pmod p$ so there is $\lfloor \frac{b-n}{p}\rfloor + \lfloor \frac{n-a}{p}\rfloor + 1$ integers in this interval.