Proving n Has Odd # Divisors If Perfect Square

[cragar]

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
$n= {P_1}^{x_1}{P_2}^{x_2}...{P_j}^{x_r}$
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 $x_r$
So the number of divisors will be $D=(x_1+1)(x_2+1)...(x_r+1)$
But if n is a perfect square then the number of divisors would be
$D=(2x_1+1)(2x_2+1)...(2x_r+1)$ 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.

 

[Dick]

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
$n= {P_1}^{x_1}{P_2}^{x_2}...{P_j}^{x_r}$
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 $x_r$
So the number of divisors will be $D=(x_1+1)(x_2+1)...(x_r+1)$
But if n is a perfect square then the number of divisors would be
$D=(2x_1+1)(2x_2+1)...(2x_r+1)$ 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.

You can do it that way, but you can also do it without using prime factorization. Group divisors into pairs where you pair p and q into {p,q} when pq=n. Do you see how that would work?

 

[cragar]

Im not sure exactly what you mean. when you say n=pq
for n to be a perfect square p=q, then $n=p^2$
Are you saying because its a perfect square I could group all the divisors together because it will have 2 of each.

 

[Dick]

Im not sure exactly what you mean. when you say n=pq
for n to be a perfect square p=q, then $n=p^2$
Are you saying because its a perfect square I could group all the divisors together because it will have 2 of each.

I'm saying the divisors occur in groups of two. Unless it's a perfect square. Then you have one group of one.

 

[cragar]

so because it is a perfect square, the divisors are doubled up, so were just repeating instead of having 2 distinct groups. because n=q*q

 

[Dick]

so because it is a perfect square, the divisors are doubled up, so were just repeating instead of having 2 distinct groups. because n=q*q

Actually the divisors are doubled up when the number is not a square. Take 12. The groups are {1,12}, {2,6} and {3,4}. Since the divisors are all in groups of 2, the number of divisors is even. Now take 64, a perfect square. The groups are {1,64}, {2,32}, {4,16} and {8}. 8*8=64 so 8 is in a group all by itself. Hence the number of divisors is odd.

 

[Curious3141]

Let d be any divisor or n (prime or composite) such that $1 \leq d \leq n$ (that covers all divisors). It's as trivial as observing that if $d|n$, then $\frac{n}{d}|n$. Hence the divisors can be listed in pairs $(d,\frac{n}{d})$ giving an even number of divisors (if one listed them all without being concerned about repeats). Where n is a perfect square, there will be exactly one divisor s such that $s^2 = n$ so $\frac{n}{s} = s$. There will therefore be exactly one "repeated" pair $(s,s)$. If only unique divisors are now listed, s will occur only once, whereas there will be an even number of the other divisors. Hence the total number of divisors will be odd iff n is a square.

 

[cragar]

Ok thanks for your posts everyone, I think I understand now.