Confused by proof of the irrationality of root 2: if $p^2$ is divisible by $2$, then so is $p$.

In typical proofs of the irrationality of $\sqrt{2}$, I have seen the following logic:

If $p^2$ is divisible by $2$, then $p$ is divisible by $2$.

Perhaps I am being over-analytical, but how do we know this to be true? IE. do we require a proof of this implication, or is it simply fact?

• If $p$ is odd, then $p^2$ is also odd. – jibounet Aug 30 '16 at 20:49
• It is not "simply fact", but rather "a simple fact": if you have an odd integer $\;2k+1\;$ ,then squaring it you get again an odd integer: $$(2k+1)^2=2(2k^2+2k)+1$$ and likewise: an even integer squared is again even. – DonAntonio Aug 30 '16 at 20:49
• It follows from unique factorization. $p^2 = p \times p$, so if $p^2$ contains (at least) a factor of $2$, then either $p$ does, or else the other $p$ does. But $p = p$, so $p$ must contain a factor of $2$. – Brian Tung Aug 30 '16 at 20:50
• Note that the two comments thus far posted are showing that the contrapositive is true, which of course implies the statement you're asking about is true. – Dave L. Renfro Aug 30 '16 at 20:51
• For what it's worth, I think this is a reasonable question. My experience (personal, and in observation of others) is that teachers often skip over this part too fast, because they're too focused on the proof by contradiction aspect (or some other aspect) of the proof and forget that someone seeing this for the first time is making their way along the forest floor and not flying above the tree tops. – Dave L. Renfro Aug 30 '16 at 20:55

The quickest proof of that fact is to note that every whole number $n$ is either even or odd.

If $n$ is even, $n=2k$ for some whole number $k$: $n^2 = 4k^2 = 2(2k^2)$ is even.

If $n$ is odd, $n=2k+1$ for some whole number $k$: $n^2 = (2k+1)^2 = 4k^2 +4k + 1 = 2(2k^2 +2k) +1$ is odd.

Therefore the square of a whole number is even if and only if that number is even.

According to Euclid's lemma if $p$ is a prime and $a,b$ are integers, then $p \mid ab$ implies that $p \mid a$ or $p \mid b$.

Since $2$ is prime and it divides $p^2 = p\cdot p$ then either $2 \mid p$ or $2 \mid p$. In either case, $2 \mid p$.

• May I ask why the downvote? – benguin Aug 30 '16 at 22:01
• A guess: because invoking Euclid's lemma is using a big sledghammer to crack a little chestnut. But one does need Euclid's Lemma (or equivalent) to prove it for general radicands. – Bill Dubuque Aug 30 '16 at 22:13
• To be honest I've never seen it argued with even/odd parity and I've always seen it done with euclid lemma. Even/odd parity might be slender and useful for this chestnut but we are immediately going to turn around as ask the student to prove root(3), root(12) and root(anything not a perfect square) is irrational in a few minutes, so we I think we should use the sledgehammer. – fleablood Aug 30 '16 at 22:36
• @fleablood The OP tagged it "real analysis" so it might be used only to give an explicit example of an irrational number (so one wouldn't need any more generality). – Bill Dubuque Aug 30 '16 at 22:49
• hmmm.... maybe. still, ... scrambles to book case... well, I'll be... Rudin does the even parity argument after all... but then he asks for an exercise for root(12). Which I guess now hat I think about it when I was a student I did do with modulo 3 arguments rather than prime factoring. I take it back. Still. It's not a bad idea to keep a sledgehammer under the bed. – fleablood Aug 30 '16 at 23:33

A simple and (maybe) less technical way to state it could be to draw the following table: $$\begin{array}{|c|c|} \hline \times&\text{even}&\text{odd}\\ \hline \text{even}&\text{even}&\text{even}\\ \hline \text{odd}&\text{even}&\text{odd}\\ \hline \end{array}$$

As an aside, I personally prefer the proof that no non-integer fraction has non-integer powers by exploiting unique prime factorization: $$\left(\frac{p_1\cdot p_2\cdots p_n}{q_1\cdot q_2\cdot q_m}\right)^s=\frac{p_1^s\cdot p_2^s\cdots p_n^s}{q_1^s\cdot q_2^s\cdot q_m^s}$$ since if you could not cancel any of the prime factors $p_1,p_2,...,p_n,q_1,q_2,...,q_m$ before, you still cannot do it when they appear with multiplicity $s$. This proves that among integers, only perfect squares, cubes etc. have integer square roots, cube roots, etc.

• Maybe your table should have a multiplication sign in the top left corner, or otherwise indicate that the operation is multiplication. – 6005 Aug 30 '16 at 22:11
• Also even simpler is $\text{even}^2 = \text{even}$, $\text{odd}^2 = \text{odd}$, instead of the table. – 6005 Aug 30 '16 at 22:11
• @6005: Thanks!! – String Aug 30 '16 at 22:17

Using modular arithmetic,

$$p^2\equiv p\mod2$$ because

$$p^2-p=p(p-1)\equiv0\mod2$$ as one of $p$ and $p-1$ is even.

It is a simple fact that you can take as an axiom, or you can have it proven easily enough.

Suppose $p$ is even, which means that $p = 2k$, where $k$ is also an integer. Then $p^2 = (2k)^2 = 4k^2$.

But if $p$ is odd, then $p = 2k + 1$, and $p^2 = (2k + 1)^2 = 4k^2 + 4k + 1$.

So if $p$ is divisible by $2$, then so is $p^2$; but if $p$ is not divisible by $2$, then neither is $p^2$.

• I've never seen this treated as an axiom. – John Coleman Aug 30 '16 at 21:51
• @JohnColeman I never said it's been treated as an axiom, I said the OP can take it as such if he wishes. I do concede it should have been clear to me that he doesn't. – Mr. Brooks Sep 1 '16 at 21:10

Some mathematicians distinguish between theorems, lemmas, and corollaries.

Though they are all statements that require proofs, the difference between them is their intention.

Theorems are considered to be important. The appearance of the word theorem is the equivalent of drawing a circle around the subsequent statement and pointing at it with arrows.

Corollaries are (almost) immediate consequences of a theorem.

Lemmas are a way of breaking up the proof of a theorem into smaller pieces. They are generally smaller points that will be useful in proving a consequent theorem.

Sometimes these distinctions are ignored, sometimes they are carried to extremes. Zorn's lemma for example has every right to be called a theorem. It is of major importance. But it is used to prove theorems. So it is properly a lemma.

I have always felt that he Fundamental Theorem Of Arithmetic should also be called a lemma.

The Fundamental Theorem Of Arithmetic. Every integer greater than $1$ is either a prime number or is the product of prime numbers, and this product is unique, up to the order of the factors.

For example, $180 = 2 \times 2 \times 3 \times 3 \times 5 = 2^2 \times 3^2 \times 5$ , and this is the only way that $180$ can be expressed as a product of prime numbers.

Lemma. Let $p$ be a prime number and let $n$ be a positive integer. If $p$ divides $n^2$, then $p$ divides $n$.

Proof. If $n=1$, then $n^2 = 1$ and $1$ has no prime factors. So $n$ must be greater than $1$. Hence $n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_m^{a_m}$ where, for some positive integer $m$, $\; p_1, p_2, \dots, p_m$ are distinct prime numbers and $\; a_1, a_2, \dots, a_m$ are non negative integers. Hence $n^2 = p_1^{2a_1} \times p_2^{2a_2} \times \cdots \times p_m^{2a_m}$. Since $p$ is a prime number, if $p$ divides $n^2$, then the fundamental theorem of arithmetic implies that $p$ must be one of $\; p_1, p_2, \dots, p_m$. It follows that $p$ divides $n$.

Note that it is crucial that $p$ be a prime number. For example, $18$ divides $6^2$ but $18$ does not divide $6$.

Theorem Let $p$ be a prime number. Then $\sqrt p$ is an irrational number.

Proof by contradiction. If $\sqrt p$ were rational, then we could say there exists positive integers, $m$ and $n$, such that $$\sqrt p = \dfrac mn$$ and $m$ and $n$ have no common factors (that is, the fraction $\dfrac mn$ has been reduced to lowest terms).

It follows that $m^2 = p n^2$. Since $p$ divides $p n^2$, then $p$ divides $m^2$. Since $p$ is a prime number, then $p$ divides $m$. So $m = px$ for some integer $x$. Then \begin{align} m^2 &= p n^2\\ (p x)^2 &= p n^2 \\ p^2 x^2 &= p n^2 \\ p x^2 &= n^2 \end{align}

Since $p$ divides $p x^2$, then $p$ divides $n^2$. Since $p$ is a prime number, then $p$ divides $n$.

But then $p$ divides both $m$ and $n$, which contradicts our assumption that $m$ and $n$ had no common factors. Hence the theorem is proved.

Since $2$ is a prime number, we have shown that

Corollary. $\sqrt 2$ is an irrational number.

$\, n\,$ odd $\Rightarrow n^2$ odd  by $(1\!+\!2i)^2 = 1\!+\!2(2i\!+\!2i^2).\,$ So $\,n^2$ even $\,\Rightarrow n\,$ even by contraposition.

My favorite proof of the irrationality of $\sqrt{2}$ invokes the Fundamental Theorem of Arithmetic at this point.

The number $p$ has some unique factorization as primes, say $p = p_1^{n_1} \cdot p_2^{n_2} \cdot p_3^{n_3}...$; so $p^2 = p \cdot p = (p_1^{n_1} \cdot p_2^{n_2} \cdot p_3^{n_3}...)(p_1^{n_1} \cdot p_2^{n_2} \cdot p_3^{n_3}...)$. The only way that $p^2$ can be divisible by 2 is for one of those prime factors to be 2; and the only way for that to happen is for one of the factors of $p$ to be 2, because $p^2$ is composed of exactly the same factors.

I'll give a tip of the hat that this is frequently the most troublesome point for my students when this is taught; we're usually so focused on understanding the proof-by-contradiction structure that this likely-new observation about prime factors gets short shrift.

There's a much simpler answer that doesn't require reaching out to other theorems - just intuition.

Suppose $p^2$ is divisible by 2, but $p$ is not. Then, $p$ is a product of only odd numbers. However, if this were the case, then $p^2$ would also be the product of only odd numbers. This can't be true because $p^2$ is divisible by 2, so $p$ must be divisible by 2 by contradiction.

$p^2$ is even iff $p$ is even. So if $2$ divides $p^2,$ it must divide $p.$

• This is circular reasoning, you've simply restated the claim. – Bill Dubuque Aug 30 '16 at 22:16
• @BillDubuque While I see your point, I disagree it's circular. Most students since elementary school are comfortable with that an even number times an even number is even and an odd number times an odd number is odd. So this answer points out that if you know that, then (by definition) you also know that if $2$ divides $p^2$ then it divides $p$. – 6005 Aug 30 '16 at 22:23
• It's circular. The student can be allowed $p$ is even $\implies p^2$ is even but not $p^2$ even $\implies p$ even. Or if the student does know that, the OP wouldn't be asking this question. – fleablood Aug 30 '16 at 22:40
• @6005 It is circular as written. On the other hand, it could very easily be reworded as "odd squared is odd, even squared is even, and any natural number is either odd or even, therefore $p^2$ is even iff $p$ if even" which is no longer circular. – dxiv Aug 30 '16 at 23:50
• @dxiv I think you just expanded on what was written. I think that's exactly what this answer is getting at. – 6005 Aug 30 '16 at 23:57

We know that any natural number can be expressed as a product of primes. Thus, p can be expressed as product of primes and so p².

Let p = a x b x c x d x ........x n

Where a, b, c, d,....... all are primes.

By hypothesis 2 divides p²,

That means there is a 2 hiding in

So, we can write p² = 2q, where q is a natural number.

So, q = (p²/2)

Since q is a natural number, p² must be even.

So, we may conclude that p must be even.

[If p is odd, p² is odd.]

Thus, 2 divides p.

$p^2$ can't have any factors that $p$ lacks.

$p$ is the product of its factors, each raised to an appropriate degree.

$p = f_1^{x_1} * f_2^{x_2}... f_n^{x_n}$

So $p^2$ must be the product of that product with itself.

$p = (f_1^{x_1} * f_2^{x_2}... f_n^{x_n}) * (f_1^{x_1} * f_2^{x_2}... f_n^{x_n})$

The set of factors is identical. Only the exponents have changed.

$p = f_1^{2x_1} * f_2^{2x_2}... f_n^{2x_n}$

So any factor appearing in one list must appear in the other, which implies the hypothesis above.

• Not a reason to downvote (don't know who downvoted) but I would have written "distinct factors" in the first sentence. – Mr. Brooks Sep 1 '16 at 21:11
• Thanks for the tip. I was wondering what the problem was. I'd assumed that distinctness was implied with factors, but you can never be too explicit. – Charlie Sep 2 '16 at 8:04