Solved

A question about the number of divisors for perfect squares

Posted on 2010-11-09
11
923 Views
Last Modified: 2012-05-10
Hey,

       I'm trying to prove the number of distinct positive divisors of a positive integer n is odd if and only if n is a perfect square.

I have an idea on how to go about this... but its not quite as robust as I'd like it to be, and there are a lot of holes in it, this is what I have so far:

Since n is a square, you would be able to find at least 2 factors for it, and then you would be able to take at least 2 factors of the original factors of n, and repeat this process till you run out of integers to factor.  Since you are factoring each divisor into 2 parts, you would always have an even number of divisors, and then n^2 divides n^2, so you have even number of divisors + 1 which would equal an odd divisor.

The hole I'm running into is... when I have 36, I take 6 & 6, and I take the factors of 6, I get 2 & 3, and I get 2, 3, 6 & 36... which is not odd... so... that's where my theory kinda fails.

Do I need to set some restrictions? Or am I going about this the wrong way?

Appreciate any help on this.
0
Comment
Question by:errang
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 2
  • 2
  • +2
11 Comments
 
LVL 2

Expert Comment

by:Hossy
ID: 34093475
You forgot "1"

factors of 36 are 1,2,3,6,36 -- which is odd
0
 
LVL 27

Expert Comment

by:d-glitch
ID: 34093624
This was answered correctly and completely by andyalder in your previous question about proofs:

"For a non-square integer every divisor d of n is paired with divisor n/d of n and s0(n) is then even; for a square integer one divisor (namely ) is not paired with a distinct divisor and s0(n) is then odd."
0
 
LVL 27

Expert Comment

by:d-glitch
ID: 34093643
Small correction/typo

"For a non-square integer every divisor d of n is paired with divisor n/d of n and s0(n) is then even; for a square integer one divisor [namely SQRT(n)] is not paired with a distinct divisor and s0(n) is then odd."
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 27

Expert Comment

by:d-glitch
ID: 34093820
If you are trying to make this into a proof:

    For any positive integer N.

    Look at all the integers m = 1 up to and including the sqrt(N)

    If m is a divisor of N, then so it N/m.
    This is the definition of a divisor.  

    m and N/m are distinct unless   m = sqrt(N) = N/m.
0
 
LVL 27

Expert Comment

by:d-glitch
ID: 34093827
>>    If m is a divisor of N, then so is N/m.
        This is the definition of a divisor.  
0
 

Author Comment

by:errang
ID: 34094071
Hm... so the basic argument is, every number has a certain pair of integers that form the given number, and each pair is unique, because something like 1 x 2 is not equal to 2 x 3.

So each square has a certain number of "pairs of integers" that would divide the given square, but the square would also divide itself, so we have 2n + 1, which is odd.

right?
0
 
LVL 2

Assisted Solution

by:Hossy
Hossy earned 83 total points
ID: 34094121
yes
0
 
LVL 27

Assisted Solution

by:d-glitch
d-glitch earned 84 total points
ID: 34094224
Divisors are always paired:   m  and  N/m

The divisors are distinct unless     m = sqrt(N) = N/m
This only way you can have an unpaired divisor is if N is a perfect square.
0
 
LVL 22

Assisted Solution

by:NovaDenizen
NovaDenizen earned 83 total points
ID: 34094740
You're coming at it from the wrong direction.  Think of the number N in terms of its prime factorization.  N = p1^a * p2^b * p3^c .  How many distinct divisors does this N have, in terms of a, b, and c?
0
 
LVL 18

Accepted Solution

by:
deighton earned 250 total points
ID: 34094810
Take a positive integer n

n has a number of factors, this number can be said to be s

the set of factors is  F={f1, f2, f3, .....fs}

for each member of the set, n / fn is a member of  F

for each f in F, then either n/f is a separate member of F or n/f = f
for each f in F n/f has its own discrete value

therefore pairs of values where n/f not equal to f can always be removed until we are left with the empty set or a set containing a value such that n/f = f

in the first case we have removed 2i factors, where i is the number of removals - i is an integer so there are an even number of factors.

In the second case we have n/f = f, so n = f*f where f is a whole number, so n is a square number and there are 2i+1 factors which is an odd number

0
 

Author Closing Comment

by:errang
ID: 34095502
Thanks
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

CSS is a visual language used to classify objects and define rules about how they should be displayed. CSS skills aren’t restricted to developers anymore, there is a big benefit to having a basic understanding of the language, regardless of your occ…
EE introduced a new rating method known as Level, which displays in your avatar as LVL. The new Level is a numeric ranking that is based on your Points. This article discusses the rationale behind the new method and provides the mathematical formula…
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

710 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question