Reading this entry on logical connectives from Gower's blog, I found the following statement with proof.
Proposition: If $\sqrt{2}$ is rational then there is an integer that is both even and odd.
Proof. If $\sqrt{2}$ is rational, then we can find positive integers $p$ and $q$ such that $\sqrt{2}=p/q$, which implies that $2q^2=p^2$. Let $k$ be the largest integer such that $p^2$ is a multiple of $2^k$. Since $p^2$ is a perfect square, $k$ must be even. (To see this, just consider the prime factorization of $p$.) But $p^2=2q^2$, and the largest $k$ for which $2q^2$ is a multiple of $2^k$ is odd. (To see this, just consider the prime factorization of $q$.) Therefore, $k$ is both even and odd, which proves the result.
Now, I just don't get two things (somebody could say, considering how relevant those things are, the entire argument...):
1) Since $p^2$ is a perfect square, $k$ must be even.
2) But $p^2=2q^2$, and the largest $k$ for which $2q^2$ is a multiple of $2^k$ is odd.
Why is the case?
Any insight is greatly appreciated.
If $n$ is any number, and $n=2^lm$ where $m$ is odd, then $n^2=2^{2l}m^2$, where $2l$ is even and $m$ is odd. Since $n$ was arbitrary, this must be true for an arbitrary square. Specifically, it holds for $p^2$ and $q^2$.
In the same way, the power of $2$ in $q^2$ must be even, so the power of $2$ in $2q^2$ is one higher and therefore odd. So in the equality $$ p^2=2q^2 $$ The number of factors $2$ that appears in the prime decomposition of the left-hand side is even, while on the right-hand side it's odd. But this conflicts with the fundamental theorem of arithmetic, which says that two prime decompositions of the same number (remember that $p^2$ and $2q^2$ are the same number) must agree on the number of times each prime appears.