Given two positive integers G and L, could you tell me how many solutions of (x, y, z) there are, satisfying that gcd(x, y, z) = G and lcm(x, y, z) = L? gcd(x, y, z) means the greatest common divisor of x, y and z, while lcm(x, y, z) means the least common multiple of x, y and z. Also, (1,2,3) and (1,3,2) are two different solutions, while (1,2*,2) and (1,2,2*) are the same solution.(* is just a symbol) Are there any ideas about this? Thanks in advance!
Answer
Let's write $\displaystyle x = \prod_{i=1}^n p_i^{a_i}$, $\displaystyle y = \prod_{i=1}^n p_i^{b_i}$, $\displaystyle z = \prod_{i=1}^n p_i^{c_i}$, where the $p_i$ are the primes that are factors of at least one of $x, y, z$.
Then $\displaystyle \gcd(x,y,z) = \prod_{i=1}^n p_i^{\min(a_i,b_i,c_i)}$ and $\displaystyle \mathrm{lcm}(x,y,z) = \prod_{i=1}^n p_i^{\max(a_i,b_i,c_i)}$.
Now, suppose that $n=1$ for simplicity. Then the number of $(x,y,z)$ with gcd $p^q$ and lcm $p^r$ is just the number of triples $(a,b,c)$ with minimum $q$ and maximum $r$. If $r=q$ this is just $1$, while if $q So define $f(s) = 0$ if $s<0$, $f(0) = 1$, and $f(s) = 6s$ if $s>0$. Now let $\displaystyle G = \prod_{i=1}^n p_i^{q_i}$ and $\displaystyle L = \prod_{i=1}^n p_i^{r_i}$. Then one can show that the number of triples with gcd $G$ and lcm $L$ is $\displaystyle \prod_{i=1}^n f(r_i-q_i)$
No comments:
Post a Comment