How do I count all values that satisfy X mod N=1 in the range [A,B]

Question

I want to count how many values of x in range [A,B] give remainder of 1 when divided by N. Is there any formula I can apply?

Answer 1

You want to find $X$ from $[A,B]$ such that $$X\equiv1\quad(\text{mod }N)$$ which is the same as $$X-1\equiv0\quad(\text{mod }N)$$ Now $X-1$ is from $[A{-}1,B{-}1]$, so you want to find the number of multiples of $N$ in that interval.

It's not hard to see there are $\left\lfloor\frac KN\right\rfloor+1$ multiples of $N$ in $[0,K]$ and $\left\lceil\frac KN\right\rceil$ in $[0,K)$. The interval $[A-1,B-1]$ can be written as $[0,B-1]$ without $[0,A-1)$, so the answer is $$\left\lfloor\frac{B-1}N\right\rfloor-\left\lceil\frac{A-1}N\right\rceil+1$$

The symbols $\lfloor\cdot\rfloor$ and $\lceil\cdot\rceil$ denote the floor and ceiling functions respectively. Also note that I assume $A-1$ and $B-1$ to be positive, but the method still works if you consider $\left\lfloor\frac KN\right\rfloor+1$ and $\left\lceil\frac KN\right\rceil$ to mean the signed number of multiples of $N$.

Answer 2

I'll use this notation: $\lceil x\rceil$ is the least integer that is not lesser than $x$, and $\lfloor x\rfloor$ is the greatest integer that is not greater than $x$.
For example, $\lceil 5.4 \rceil=6$ and $\lfloor 5.4 \rfloor=5$, and $\lceil 5\rceil=\lfloor 5\rfloor=5$.
It is also advsisable to take two negative examples: $\lceil -5.4\rceil=-5$, $\lfloor -5.4 \rfloor=-6$, $\lceil -5\rceil=\lfloor -5\rfloor=-5$

The first of these values is $Na+1$ for some integer $a$. Then, $Na+1\geq A$ and $Na+1-N<A$. That is, $$A\leq Na+1 <A+N$$ Divide by $N$ to get: $$\frac AN\leq a+\frac1N<\frac AN+1$$ that is, $$\frac{A-1}N\leq a<\frac{A-1}N+1$$ In other words, $$a=\left\lceil\frac{A-1}N\right\rceil$$

Now, the last of the values that you want to count is $Nb+1$ for some integer $b$. Similarly, $$B-N<Nb+1\leq B$$ or $$\frac {B-1}N-1<b\leq \frac{B-1}N$$ or equivalently, $$b=\left\lfloor\frac{B-1}N\right\rfloor$$

Then, there are $$\left\lfloor\frac{B-1}N\right\rfloor-\left\lceil\frac{A-1}N\right\rceil+1$$ of these values.