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$ – Michael Hardy Sep 22 '11 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)$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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