If we know that $\gcd(a,b)=12$ and $\operatorname{lcm}(a,b)=360$, how can we find all unordered pairs $a,b$?
The answer in the back of the book I got this from gives $(12,360), (24,180), (36,120), (60,72)$ as the solutions.
[Math] If we know the GCD and LCM, how to find all unordered pairs
elementary-number-theory
Best Answer
When solving such questions, it is best to think in terms of prime factorizations instead of integers. So we start by prime-factorizing $360$ and $12$: \begin{align*} 360 &= 2^3 \cdot 3^2 \cdot 5^1 \\ 12 &= 2^2 \cdot 3^1 \end{align*} $a$ and $b$ must divide $360$, since $360$ is the LCM, so they cannot have any prime factors other than $2, 3, 5$. So \begin{align*} a &= 2^x 3^y 5^z \\ b &= 2^{x'} 3^{y'} 5^{z'} \end{align*} Now from LCM and GCD being $360$ and $12$, we get \begin{align*} \text{max}(x,x') = 3, \text{min}(x,x') = 2 \implies \{x,x'\} = \{2,3\} \\ \text{max}(y,y') = 2, \text{min}(x,x') = 1 \implies \{y,y'\} = \{1,2\} \\ \text{max}(z,z') = 1, \text{min}(z,z') = 0 \implies \{z,z'\} = \{0,1\} \\ \end{align*} So to write out all possibilities, we just have to assign $2$ and $3$ to $x$ and $x'$, $1$ and $2$ to $y$ and $y'$, and $0$ and $1$ to $z$ and $z'$. Since we only want unordered possibilities, we can start out taking $z = 0$, $z' = 1$. So all unordered possibilities for $(a,b)$ are, as you wrote: \begin{align*} (2^2 3^1, 2^3 3^2 5^1) &= (12, 360) \\ (2^3 3^1, 2^2 3^2 5^1) &= (24, 180) \\ (2^2 3^2, 2^3 3^1 5^1) &= (36, 120) \\ (2^3 3^2, 2^2 3^1 5^1) &= (72, 60). \\ \end{align*}