# Gower's argument that if $\sqrt{2}$ is rational, then there is an integer that is both even and odd

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.

• 1. If k is odd $2^k = 2.2^{2m}$ for some m. – Paul Sep 2 '16 at 10:29
• Thanks. Ok, I see, but what is the problem then with $p^2$? – Kolmin Sep 2 '16 at 10:33
• $p = \sqrt{2q^2} \in N$ since $p^2$ is a perfect square. If $k$ is odd then $p$ will have a factor $\sqrt{2}$ in it. But then p isn't in N. – Piotr Benedysiuk Sep 2 '16 at 12:10

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.
• Thanks for your answer. I see (almost) everything. The one thing I don't see is that you start by writing that, if $n = 2^l m$ with $m$ odd, then etc etc. From then on, everything is clear, but why in Gower's proof $q$ should actually be odd? (because it ends up pretty much on them as far as I see) – Kolmin Sep 2 '16 at 10:56
• $q$ is not necessarily odd. But if we write $2q^2$ as an odd number times a power of $2$, then that power of $2$ must have odd exponent. – Arthur Sep 2 '16 at 11:00
Consider the dyadic valuation $v_2(n)$, i.e. the exponent of $2$ when decomposing $n$ as a product of primes. By the unicity of prime decomposition, we have $$v_2(mn)=v_2)(m)+v_2(n).$$ In particular, $\;v_2(n^2)=2v_2(n)\;$ and $\;v_2(2n)=v_2(n)+1$.