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.
Best Answer
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.$$