# greatest common divisor is 7 and the least common multiple is 16940

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

-

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.

-
Kudos for emphasizing the role played by uniqueness of factorization. –  Bill Dubuque Dec 11 '12 at 6:48