Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  Michael Hardy Sep 22 '11 at 22:35
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
    
Aha! I won't wait for other replies because this nails it. Thanks. –  gerry nixon Sep 22 '11 at 14:55
    
I don't seem to have enough points to upvote. Sorry! –  gerry nixon Sep 22 '11 at 14:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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