TITLE: Find smallest $x$ such that $\gcd(a + x, b + x) = c$.
QUESTION [2 upvotes]: I need to find the smallest $x$ such that
$$\gcd(a + x, b + x) = c$$
where $a, b, c, x$ are positive integers and $a \le b$. I was able to rewrite it as
$$\gcd(a + x, b - a) = c$$
This shows that $c$ must be a divisor of $b - a$ to have a solution. Assuming that a solution exists, I am not able to proceed.

REPLY [2 votes]: Given positive integers $a,b,c$, with $a<b$, we wish to determine the least positive integer $x$ for which $\gcd(a+x,b+x)=c$.
For each $x \in \mathbb N$, write $g_x=\gcd(a+x,b+x)=\gcd(a+x,b-a)$. Thus, a necessary condition for the gcd condition to hold for some $x$ is that $c \mid (b-a)$.
We assume $c \mid (b-a)$, and write $b-a=mc$, where $m \in \mathbb N$. So now we want the least positive integer $x$ for which $a+x=nc$, with $n \in \mathbb N$ and $\gcd(n,m)=1$. This amounts to finding the least positive integer of the form $nc-a$ with $\gcd(n,m)=1$. There isn't much more you can simplify this in general.
$\bullet$ If $c>a$, then choose $n=1$, so the least $x=c-a$.
$\bullet$ If $c=a$, which means $a \mid b$ and $m=\frac{b}{a}-1$, choose $n$ to be the smallest positive integer $>1$ and coprime to $m$. This is the smallest prime $p$ such that $p \nmid m$. The least $x=(n-1)a=(p-1)a$.
$\bullet$ If $c<a$, there is no significant simplification of the general statement. We look for the smallest $n>\left\lfloor\frac{a}{c}\right\rfloor$ and coprime to $m$.
{"set_name": "stack_exchange", "score": 2, "question_id": 3750285}