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 ?


closed as off-topic by user223391, Aloizio Macedo, user91500, Davide Giraudo, drhab Jul 30 '15 at 10:06

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Community, Aloizio Macedo, user91500, Davide Giraudo, drhab
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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 Myerson Jul 29 '15 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$ – lapin Jul 29 '15 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 Myerson Jul 29 '15 at 9:02
  • $\begingroup$ Obviously $x$ is a multiple of $c$. So, for which $k$ do you have $gcd(a, kc) > c$? $\endgroup$ – user251257 Jul 29 '15 at 9:03
  • $\begingroup$ Are you still here, lapin? $\endgroup$ – Gerry Myerson Jul 30 '15 at 12:51

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


Not the answer you're looking for? Browse other questions tagged or ask your own question.