3 ms·
Simpler explanation for why perfect square <=> odd number of factors Proof: For every divisor d of n, n/d is another, different, divisor. This gives a pairing
by boyobo 7y ago
Simpler explanation for why
perfect square <=> odd number of factors
Proof: For every divisor d of n, n/d is another, different, divisor.
This gives a pairing of all the divisors.
The only exception is if n/d = d.
The exceptional case n/d=d only happens when n=d^2, i.e. when n is a perfect square.
Thus, when n is not a perfect square, there is a pairing of all its divisors, hence the number of divisors is even.
If n is a perfect square, the pairing pairs up all the divisors except for sqrt(n). Thus the number of divisors is odd.
- seanhunter 7y agoWhat about 27? It has an odd number of factors but isn't a perfect square. I think your reasoning fails for x^y where y is an odd number > 1.
- boyobo 7y agoThe factors of 27 are 1,3,9 and 27. That’s four factors. That's why door 27 is closed at the end of the open/closing process - employees 1,3,9 and 27 touch the door and so the final state of the door is the same as the initial state of the door. Maybe you are talking about the number of prime factors. This quantity is irrelevant to door open/closing problem.
- seanhunter 7y agoAah you're right. Thanks.
- jerome-jh 7y agoperfect square => even number of factors n = r^2 n = (p1^k1 * p2^k2 * ... * pi^ki)^2 n = p1^(2 * k1) * p2^(2 * k2) * ... * pi^(2 * ki) hence n has 2 * (k1+k2+...+ki) factors. Or am I wrong? Reciprocal left as an exercise ;)
- boyobo 7y agoNot really sure what your argument is. But it’s wrong, because n=4 is a counterexample. The factors are 1,2 and 4. This is an odd number of factors. Edit: it seems you are talking about 'The number of factors in the prime factorization of n'. This is not really relevant to the question posed in the submission.
- jerome-jh 7y agoIndeed I was talking about prime factors. I understood your point later last night and it is certainly valid. I quite do not understand the original paper though.