Solved

A question about the number of divisors for perfect squares

Posted on 2010-11-09
11
899 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
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 

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

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Surprisingly, there is a lot to Gym battles, and I thought it would be helpful to share knowledge about all the ins and outs of this feature!
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…
Notifications on Experts Exchange help you keep track of your activity and updates in one place. Watch this video to learn how to use them on the site to quickly access the content that matters to you.
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…

747 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

11 Experts available now in Live!

Get 1:1 Help Now