Is Every Number with an Odd Number of Divisors a Perfect Square?

[GeoMike]

Ok, the proof to be done is pretty simple:
Prove that a number is a square only when the number of positive divisors is odd.

I pretty sure I know the answer, I'm just not sure how to go about writing it out...

If c is the number then you can write:
c=ab.
a and b are divisors of c. If a doesn't equal b then you have two different divisors. If a=b, then c=ab can be rewritten as c=a^2, and you only have one divisor. Because of this any number that can be written as a square of another number has an odd number of divisors -- all the pairs of factors that equal the number plus the 1 divisor that is squared to make the number.

I guess I just need to know how to write this out better, and how to make sure I haven't assumed to much as given/proven at the outset.
Thanks,
-GM-

 

[shmoe]

That's pretty much it, you've got the essential idea of pairing divisors c=ab with a,b distinct, which leaves out the oddball $$\sqrt{c}$$ out. You could try organizing the divisors c=ab with the assumption that a<=b, but this isn't necessarily any better.

For an alternate way, you could look at the prime factorization of c and count the divisors that way. (this isn't a 'better' way, but gives a different point of view to consider if you run across other divisor problems)

 

[Architeuthis Dux]

Sure, I'd be happy to help with the proof on divisors. Let's start with the statement you are trying to prove: "A number is a square only when the number of positive divisors is odd."

To prove this statement, we will use a proof by contradiction. This means that we will assume the opposite of the statement is true and then show that this leads to a contradiction, which means that our original statement must be true.

So, let's assume that a number c is a square, but the number of positive divisors is even. This means that c has an even number of divisors, which we can represent as 2n, where n is a positive integer.

Now, let's consider the prime factorization of c. We can write c as c = p1^a1 * p2^a2 * ... * pn^an, where p1, p2, ..., pn are distinct prime numbers and a1, a2, ..., an are positive integers.

Since c is a square, we know that each exponent ai must be even (because when we multiply two numbers with the same base, we add their exponents). Therefore, we can rewrite our prime factorization as c = p1^(2b1) * p2^(2b2) * ... * pn^(2bn), where b1, b2, ..., bn are positive integers.

Now, let's consider the number of divisors of c. Each divisor of c can be written as d = p1^x1 * p2^x2 * ... * pn^xn, where 0 ≤ xi ≤ 2bi for each i. This means that each divisor of c can be represented by choosing an exponent between 0 and 2bi for each prime factor.

Since c has 2n divisors, this means that there are (2b1 + 1) * (2b2 + 1) * ... * (2bn + 1) possible combinations of exponents for the divisors of c. But this is an odd number, since each factor (2bi + 1) is odd.

However, we assumed that the number of divisors of c is even, which leads to a contradiction. Therefore, our original statement must be true: a number is a square only when the number of positive divisors is odd.

I hope this helps you to write