0
$\begingroup$

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$?

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

2 Answers 2

0
$\begingroup$

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)\}$

$\endgroup$
4
  • $\begingroup$ 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$ ? $\endgroup$
    – 766F6964
    Oct 25, 2018 at 17:17
  • $\begingroup$ 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$. $\endgroup$
    – kcborys
    Oct 25, 2018 at 17:38
  • $\begingroup$ 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$ ? $\endgroup$
    – 766F6964
    Oct 25, 2018 at 19:06
  • $\begingroup$ Off the top of my head it should be $\sum_{b=n+1}^{L}(\lfloor\frac{a-n}{b}\rfloor+1)$ $\endgroup$
    – kcborys
    Oct 25, 2018 at 20:05
0
$\begingroup$

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}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .