Proof about divisors

  • Thread starter cragar
  • Start date
  • #1
2,544
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


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

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,260
619

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


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

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
2,544
3
Im not sure exactly what you mean. when you say n=pq
for n to be a perfect square p=q, then [itex] n=p^2 [/itex]
Are you saying because its a perfect square I could group all the divisors together because it will have 2 of each.
 
  • #4
Dick
Science Advisor
Homework Helper
26,260
619
Im not sure exactly what you mean. when you say n=pq
for n to be a perfect square p=q, then [itex] n=p^2 [/itex]
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.
 
  • #5
2,544
3
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
Dick
Science Advisor
Homework Helper
26,260
619
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.
 
  • #7
Curious3141
Homework Helper
2,843
87
Let d be any divisor or n (prime or composite) such that [itex]1 \leq d \leq n[/itex] (that covers all divisors). It's as trivial as observing that if [itex]d|n[/itex], then [itex]\frac{n}{d}|n[/itex]. Hence the divisors can be listed in pairs [itex](d,\frac{n}{d})[/itex] 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 [itex]s^2 = n[/itex] so [itex]\frac{n}{s} = s[/itex]. There will therefore be exactly one "repeated" pair [itex](s,s)[/itex]. 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
2,544
3
Ok thanks for your posts everyone, I think I understand now.
 

Related Threads on Proof about divisors

  • Last Post
Replies
8
Views
1K
Replies
6
Views
2K
Replies
7
Views
2K
  • Last Post
Replies
2
Views
782
Replies
2
Views
1K
  • Last Post
Replies
4
Views
10K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
1
Views
995
  • Last Post
Replies
12
Views
3K
  • Last Post
Replies
1
Views
4K
Top