11
$\begingroup$

How many positive integers less than 1000 have an odd number of positive integer divisors?

Well I know that the number has to be composite because a prime number has 2 divisors, which are 1 and itself. I don't have any other thoughts to solve this problem other than brute force, which will take a long time and is not accurate. Any help? Thanks.

$\endgroup$
  • 1
    $\begingroup$ For a composite number, every positive integer divisor must have a partner to multiply by to get your original number. Except for.... $\endgroup$ – turkeyhundt Jan 21 '15 at 4:40
  • 2
    $\begingroup$ Hint: divisors usually occur in pairs - $ab=c$. When do they not occur in pairs? try the first 20 numbers. $\endgroup$ – Joffan Jan 21 '15 at 4:41
  • 12
    $\begingroup$ oooh all perfect squares? $\endgroup$ – suomynonA Jan 21 '15 at 4:42
  • 1
    $\begingroup$ $\overset{o,o}\smile$ try it out $\endgroup$ – Joffan Jan 21 '15 at 4:43
  • 2
    $\begingroup$ Not quite composite, $1$ qualifies. $\endgroup$ – André Nicolas Jan 21 '15 at 4:58
5
$\begingroup$

They are the squares so the answer is $\lfloor \sqrt{1000} \rfloor = 31$. To see this notice that the number of divisors of a number is the product of each exponent plus one, i.e. $n = \prod{p_i^{e_i}}$ and $\tau(n) = \prod{(e_i+1)}$. If $\tau(n)$ is odd then all $e_i$ are even which means $n$ is a square.

$\endgroup$
6
$\begingroup$

The answer is number of perfect squares less than equal to the given number, as we know perfect squares have odd number of divisors. Number of divisors of any number can be calculated by decomposing it into prime factors. If $n=p_1^{e_1}p_2^{e_2}\ldots p_n^{e_n}$ then number of divisors is $(e_1+1)(e_2+1)\ldots(e_n+1)$. Let $n = a^2$, then if $d$ is a factor then so is $\frac{n}{d}$. Thus we see that the factors are in pairs except for a because $\frac{n}{a} = a$. Thus total number of factors is $2x+1$ where $x$ is number of factors less than $a$. So odd number of factors.

$\endgroup$
4
$\begingroup$

If we allow division by 1 and by the number it self then all the prime numbers have exactly two divisors so we can discount all the prime numbers.

Now consider the composite numbers that are not a perfect square say 6. This is 1x6 or 2x3 so we can discount all these too.

Finally we consider the composite numbers that are perfect squares say 4. This is 1x4 or 2x2. It is therefore divisible by an odd number of factors. This is true for all perfect squares and since the square root of 1000 is just over 31.6 there will be 31 natural numbers less than 1000 that have an odd number of factors

$1^2 = 1$, $2^2 = 4$, $3^2 = 9$, ... $31^2 = 961$

$\endgroup$

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.