$a,b,n \in \mathbb Z$. Find the smallest value of $n$ such that $b\mod n = a$

Question

Let $a,b,n \in \mathbb Z$. Find the smallest value of $n$ such that $b\mod n = a$ where $a,b$ are known values and $b > a$.

What's the most efficient way to solve such a problem? The naive approach would be choose values of $n$ and increment up until the smallest $n$ is found.

How would it work for $a=4, b=6$? – Arthur Oct 17 '17 at 20:05 — Arthur, Oct 17 '17 at 20:05
@Arthur That case doesn't work I suppose. – WHY Oct 17 '17 at 20:14 — WHY, Oct 17 '17 at 20:14
@mvw $\frac{b}{n}$ gives remainder $a$ – WHY Oct 17 '17 at 20:18 — WHY, Oct 17 '17 at 20:18

Peter · Answer 1 · 2017-10-17T20:35:22.073

0

"$b\ mod\ n\ =a$" means $\ b\equiv a\mod n\ $ , so we have $\ n|b-a\ $, thus the smallest positive value of $\ n\ $ is just the smallest prime factor of $\ b-a\ $, if we assume $n>1$. If $\ b-a=1\ $, the only solution is $n=1$, if we allow it.

In the case $n$ must be greater than $a$ :

If there is a divisor of $\ b-a\ $ which is greater than $a$, then the smallest of the divisors greater than $a$ is the optimal solution, but in this case, we do not always have a solution at all. For example $b=19$ , $a=16$.

edited Oct 17 '17 at 20:35

answered Oct 17 '17 at 20:15

Peter

84,454

Thanks for your answer, Peter. As an example, let $b=277,a=5$. Then $b-a=272$ with smallest prime factor of 2, but 2 doesn't satisfy the equation. $8$ is the smallest value of $n$ in this case. Am I misunderstanding your answer? – WHY Oct 17 '17 at 20:26
@WHY I edited the answer – Peter Oct 17 '17 at 20:38

$a,b,n \in \mathbb Z$. Find the smallest value of $n$ such that $b\mod n = a$

1 Answers1