Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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.

share|cite|improve this answer
Kudos for emphasizing the role played by uniqueness of factorization. – Bill Dubuque Dec 11 '12 at 6:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.