# Proof about divisors

1. Dec 28, 2011

### cragar

1. The problem statement, all variables and given/known data
Let n be a positive integer. Prove that n has an odd number of divisors if and only if n is a perfect square.
3. The attempt at a solution
Lets 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.

2. Dec 28, 2011

### Dick

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?

3. Dec 28, 2011

### 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.

4. Dec 28, 2011

### Dick

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

5. Dec 29, 2011

### 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

6. Dec 29, 2011

### Dick

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.

7. Dec 29, 2011

### 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.

8. Dec 29, 2011

### cragar

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