How many positive integers N are there such that the least common multiple of N and 1000 is 1000?

I did found the solution to this problem , but I did it by brute force. When I was tackling this problem, I didn't know what multiples where so I had to look it up. I think I had a blurred view of what multiples are. So, to help me, I found the definition: multiples are some number multiplied by an integer. For instance, the multiples of 4 are ...-8,0,4,8,12,16,20 and so on.

And the least common multiple of 4 and 5(as in an example to help clarify the problem) is 20 because

The multiples of 4: 4,8,12,16,20

The multiples of 5: 5,10,15,20,25

I know I probably wasted your time writing that stuff above, but it helps me because I get forget what it means to find multiples.

Now back to the problem. The problem asks to find all values n such that 1000 is divisible by n. So basically, I just listed them like this:

n: 1 2 ,4, 5, 8, 10, 20, 25, 40, 50,100,125,200,250,500,1000

1000/n has remainder 0? : There are 16 n's.

So again, I feel like there's a trick or method in the problem that I don't know in order to solve the problem. Do you know any other way,besides my brute force method, in solving this problem?

Thank you.

  • 1
    $\begingroup$ +1 for correctly going from "I don't know what multiple means" to "oh, it's just asking for the divisors of 1000". $\endgroup$ – Henning Makholm Jan 2 '14 at 4:12

Yes, we have another way to solve your question.

$N$ has to be a divisor of $1000$, and any divisor of $1000$ satisfies your condition. This means that what you want is the number of the divisors of $1000.$

By the way, we have a formula to count the number of the divisors of a number $a$.

It is known that the number of the divisors of a number $a$ such that $$a={p_1}^{a_1}\cdot {p_2}^{a_2}\cdots {p_k}^{a_k}$$ is $$(a_1+1)(a_2+1)\cdots (a_k+1)$$ where $p_1\lt p_2\lt\cdots p_k$ are prime numbers.

Noting that $1000=2^3\cdot 5^3,$ the answer for your question will be $$(3+1)\cdot (3+1)=16.$$

  • 2
    $\begingroup$ Nice solution mathlove..... $\endgroup$ – juantheron Jan 2 '14 at 4:18
  • $\begingroup$ @juantheron: Thanks a lot! $\endgroup$ – mathlove Jan 2 '14 at 4:41

$1000=2^35^3$, so for a divisor of 1000, you have 4 choices for the exponent of 2 and 4 choices for the exponent of 5, giving 4*4=16 divisors of 1000.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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