Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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|improve this answer
    
Kudos for emphasizing the role played by uniqueness of factorization. –  Bill Dubuque Dec 11 '12 at 6:48

Your Answer

 
discard

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.