Solved

A question about the number of divisors for perfect squares

Posted on 2010-11-09
11
905 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
 
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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 

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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Webcam indoor recommendation 21 109
iPhone 7 64GB 5 103
where can I purchase a ribbon for a Brother Fax-575 Fax Machine? 8 30
fountain pens in usa 6 41
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 …
Whether you believe the “gig economy,” as it has been dubbed, is the next big economic paradigm shift (https://www.theguardian.com/commentisfree/2015/jul/26/will-we-get-by-gig-economy) or an overstated trend (http://www.wsj.com/articles/proof-of-a-g…
Articles on a wide range of technology and professional topics are available on Experts Exchange. These resources are written by members, for members, and can be written about any topic you feel passionate about. Learn how to best write an article t…
Where to go on the main page to find the job listings. How to apply to a job that you are interested in from the list that is featured on our Careers page.

863 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

Need Help in Real-Time?

Connect with top rated Experts

22 Experts available now in Live!

Get 1:1 Help Now