- #1
cragar
- 2,552
- 3
Homework Statement
Let n be a positive integer. Prove that n has an odd number of divisors if and only if n is a perfect square.
The Attempt at a Solution
Let's factor n into its prime factorization
[itex] n= {P_1}^{x_1}{P_2}^{x_2}...{P_j}^{x_r} [/itex]
where P's are prime numbers and x's are natural numbers.
Now in order to get all the divisors from the prime factors we need to take all the possible combinations of the prime factors, from 0 up to [itex] x_r [/itex]
So the number of divisors will be [itex] D=(x_1+1)(x_2+1)...(x_r+1) [/itex]
But if n is a perfect square then the number of divisors would be
[itex] D=(2x_1+1)(2x_2+1)...(2x_r+1) [/itex] and an odd number times an odd number is an odd number therefore if n is a perfect square then it will have an odd number of divisors.
And this is the only way to guarantee that it will have an odd number of divisors.