# $\gcd(a_1x_1,\ldots,a_nx_n)$ as $x_1,\ldots, x_n$ runs through all $n$-tuples of relatively prime integers

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

• 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. Sep 22, 2011 at 22:35

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