x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 985

# A question about the number of divisors for perfect squares

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
errang
• 5
• 2
• 2
• +2
4 Solutions

Commented:
You forgot "1"

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

Commented:
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

Commented:
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

Commented:
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

Commented:
>>    If m is a divisor of N, then so is N/m.
This is the definition of a divisor.
0

Author Commented:
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

Commented:
yes
0

Commented:
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

Commented:
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

Commented:
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 Commented:
Thanks
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

## Featured Post

• 5
• 2
• 2
• +2
Tackle projects and never again get stuck behind a technical roadblock.