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 ?
-
1$\begingroup$ Do you know the Unique Factorization Theorem, lapin? Do you know how to express the gcd of two numbers in terms of their factorizations into primes? $\endgroup$– Gerry MyersonJul 29, 2015 at 7:32
-
$\begingroup$ nope not a homework problem, just wondering, please suggest edits to the title. and @GerryMyerson any number can be factorised into primes or is a prime itself, but i am not able to see the hint you are trying to give. $\endgroup$– lapinJul 29, 2015 at 7:39
-
$\begingroup$ The hint is, think about how to express the gcd of two numbers in terms of the factorizations of the two numbers. If $r=2^73^45^8$ and $s=2^93^27^5$, can you tell me what $\gcd(r,s)$ is? $\endgroup$– Gerry MyersonJul 29, 2015 at 9:02
-
$\begingroup$ Obviously $x$ is a multiple of $c$. So, for which $k$ do you have $gcd(a, kc) > c$? $\endgroup$– user251257Jul 29, 2015 at 9:03
-
$\begingroup$ Are you still here, lapin? $\endgroup$– Gerry MyersonJul 30, 2015 at 12:51
1 Answer
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$.