1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof about divisors

  1. Dec 28, 2011 #1
    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
    [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.
     
  2. jcsd
  3. Dec 28, 2011 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  4. Dec 28, 2011 #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.
     
  5. Dec 28, 2011 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I'm saying the divisors occur in groups of two. Unless it's a perfect square. Then you have one group of one.
     
  6. Dec 29, 2011 #5
    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
     
  7. Dec 29, 2011 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  8. Dec 29, 2011 #7

    Curious3141

    User Avatar
    Homework Helper

    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.
     
  9. Dec 29, 2011 #8
    Ok thanks for your posts everyone, I think I understand now.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof about divisors
  1. Proof of zero divisor (Replies: 4)

Loading...