Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}]

And had the results:

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

share|cite|improve this question
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
up vote 15 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer
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
@N.S. But that /is/ a modular arithmetic argument! It's an argument mod $2$. – Stella Biderman Apr 28 at 15:21

(1). The set of congruences of squares, modulo $10$, is $A=\{0,1,4,5,6,9\}$ And the set of congrences, modulo $10,$ of $\{2 x: x\in A\}$ is $B=\{0,2,8\}.$ And $A\cap B=\{0\}$. So, modulo $10,$ we have $$(2). \quad n^2-2 m^2\equiv 0\iff n^2\equiv 2 m^2\equiv 0\iff ((n\equiv 0 \land (m\equiv 0\lor m\equiv 5)).$$ (3). Observe that $n\equiv 0\pmod {10}\iff n^2\equiv 0\pmod {100},$ but that $m\equiv 5\pmod {10} \implies 2 m^2\equiv 50 \pmod {100}.$ And also $m^2\equiv 0 \pmod {10}\iff m\equiv 0 \pmod {10}.$

(4). So $n^2=2 m^2\implies n \equiv m\equiv 0 \pmod {10}.$

(5). Suppose $0\ne (n_1)^2=2(m_1)^2.$ Let $n_{j+1}=n_j/10$ and $m_{j+1}=m_j/10.$ We have $0\ne (n_j)^2=2( m_j)^2$ for each $j\in N.$ And from (4) we have $n_j ,m_j\in N\implies n_{j+1},m_{j+1}\in N.$

(6). Conclusion : Suppose there exist $n_1,m_1\in N$ with $n_1^2=2 m_1^2.$ Then $(n_1,n_2,n_3,...)$ is an infinite descending sequence in $N$, which is impossible. Or,without mentioning infinite sequences, we have $0<n_1/10^j<1$ for some (large enough) $j\in N,$ implying that $n_j\in N \land 0<n_j<1 ,$ which is absurd. Or by the well-ordering of $N$ : If such $n_1,m_1$ exist there would be a least possible $n_1, $ implying $0<n_1\leq n_2=n_1/10, $ which is absurd.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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