Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

A question about the number of divisors for perfect squares

Posted on 2010-11-09
11
Medium Priority
?
958 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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
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 332 total points
ID: 34094121
yes
0
 
LVL 27

Assisted Solution

by:d-glitch
d-glitch earned 336 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 332 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 1000 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

New Tabletop Appliances Blow Competitors Away!

WatchGuard’s new T15, T35 and T55 tabletop UTMs provide the highest-performing security inspection in their class, allowing users at small offices, home offices and distributed enterprises to experience blazing-fast Internet speeds without sacrificing enterprise-grade security.

Question has a verified solution.

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

An introduction to the wonderful sport of Scam Baiting.  Learn how to help fight scammers by beating them at their own game. This great pass time helps the world, while providing an endless source of entertainment. Enjoy!
In this article, I’ll show how research, determination, and use of modern technology helped me solve a DNA mystery.
The Bounty Board allows you to request an article or video on any technical topic, or fulfill a bounty request to earn points. Watch this video to learn how to use the Bounty Board to get the content you want, earn points, and browse submitted bount…
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.
Suggested Courses

972 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