Find smallest $x$ such that $\gcd(a + x, b + x) = c$.

Question

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.

Answer 1

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