Suppose $a_1,\ldots, a_n$ are arbitrary integers. Is there some simple way to describe the set $S$ of all possible values of $\gcd(a_1x_1,\ldots,a_nx_n)$ as $x_1,\ldots, x_n$ runs through all n-tuples of relatively prime integers? (By "relatively prime" I mean here that no prime divides all the $x_i$.) It is easy to see that elements of $S$ are divisible by $\text{gcd}(a_1,\ldots,a_n)$, and that every element of $S$ is a divisor of $\operatorname{lcm}(a_1,\ldots,a_n)$. But it is not clear to me (and may not be true) that every multiple of $\gcd(a_1,\ldots,a_n)$ that is also a divisor of $\operatorname{lcm}(a_1,\ldots,a_n)$ is a member of $S$.

  • $\begingroup$ You shouldn't write \text{gcd} within TeX; just write \gcd. In some contexts the effects are different; for example, when an operatorname is followed by an expression, spacing it made to follow standard conventions. $\endgroup$ Sep 22, 2011 at 22:35

1 Answer 1


Yes, you can get exactly the numbers that are both multiples of $\gcd(a_1,\dotsc,a_n)$ and divisors of $\text{lcm}(a_1,\dotsc,a_n)$.

For each prime $p$, the exponent of $p$ in $\gcd(a_1,\dotsc,a_n)$ is the least exponent $k_\min$ of $p$ among the $a_1,\dotsc,a_n$, and the exponent of $p$ in $\text{lcm}(a_1,\dotsc,a_n)$ is the greatest such exponent $k_\max$. The exponent of $p$ in $\gcd(a_1x_1,\dotsc,a_nx_n)$ is at least $k_\min$, so $\gcd(a_1,\dotsc,a_n)|\gcd(a_1x_1,\dotsc,a_nx_n)$. The exponent of $p$ in $\gcd(a_1x_1,\dotsc,a_nx_n)$ is at most $k_\max$, since otherwise each of the $x_1,\dotsc,x_n$ would have to contain at least one factor $p$; so $\gcd(a_1x_1,\dotsc,a_nx_n)\mid\text{lcm}(a_1,\dotsc,a_n)$.

To obtain a given exponent $k$ of $p$ with $k_\min\le k\le k_\max$, only those $x_i$ have to contain factors of $p$ for which $a_i$ doesn't already have $k$ factors of $p$. Since there is at least one $a_i$ that has $k_\max$ factors of $p$ (with $k_\max\ge k$), you can obtain any such $k$ without making all $x_1,\dotsc,x_n$ divisible by $p$. By doing this for all $p$, you can obtain coprime $x_1,\dotsc,x_n$ for any value of $\gcd(a_1x_1,\dotsc,a_nx_n)$ with $\gcd(a_1,\dotsc,a_n)\mid\gcd(a_1x_1,\dotsc,a_nx_n)\mid\text{lcm}(a_1,\dotsc,a_n)$.

  • $\begingroup$ Aha! I won't wait for other replies because this nails it. Thanks. $\endgroup$ Sep 22, 2011 at 14:55
  • $\begingroup$ I don't seem to have enough points to upvote. Sorry! $\endgroup$ Sep 22, 2011 at 14:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .