What is the inverse function of gcd?

Question

Let $a,x,c \in\mathbb{Z}$.
If $\gcd(a,x)=c$ where $a, c$ are constants and $x$ is a variable,
then what values can $x$ take and how to find those values ?

Answer 1

Note that $\gcd(a,x)=c \iff \gcd(a/c,y)=1$ where $y=x/c$. The latter equation has $\phi(a/c)$ solutions with $1\le y \le a/c$, where $\phi$ denotes the Euler phi function. This means the original equation has $\phi(a/c)$ "basic" solutions $x_0$ with $1\le x _0\le a$. All other solutions have the form $x=x_0+ka$ where $x_0$ is a basic solution.

This leaves the question of actually finding the basic solutions. If you know the prime factorization of $a/c$, say $a/c=p_1^{e_1}\cdots p_k^{e_k}$, it's easy to list the integers relatively prime to each $p_i^{e_i}$; you then find the values of $y$ by using the Chinese Remainder Theorem. Then multiply each $y$ by $c$ to find the values of $x$.