3

In the proof for "$\sqrt2$ is irrational" one of the steps goes like this:

$a^2 = 2b^2$

From this we conclude that $a^2 \equiv 0 \mod 2 $ We don't stop here and infer that $a \equiv 0 \mod 2$ implying $a^2 \equiv 0 \mod 4$

How can we make that connection that since $a^2 \equiv 0 \mod 2$ , and $a \equiv 0 \mod 2$ and not $\sqrt2$

Does this make any sense?

Update:

I fully understand that squaring an even number gives an even number as a result. What I don't understand is how it was said that since a^2 is even then a is a multiple of 2, as opposed to saying it's a multiple of $\sqrt2$.

Nathaniel Bubis
  • 33,018
Rire1979
  • 409

4 Answers4

3

We proceed by contrapositive: If $a$ is odd, then $a^2$ is odd. Hence if $a^2$ is even, then $a$ is even.

To see the first implication, if $a$ is odd then we write $a = 2k + 1$. Then $a^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$ is odd.

1

If $a$ is odd, say $a=2k+1$, then $a^2=4k^2+4k+1$ would also be odd.

azarel
  • 13,120
1

Because 2 is a prime. 2*1 = 2 = divisible by 2

Don Larynx
  • 4,703
1

To continue with your own way of reasoning, if $a^2 \equiv 0 \pmod{2}$, then, since $2$ is a prime number $\mathbb{Z}_2$ is a field and therefore there must be no nilpotent elements in a field except $0$, hence $a \equiv 0 \pmod{2}$. You can reword it in other ways too, but only the way of wording it will be different, the core of all of them will be the same as the following theorem:

In general, if a prime number $p \mid a^n$ then you can say $p \mid a$. Because we can write $p \mid a^n \implies p \mid a.a^{n-1}$. Now, if $p \mid a$ then we're done, but if it doesn't, then $(p,a)=1$ and we can apply Euclid's theorem to obtain $p \mid a^{n-1}$. Now you can apply the same logic to $p \mid a^{n-1}$ recursively until you conclude $p \mid a$. This is the same as saying $a^n \equiv 0 \pmod{p} \implies a \equiv 0 \pmod{p}$ where $p$ is a prime number.

moreover, it's obvious that if $a \equiv 0 \pmod{m}$ then $a^n = 0 \pmod{m^n}$. This is really equivalent to $m \mid a \implies m^n \mid a^n$ which is easy to see.

user66733
  • 7,379
  • But since we've said $\sqrt2$ is rational and ($\sqrt2$)^2 = 2, can't we say $\sqrt2$ is prime? – Rire1979 Sep 16 '13 at 19:53
  • @Rire1979: No, prime numbers are only defined for integers, not even rationals. They are the building blocks of integers under multiplication in the sense that you can decompose any integer number whose absolute value is bigger than one into a product of them uniquely. We don't have such a thing for $\mathbb{Q}$ because $\mathbb{Q}$ is a field and every non-zero element has an inverse which causes troubles. Notice how we have excluded invertible elements of $\mathbb{Z}$ in prime factorization, now in $\mathbb{Q}$ everything except zero is invertible! to be continued... – user66733 Sep 17 '13 at 01:41
  • @Rire1979: To show that $\sqrt{2}$ isn't an integer number, you should use the fact that if $m,n \in \mathbb{N}$ and $m<n$ then $a^m < a^n$ for $a \in \mathbb{N}$ and then you should note that $1<\sqrt{2}<2$ while there is no integer between $2$ and $1$. Hence, $\sqrt{2}$ is not an integer and can't be prime. – user66733 Sep 17 '13 at 01:46
  • I get it now, thanks! – Rire1979 Sep 20 '13 at 18:12