Hacker News new | past | comments | ask | show | jobs | submit login

Let n = 2r, and n = xx for some integers r and x, because n is even and n is a square. So xx = 2r.

Because of the fundamental theorem of arithmetic, we know that x must be representable as the product of a unique string of prime numbers.

Because 2 is prime, then since xx = 2r, there must be a 2 in the string of primes for xx.

But since 2 is prime, it must be in x as well, because a prime cannot come out of nowhere. In other words, if there is a given prime P in xx, there must be at least two P in xx, because there was at least one in x, and the number of each one got doubled in xx.

Therefore xx = 2r = 2*2*y = 4y for some integer y.

Therefore n = 4y and sqrt(n) = sqrt(4y) = sqrt(4)sqrt(y) = 2sqrt(y) which is an even number.

Therefore sqrt(n) is even.




FTA is massive overkill. For every number n, either n can be expressed as 2k for some k, or 2k+1 for some k, but not both (proof: by induction); in particular the square root can too. If the square root is (2k+1), then the square is 4k^2 + 4k + 1 = 2(2k^2+2k) + 1, which is by definition odd, not even as we supposed.


True, but the FTA proof is just really intuitive for me and I like it.


Thanks for the proof, it was fun to follow, and I agree that it's quite intuitive.

I think that it would be helpful to mention why sqrt(y) must be an integer.

(I know that it is, but it also feels a bit glossed over, given that all the other steps of the proof were explained so thoroughly.)


The FTA proof is the one that's obvious, though. If it's really easy to do something using a basic tool, why worry that the basic tool is complex to describe?




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: