# Is there a proof of the irrationality of $\sqrt{2}$ that involves modular arithmetic?

I was reading Ian Stewart's Concepts of Modern Mathematics.

Using congruences, It's possible to explain why all perfect squares end in $0,1,4,5,6,9$ but not in $2,3,7,8$.

With this I had the idea of exploring the congruences for both sides of $n^2=2m^2$ in Mathematica:

Table[Mod[n^2, 9], {n, 0, 20}]

Table[Mod[2 m^2, 9], {n, 0, 20}]

{0, 1, 4, 0, 7, 7, 0, 4, 1, 0, 1, 4, 0, 7, 7, 0, 4, 1, 0, 1, 4}

{0, 2, 8, 0, 5, 5, 0, 8, 2, 0, 2, 8, 0, 5, 5, 0, 8, 2, 0, 2, 8}

But I'm still not sure if the outputs really show what I'm looking for, I have also tried $mod \;10$. The idea is still pretty loose in my mind, I'm stuck on deciding if this proves something or what directions I could take in this enterprise.

-
A side remark--could one use the Hasse principle, knowing that $x^2-2=0$ has no solution in $\mathbf{Q}_3$ - the $3$-adic field - to show that $x^2-2=0$ has no solution in $\mathbf{Q}$? –  doppz Dec 8 '13 at 16:34
@doppz: You don't need this kind of machinery. ${\bf Q}$ is a subring of ${\bf Q}_3$. So if the polynomial is irreducible over the latter, it can't be reducible over the former, plain and simple. –  tomasz Dec 8 '13 at 17:11

$x^2-2$ is irreducible over $\mathbb{Z}$ by reduction since it is irreducible over $\mathbb{F}_3$. Check directly $0^2-2 \equiv 1, 1^2-2 \equiv 2, 2^2-2 \equiv 2 \bmod 3$.

Another alternative: If $z \in \mathbb{Z}$ with $z^2=2$, then the $2$-adic valuation gives $2 \cdot v_2(z)=v_2(2)=1$, contradiction.

-
This is exactly the answer I wanted to write upon seeing the title. :) –  tomasz Dec 8 '13 at 17:09
@Martin Could you expand a little on the $2$-adic evaluation? I don't know much about it. You don't need necessarily to expand it, if you give me some easy material about it, it's gonna be enough. I've read this. But I'm still a little confused. –  Voyska Dec 14 '13 at 14:03
When $n = \prod_{p \text{prime}} p^{e(p)}$ is the prime factorization, then $e(p)$ is called the $p$-adic valuation of $n$ and denoted $v_p(n)$. For example, $v_2(12)=v_2(2^2 \cdot 3)=2$. –  Martin Brandenburg Dec 14 '13 at 14:18

This is just the standard proof, rewritten in modular arithmetic:

The key here is that $\gcd(m,n)=1$.

Now, look at $$n^2=2m^2 \pmod{4},$$ in all three cases:

• $m,n$ both odd.
• $m$ even, $n$ odd
• $m$ odd, $n$ even

This proof is pretty artificial though.

-
Artificial? Why? –  Voyska Dec 8 '13 at 21:03
@GustavoBandeira Because this is really the one side even implies the other one even argument written with Modular arithmectic. –  N. S. Dec 8 '13 at 21:43