2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 1. If k is odd $2^k = 2.2^{2m}$ for some m. $\endgroup$ – Paul Sep 2 '16 at 10:29
  • $\begingroup$ Thanks. Ok, I see, but what is the problem then with $p^2$? $\endgroup$ – Kolmin Sep 2 '16 at 10:33
  • $\begingroup$ $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. $\endgroup$ – Piotr Benedysiuk Sep 2 '16 at 12:10
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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) $\endgroup$ – Kolmin Sep 2 '16 at 10:56
  • $\begingroup$ $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. $\endgroup$ – Arthur Sep 2 '16 at 11:00
  • $\begingroup$ Thanks a lot. I actually think I miss some basic property of arithmetic (something that has to be done in elementary school at most or so) that is not making me see clearly the argument. I will go back there, and then most probably with your answer I will see it. $\endgroup$ – Kolmin Sep 2 '16 at 11:05
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.