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!
[Math] GCD and LCM of three numbers
algorithmsnumber theory
Related Solutions
As others say, one way to do it is using the identity $\gcd(a,b,c)=\gcd(a,(\gcd(b,c))$. This identity is true since the "gcd" is the maximal element of the intersection of the sets of factors of the inputs. For example, taking $\gcd(6,10)$, the set of factors of $6$ is {$6, 3, 2, 1$}, the set of factors of $10$ is {$10, 5, 2, 1$}, their intersection is {$2, 1$}, and the maximal element is $2$. The identity follows since intersections of sets are commutative and associative.
However, it's also possible to extend Stein's algorithm to handle more than two inputs. Wikipedia gives 5 steps to Stein's algorithm, and we can change them to the following to compute the gcd of a set $S$ of numbers:
- If anything in $S$ is zero, remove it.
- If everything in $S$ is even, divide everything in $S$ by 2, and then multiply the final answer by 2 at the end.
- If some numbers in $S$ are even and some are odd, divide all the even numbers by 2.
- If every number in $S$ is odd, then choose an arbitrary element of $S$ and call it $k$. Replace every other element, say $n$, with $|n-k|/2$.
- Repeat steps 1–4 until there is only one remaining element in $S$. After you remember to multiply in the twos that you got from step 2, that's your gcd!
Lemma. Let $G$ be a group, written multiplicatively, and let $H$ and $K$ be two subgroups. If $HK = \{hk\mid h\in H, k\in K\}$, then $$|HK||H\cap K| = |H||K|$$in the sense of cardinalities.
Proof. Consider the map $H\times K\to HK$ given by $(h,k)\mapsto hk$. I claim that the map is exactly $|H\cap K|$ to $1$. Indeed, if $hk=h'k'$, then $h'^{-1}h = k'k^{-1}\in H\cap K$, so there exists $u\in H\cap K$, namely $u=h'^{-1}h$ such that $h=h'u$ and $k=u^{-1}k'$. Thus, $(h,k) = (h'u,u^{-1}k')$ maps to the same thing as $(h',k')$. Conversely, given $v\in H\cap K$, we have that $(h'v,v^{-1}k')\in H\times K$ maps to the same thing as $(h',k')$.
Thus, each element of $HK$ corresponds to precisely $|H\cap K|$ elements of $H\times K$. Thus, $|HK||H\cap K| = |H\times K| = |H||K|$, as claimed. $\Box$
Let $a$ and $b$ be integers, and consider $\mathbb{Z}/\langle ab\rangle$. This is a group with $|ab|$ elements. This group contains subgroups generated by $\gcd(a,b)$, by $a$, by $b$, and by $\mathrm{lcm}(a,b)$. $\gcd(a,b)$ generates the largest subgroup containing both $a$ and $b$; i.e., $\langle \gcd(a,b)\rangle = \langle a\rangle + \langle b\rangle$; while $\mathrm{lcm}(a,b)$ generates the smallest subgroup contained in both $\langle a\rangle$ and $\langle b\rangle$, i.e., $\langle \mathrm{lcm}(a,b)\rangle = \langle a\rangle\cap\langle b\rangle$. By the Lemma (with addition, since we are working in an additive group), we have: $$|\langle a\rangle+\langle b\rangle| |\langle a\rangle\cap\langle b\rangle| = |\langle a\rangle||\langle b\rangle|$$ Now, the subgroup generated by $\gcd(a,b)$ has $\frac{|ab|}{\gcd(a,b)}$ elements; the subgroup generated by $\mathrm{lcm}(a,b)$ has $\frac{|ab|}{\mathrm{lcm}(a,b)}$ elements; that generated by $a$ has $\frac{|ab|}{|a|}$ elements, that generated by $b$ has $\frac{|ab|}{|b|}$ elements. Plugging all of that in it becomes $$\gcd(a,b)\mathrm{lcm}(a,b) = |a||b|$$ which yields the desired equality. $\Box$
Best 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<r$ this is $6(r-q-1) +3+3 = 6(r-q)$ where the first term counts the triples where all three are different and the other two terms are for triples where two of them are equal (either two equal to $p^q$ or two equal to $p^r$). If $r<q$ the number is $0$.
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)$