# If we know the GCD and LCM, how to find all unordered pairs?

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.

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*}

• How are you deciding the order to assign values to x, y, z, etc? – DERPYPENGUIN Sep 11 '16 at 7:42
• @DERPYPENGUIN If you mean whether to take $x = 2$ and $x' = 3$ or $x = 3$ and $x' = 2$, for example, then the answer is that both are possible and so you write both of them down, each gives you a different possible ordered pair $(a,b)$. – 6005 Sep 11 '16 at 7:44

Use the fact that the product of two numbers $a$ and $b$ is the same as the product of gcd$(a,b)$ and lcm$(a,b)$. So looking at alternative factorizations should lead to the answer.

Here we are given $12$ and $360$. Divide $360$ by some factor $k$ and multiply $12$ by that same $k$. That is $a=360/k, b=12k$ for various divisors $k$ of 360.

• Confusing... alternative factorizations of 12*360 can include "divide 12 by k and multiply 360 by k". – arivero May 10 '18 at 14:00
• Replace 12 by 12*k and to componsate for that diivide 360 by k: – P Vanchinathan May 11 '18 at 0:30
• Replace 12 by 12*k and to componsate for that divide 360 by k, choosing k carefully to get a whole number by division: So that $12\times 360 = (12\times k) \times \frac{360}{k}$ are two different factorizations. – P Vanchinathan May 11 '18 at 0:32

The problem is equivalent to finding all pairs $(a,b)$ with $gcd(a,b)=1$ and $lcm(a,b)=30$. Indeed, given such a pair, $(12a,12b)$ satisfies your requirements and conversely if you have a pair satisfying your conditions then $(\frac{a}{12},\frac{b}{12})$ satisfies the present condition. Write $30$ as $2\times 3\times 5$. Now the tuples $(a,b)$ satisfying the condition are in bijection with the partitions of $\{2,3,5\}$ into two parts. This is because $a,b$ cannot share a common factor, and their least common multiple has all the factors of $30$. So you decide which are the prime factors of $a$, and then $b$ has to take all the rest.

For example, take $a=2\times 5$, $b=3$, this gives the pair $(10,3)$, and to get one of the tuples in your question we multiply by $12$ and get $(120,36)$.

• (+1) I like reducing it down to partitions of $\{2,3,5\}$. – 6005 Sep 11 '16 at 7:35

If $\gcd(a,b) = 12$, then $12 \mid a$ and $12 \mid b$. Hence $\dfrac{a}{12}$ and $\dfrac{b}{12}$ are integers and $\gcd\left( \dfrac{a}{12}, \dfrac{b}{12} \right) = 1$ . Hence...

\begin{align} ab &= \gcd(a,b) \times \operatorname{lcm}(a,b) \\ ab &= 12 \times 360 \\ \dfrac{a}{12} \dfrac{b}{12} &= \dfrac{360}{12} \\ \dfrac{a}{12} \dfrac{b}{12} &= 30 \\ \end{align}

So, if you are looking for unordered pairs, $\left(\dfrac{a}{12}, \dfrac{b}{12} \right) \in \{ (1,30), (2,15), (3,10), (5,6)\}$

Note that the condition $\gcd\left( \dfrac{a}{12}, \dfrac{b}{12} \right) = 1$ has been satisfied in each case.

So, $(a,b) \in \{ (12,360), (24,180), (36,120), (60, 72)\}$

These problems are sometimes solved with Venn diagrams in middle school, and I think the method is helpful to work through and understand! For an example discussion, see:

Feldman, Z. (2014). Rethinking factors. Mathematics Teaching in the Middle School, 20(4), 230-236.

You can draw a Venn diagram with each circle representing one of $a$ and $b$, and place their shared prime factors in the overlapping region to correspond to their GCF. Once the remaining factors are placed in the other regions, you can multiply across all visible prime factors to get their LCM.

For this problem: The question now becomes, how can you place the remaining factors in $a$ and $b$ so that the product across all present numbers is $360$?

Already present is a $12$, so the remaining product needs to be $30$ since $12 \cdot 30 = 360$.

Now consider all factor pairs for $30$:

$$(1, 30); (2, 15); (3, 10); (5, 6); (6, 5); (10; 3); (15, 2); (30, 1)$$

For each such factor pair $(m, n)$ you can put $m$'s factors into $a$'s region, and $n$'s factors into $b$'s region. This gives a total of eight solutions (or four solutions, up to symmetry, which are exactly the ones that you listed in your question). As an example, if you take the second factor pair, $(2, 15)$, you could put $2$ into $a$'s region, and $15 = 3 \cdot 5$ into $b$'s region; this results in the following picture: Computing each region, we find $a = 2 \cdot 2 \cdot 2 \cdot 3 = 24$ and $b = 3 \cdot 5 \cdot 2 \cdot 2 \cdot 3 = 180$.

So in this case, we find that $(a, b) = (24, 180)$.

Going through the remaining cases for each of $30$'s factor pairs yields the other solutions.

I think you know {L.C.M }x {H.C.F.}= product of numbers [valid for 2 numbers only].

In your case {L.C.M }x {H.C.F.} =360*12 = a*b N

Note that none of a and b can be smaller than 12 since it is {H.C.F.}. Now only thing you have to do is to resolve 360*12 into two factors. You will find that these ways are (12*360), (24*180), (36*120) and (60*72).

The others will be excluded(such as 48*90) because one of them is not divisible by 12 which is {H.C.F.}.

Hope you get my message, if any problem regarding solution leave comment

• @Jaideepkhare delete this comment – Vidyanshu Mishra Mar 22 '18 at 9:45