3
$\begingroup$

How many such number-pairs are there for which the greatest common divisor is 7 and the least common multiple is 16940?

2 Answers 2

6

Let the two numbers be $7a$ and $7b$.

Note that $16940=7\cdot 2^2\cdot 5\cdot 11^2$.

We make a pair $(a,b)$ with gcd $1$ and lcm $2^2\cdot 5\cdot 11^2$ as follows. We "give" $2^2$ to one of $a$ and $b$, and $2^0$ to the other. We give $5^1$ to one of $a$ and $b$, and $5^0$ to the other. Finally, we give $11^2$ to one of $a$ and $b$, and $11^0$ to the other. There are $2^3$ choices, and therefore $2^3$ ordered pairs such that $\gcd(a,b)=1$ and $\text{lcm}(a,b)=2^2\cdot 5\cdot 11^2$. If we want unordered pairs, divide by $2$.

Here we used implicitly the Unique Factorization Theorem: Every positive integer can be expressed in an essentially unique way as a product of primes.

There was nothing really special about $7$ and $16940$: any problem of this shape can be solved in basically the same way.

  • 0
    Kudos for emphasizing the role played by uniqueness of factorization.2012-12-11
0

Theorem. The number of unordered pairs $(x,y)$ such that $\gcd(x,y) = G$ and $\operatorname{lcm}(x,y) = L$ is $2^{n-1}$ where $n$ is the number of distinct prime factors of $\frac LG$.

Proof

If $\gcd(x,y) = G$, and $\operatorname{lcm}(x,y) = L$, then \begin{array}{ll} 1. & u = \dfrac xG \; \text{and} \; v = \dfrac yG \; \text{are integers} \\ 2. & \gcd(u,v) = 1 \\ 3. & uv = \dfrac LG \end{array}

It should be pretty easy to see that first two properties are true. The third property is a consequence of the fact that $xy = \gcd(x,y) \operatorname{lcm}(x,y) = GL$:

\begin{align} L &= \dfrac{xy}{G} \\ &= \dfrac{(Gu)(Gv)}{G} \\ &= Guv\\ \end{align}

It follows that the number of unordered pairs $(x,y)$ such that $\gcd(x,y) = G$ and $\operatorname{lcm}(x,y) = L$ is equal to the number of unordered pairs (u,v) such that $\gcd(u,v) = 1$ and $uv = \dfrac LG$.

Suppose that $\displaystyle \frac LG = \prod_{i=1}^n p_i^{a_i}$ where the $p_i$ are distinct prime numbers. For $i=1..n$, let $P_i = p_i^{a_i}$, so that $\displaystyle \frac LG = \prod_{i=1}^n P_i$. We see that finding a pair of relatively prime $u$ and $v$ such that $\dfrac LG = uv$ corresponds to expressing the set $\{ P_1, P_2, \dots, P_n\}$ as the union of a pair of disjoint subsets (where the empty set must correspond to the number 1). There are $2^{n-1}$ such subsets.

EXAMPLE

For this problem, $G = 7$ and $L = 16940\;$, $\dfrac LG = 2420 = 2^2 \times 5 \times 11^2 = 4 \times 5 \times 121$.

Note that $2420 = 2^2 \times 5 \times 11^2 = 4 \times 5 \times 121$. So there are $2^{3-1} = 4$ unordered pairs.

In order to enumerate those pairs, we seek all $u, v$ such that $gcd(u,v) = 1$ and $uv = 2420$. We find

\begin{array}{c|cc|cc} \text{Partition} & u & v & x & y\\ \hline \{\},\{4,5,121\} & 1 & 2420 & 7 & 14640\\ \{4\}, \{5,121\} & 4 & 605 & 28 & 4235\\ \{5\}, \{4,121\} & 5 & 484 & 35 & 3388\\ \{121\}, \{4,5\} & 121 & 20 & 847 & 140\\ \hline \end{array}