Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

> Likewise if a number is even and is a square of an integer, then its square root must be even.

The proof would be more compelling if this was proven instead of being taken as an obvious fact.



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?


Even x Even results Even

Even x Odd irrelevant if squaring

Odd x Odd results Odd


except sqrt(2) x sqrt(2) is even ( i know we're talking about numbers in Z in this case, and sqrt(2) definitely isn't in Z, but still)

Which made me wonder if the original sentence isn't already assuming something about sqrt(2) and even/odd properties.

(i stopped at the same step as OP wondering if this is as trivial as it seemed)


>Odd x Odd results Odd

This isn't obvious and can't be taken for granted. The explanation posted above (2k+1)^2 by Smaug123 explains this part.


It is really trivial though.




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

Search: