# What are the explanations for certain steps in these proofs for the irrationality/rationality of certain numbers?

From Stephen Abbott's Understanding Analysis:

Theorem:

There is no rational number whose square is 2.

Proof:

Assume for contradiction, that there exist integers $p$ and $q$ satisfying (1) $\left(\frac{p}{q}\right)^2 = 2$. We may also assume that $p$ and $q$ have no common factor, because, if they had one, we could simply cancel it out and rewrite the fraction in lowest terms. Now, equation (1) implies (2) $p^2 = 2q^2$. From this we can see that the integer $p^2$ is an even number (it is divisible by 2), and hence $p$ must be even as well because the square of an odd number is odd. This allows us to write $p=2r$, where $r$ is also an integer. If we substitute $2r$ for $p$ in equation (2), then a little algebra yields the relationship $2r^2=q^2$. This last equation implies that $q^2$ is even, and hence $q$ must also be even. Thus, we have shown that $p$ and $q$ are both even (i.e., divisible by $2$) when they were originally assumed to have no common factor. From this logical impasse, we can only conclude that equation (1) cannot hold for any integers $p$ and $q$, and thus the theorem is proved.

Exercise:

(a) Prove that $\sqrt{3}$ is irrational. Does a similar argument work to show that $\sqrt{6}$ is irrational?

(b) Where does the proof of the irrationality of $\sqrt{2}$ break down if we try to use it to prove $\sqrt{4}$ is irrational?

Solution:

(a) Assume, for contradiction, that there exist integers $p$ and $q$ satisfying (1) $\left(\frac{p}{q}\right)^2 = 3$. Let us also assume that $p$ and $q$ have no common factor. Now, equation (1) implies (2) $p^2 = 3q^2$. From this, we can see that $p^2$ is a multiple of $3$ and hence $p$ must also be a multiple of $3$. This allows us to write $p = 3r$, where $r$ is an integer. After substituting $3r$ for $p$ in equation (2), we get $(3r)^2 = 3q^2$, which can be simplified to $3r^2=q^2$. This implies $q^2$ is a multiple of $3$ and hence $q$ is also a multiple of $3$. Thus we have shown $p$ and $q$ have a common factor, namely $3$, when they were originally assumed to have no common factor. A similar argument will work for $\sqrt{6}$ as well because we get $p^2 = 6q^2$ which implies $p$ is a multiple of $2$ and $3$. After making the necessary substitutions, we can conclude $q$ is a multiple of $6$, and therefore $\sqrt{6}$ must be irrational.

(b) In this case, the fact that $p^2$ is a multiple of $4$ does not imply $p$ is also a multiple of $4$. Thus, our proof breaks down at this point.

Question(s):

Could somebody please help and spell out for me some of the theorems which are being used along the way in the arguments above? Since the theorem quoted above is the first theorem in the book, I am not exactly sure what is assumed to be common knowledge or whatever...

For $\sqrt{3}$, what exactly is being used to justify "$p^2$ is a multiple of $3$ and hence $p$ must also be a multiple of $3$"? I've seen some other proofs for this which have to do with even and odd numbers, but the one above has to do specifically with $3$, right?

For $\sqrt{6}$, why is it important to say "$p^2 = 6q^2$ implies $p$ is a multiple of $2$ and $3$" instead of "is a multiple of $6$"?

For $\sqrt{4}$, why is it so clear that "the fact that $p^2$ is a multiple of $4$ does not imply $p$ is also a multiple of $4$"? I know I can think of a counterexample like $p=2 \Rightarrow p^2=4$ and $4$ is divisible by $4$, but $2$ is not. But what is the pattern to notice?

Any help is appreciated. Also, as if it weren't obvious, I think that answers which are not too advanced will be most helpful for me, thanks!

-
For the part about the square root of 4: It's because a square isn't a prime. Recall that $$p \text{ prime} \iff \left(p \mid ab \implies p \mid a \lor p \mid b\right)$$ – kahen Aug 19 '11 at 17:13
In a similar vein, for $\sqrt 3$, it's using the fact the $3$ is prime: $3$ divides $p^2$, but since $3$ is prime, it must divide $p$ (see Kahen's statement above). – John M Aug 19 '11 at 17:19
To obtain optimal answers one should reveal reasonable context. Is this a course on proofs, number theory, or what? Do you know any number theory or abstract algebra? – Bill Dubuque Aug 19 '11 at 17:20
@kahen and John, thank you for your comments! – ghshtalt Aug 19 '11 at 17:22
@Bill: for context, this is me trying to go through the book Understanding Analysis by Stephen Abbott. Unfortunately I do not know any number theory or abstract algebra... – ghshtalt Aug 19 '11 at 17:23

"$p^2$ is a multiple of $3$ and hence $p$ must also be a multiple of $3$".

This follows from Euclid's lemma, which says that if a prime number divides the product of two numbers, then it divides at least one of the two numbers. In this case the prime number involved is $3$ and the two numbers whose product it divides are both $p$.

But you can get by with something weaker than Euclid's lemma and easier to prove. Every integer is either a multiple of 3, or 1 more than a multiple of 3, or 2 more than a multiple of 3. Thus either $3n$ or $3n+1$ or $3n+2$. If you square those, you get $9n^2$, which is clearly a multiple of 3, or $(3n+1)^2 = 9n^2 + 6n + 1 = 3(\text{something})+1$, thus not a multiple of 3, or $(3n+2)^2 = 9n^2 + 12n + 4 = 3(\text{something})+1$, thus again not a multiple of 3. Hence $p^2$ is a multiple of 3 only in the case where $p$ itself is a multiple of 3.

6 is not prime. If 6 divides $ab$, then it need not be true that 6 divides $a$ or 6 divides $b$. For example, if $a=8$ and $b = 9$, the 6 divides $ab$ but 6 divides neither $a$ nor $b$. But it is true that if 6 divides $ab$ then 2 divides $ab$ and 3 divides $ab$. And 2 and 3 are prime. Hence 2 divides either $a$ or $b$ and 3 divides either $a$ or $b$.

-
thank you for this – ghshtalt Aug 20 '11 at 6:11

The key - at the heart of unique factorization - is the prime divisor property: a prime divides a product iff it divides one of the factors. By induction, this partly generalizes to products of distinct primes, i.e. "squarefree" integers. Namely, if a squarefree integer divides $\rm\:n^k\:$ then it must divide $\rm\:n\:.\:$ This squarefree divisor property shows how to generalize the classical proofs to any radicand that is not a perfect-square. Pull out of the radicand the squarepart, leaving a squarefree radicand $\ne 1\:.\:$ Now apply to this squarefree radicand the classical proof as above, using the squarefree divisor property in place of the prime divisor property. Thus the proof generalizes to the squarefree radicand $\:6\:,\:$ but not to the square $\:4 = 2^2\:,\:$ as you have observed. See here for much more on squarefree integers.

There are other approaches to such irrationality proofs, e.g. using the parity of exponents in a unique prime factorization, or unique fractionization, or Euclid's Lemma, or, more generally, employing the monic case of the rational root test ("integral closure"), e.g. see this prior thread.

-
But of course you don't need unique factorization. After all, the Pythagoreans, who proved that $\sqrt{2}$ is irrational, probably didn't know about unique factorization. What you need is only some weak special cases of unique factorization, which are easy to prove. – Michael Hardy Aug 19 '11 at 17:37
@Mic The ancient brute force proofs essentially verify that $\rm\:n^2 \equiv 0\:$$\:\Rightarrow\:$ $\rm\:n\equiv 0\pmod p\:$ by manually verifying it for all $\rm\:p\:$ congruence classes $\rm 0,1,\ldots,p-1\:.$ That only works for a fixed prime. It does not generalize to a proof for all primes. Ingenuity is required for the generalization. – Bill Dubuque Aug 19 '11 at 17:46
@Mic Further, one doesn't need anything near as powerful as unique factorization. Rather it suffices to use integral closure (or, more precisely, the special case known as root closure). If you follow the links to my posts (and their links...) you will find much written on such topics, including proofs that generalize all the classical irrationality proofs. – Bill Dubuque Aug 19 '11 at 17:49
thank you very much – ghshtalt Aug 20 '11 at 6:10

For $\sqrt{4}$, why is it so clear that "the fact that $p^2$ is a multiple of $4$ does not imply $p$ is also a multiple of $4$"?

Since $4=2^2$, $p^2$ is a multiple of $4$ only tells us that $p$ is a multiple of $2$.

For any number $n$, if $p^2$ is a multiple of $n^2$, then all we know is that $p$ must be a multiple of $n$.

However, suppose that for some prime, $q$, we have that $p^2$ is a multiple of $q^{2k+1}$, then $p$ must be a multiple of $q^{k+1}$ (one of the $p$'s in $p^2$ must have at least $k+1$ of the factors of $q$). The same can also be said if $q$ is square-free rather than just prime, but I leave that as an exercise.

-
thank you rbojohn – ghshtalt Aug 20 '11 at 6:11