# Given $n$, find $a$ and $b$ such that ${a \mod b = n}$

Let's assume I am given a positive integer $$n$$, as well as an upper limit $$L$$.

How could one find all, or at least one, possible solutions for $$a$$ and $$b$$ such that $${a \mod b = n}$$ where as $$0 <=a, b <= L$$?

• When you say $a\mod b = n$, do you mean $a \equiv n \pmod b$? Oct 25, 2018 at 15:29
• I think that by $a\mod b$ he means the rest from division $a$ by $b$. This is common notation for that Oct 25, 2018 at 15:35
• @SamStreeter I meant that $n$ is the remainder of the division $a$ by $b$ just as Jakobian said. Oct 25, 2018 at 17:04
• @766F6964 What I have written means the same thing and is more standard notation in modular arithmetic. Oct 25, 2018 at 17:37

Assuming you mean $$n$$ to be the remainder of $$\frac{a}{b}$$, you could iterate over all $$n< b \leq L$$ and compute all $$a = n+ kb$$ for $$k\geq 0$$ and $$a\leq L$$.

Edit: here is a worked example. Suppose $$n=2$$ and $$L=5$$.

$$a \mod b$$ will be smaller than $$b$$, so we must start with $$b>2$$.

For $$b=3$$, we can try: \begin{align}a = 2 + 0\cdot 3 = 2 \\a = 2+1\cdot 3 = 5\end{align} and these are the only values of $$a\leq 5$$.

For $$b=4$$, $$a=2+0 cdot 4 = 2$$ is our only result and for $$b=5$$, $$a=2+0\cdot 5 = 2$$ is our only result.

This gives us solution set $$\{(2,3), (5,3), (2,4), (2,5)\}$$

• Thanks for your reply. Do you mind adding an example with small numbers, so that it is easier to follow your approach? Also, would this work too if $n=L$ ? Oct 25, 2018 at 17:17
• I added an example @766F6964 . $n=L$ would not work because $b\leq L$ and the remainder of $\frac{a}{b}$ is less than $b$. Oct 25, 2018 at 17:38
• Thanks a lot. With your example is was able to understand everything. One more thing: Is there a formula to calculate how many combinations exist for $a$ and $b$ under $L$ without the need to calculate all of them until $b=L$ ? Oct 25, 2018 at 19:06
• Off the top of my head it should be $\sum_{b=n+1}^{L}(\lfloor\frac{a-n}{b}\rfloor+1)$ Oct 25, 2018 at 20:05

For each $$b \in \mathbb{N}$$, we have $$\{a \in \mathbb{Z} : a \equiv n \pmod b\} = \{n+kb : k \in \mathbb{Z}\}$$. Then note that $$0 \leq n+kb \leq L$$ iff $$-\frac{n}{b} \leq k \leq \frac{L-n}{b}$$.