Solved

A question about the number of divisors for perfect squares

Posted on 2010-11-09
11
912 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
  • 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
PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

 
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

Netscaler Common Configuration How To guides

If you use NetScaler you will want to see these guides. The NetScaler How To Guides show administrators how to get NetScaler up and configured by providing instructions for common scenarios and some not so common ones.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Samsung Smart View subtitles don't work 1 304
I have a question about a grounding mat i use at night to sleep better. 13 48
Detailed steps to upload 6 37
QQ problem 22 23
Phishing is at the top of most security top 10 efforts you should be pursuing in 2016 and beyond. If you don't have phishing incorporated into your Security Awareness Program yet, now is the time. Phishers, and the scams they use, are only going to …
Stuck in voice control mode on your Amazon Firestick?  Here is how to turn it off!!!
Saved searches can save you time by quickly referencing commonly searched terms on any topic. Whether you are looking for questions you can answer or hoping to learn about a specific issue, a saved search can help you get the most out of your time o…
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…

773 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