What is the most rigorous proof of the irrationality of the square root of 3?

I am currently trying to self-study Stephen Abbott's Understanding Analysis. The first exercise asks to prove the irrationality of √3, and I understand the general idea of the contradiction by finding that the relatively prime integers p and q have a common factor. However, I am stuck on the idea that if p^2 is divisible by 3, then p is divisible by 3. Abbott's solution assumes this, but I have also seen proofs that analyze the situations where a and b are even or odd (such as NASA's). Even or odd really is just saying multiple of 2, which confuses me as to why the even/odd method (which is much less concise) would be used.

Sorry for the block of rambling text, I just want to start writing proofs the right way. I guess my real questions are:

If p^2 is divisible by a prime number, is p also divisible by that prime number? Can this just be assumed, or is there a theorem I have to mention in the proof? Why do some proofs analyze the even/odd situations of a and b? Are they more rigorous, and if they are not, why are they used, considering their added length and complexity? Finally, am I simply over thinking the idea of being rigorous and missing the big picture?

• even/odd (that is, divisibility by $2$) is used to show $\sqrt{2}$ is irrational. But for $\sqrt{3}$ we consider divisibility by $3$ instead. – GEdgar Jun 3 '15 at 0:25
• If $p^2$ divides a prime, so does $p$. This is a theorem. – Akiva Weinberger Jun 3 '15 at 0:26
• Don't confuse "divides" with "divisible by" – GEdgar Jun 3 '15 at 0:28
• In case it wasn't clear what @ GEdgar's comment is in reference to, it is to @columbus's comment. It should read "if $ab$ is divisible by a prime, $p$, then either $a$ is divisible by $p$ or $b$ is divisible by $p$." Indeed, this is the definition of a prime element in a ring. The definition that says "a prime cannot be expressed as a product of two non-unit integers" is rather the definition of an irreducible element (which happens to be the same as prime for integers). – JMoravitz Jun 3 '15 at 0:42
• "What is the most rigorous proof of..." How does one compare the degrees of rigor of proofs? – Did Jun 3 '15 at 6:02

personally I prefer to prove these results by contrapositive. If $p,q$ are coprime positive integers with $q>1$ then $$p^{k}/q^{k}$$ is not an integer for any $k>0.$ This immediately implies the irrationality of all roots of $3.$ In fact, it proves that any root of an integer that is not an integer is irrational.

The key is, as everyone has already said, is that $p,q$ coprime implies that $p^{k}$ and $q^k$ are also coprime, and so $p^k/q^k$ is not an integer.

This is implied by that if a prime $m$ divides $ab$ then it divides $a$ or $b.$ So if it divides $p^k$ it divides $p$ and if it divides $q^k$ it divides $q.$ So no prime will divide both of them unless it divides $p$ and $q$ which we ruled out.

How do we prove the result that $m$ must divide $a$ or $b$? Either it divides $a$ and we are done or $m$ and $a$ are co-prime since $m$ is prime. We then have that there exist $\alpha$ and $\beta$ such that $$\alpha m + \beta a =1.$$ (this follows from the Euclidean algorithm.) So $$b\alpha m + \beta ab =b$$ Since $m$ divides $ab$ it divides the LHS, so it divides the RHS too.

(See my book "proof patterns" for more discussion.)

• Could you explain why the irrationality of all roots of 3 is immediately implied? – Bryan Jun 3 '15 at 22:51
• I think I get it now. For example, if we let k be 2, and there is no (p/q)^k that is an integer, and since 3 is an integer, then the sqrt of 3 has no rational solution. Since k can be any real number, all roots of 3 are irrational. Is this the general idea? – Bryan Jun 3 '15 at 22:58
• yes that's right and we get for example that the square root of 12 is irrational which is trickier by the other method. – Mark Joshi Jun 4 '15 at 1:09

If a product $ab$ is divisible by a prime $p$, then at least one of the factors is divisible by $p$. If you do not already know this (and Abbott has not proved it prior to this point of the book), then you may need to go back to a more elementary book for its proof.

Euclid, Book VII, Propsition 30

• This is what I was looking for. I was not aware of this theorem. Do you know its exact name? – Bryan Jun 3 '15 at 0:35
• Thank you! Just for verification, I don't need to state that I used Euclid's Lemma during the proof, correct? – Bryan Jun 3 '15 at 0:41
• @Bryan You don't need to invoke the high-powered Euclid's Lemma. Instead, you can do a simple remainder-case analysis just like the parity analysis used for $\,\sqrt 2.\ \$ – Bill Dubuque Jun 3 '15 at 0:44
• Could you elaborate what you mean by remainder-case analysis? – Bryan Jun 3 '15 at 0:48
• Never mind, Bernard's proof of the lemma explains it perfectly. – Bryan Jun 3 '15 at 0:56

Suppose that $\sqrt{3}$ is rational and $\sqrt{3}=a/b$ then squaring both sides gives you $3b^{2}=a^{2}$. We can suppose that $a/b$ is reduced (so $a$ and $b$ have no common factors). This means, in particular, that it is not the case that both $a$ and $b$ are even. Note that $n^{2}\equiv 0,1\mod 4$, $n^2\equiv 0\mod 4$ if $n$ is even and $1$ otherwise. Then, look at $3b^{2}\equiv a^{2}\mod 4$. It is inconsistent. Contradiction.

As for the second (tangent) question: if $p|n^{2}$ where $p$ is a prime, then it is true that $p|n$. Think about the prime factorization of $n^{2}$... $n^{2}=(n)^{2}=(p_1^{k_1}...p_{m}^{k_m})^{2}=p_{1}^{2k_1}...p_{m}^{2k_m}$. So $n$ and $n^2$ have exactly the same prime divisors and knowing how $n$ (or $n^2$) factors tells you how $n^{2}$ (or $n$) factors.

Prompted by the title of the question, FYI here is a sketch of another very nice proof.

If $\sqrt3$ is equal to the fraction $$\frac pq$$ which is a quotient of positive integers, then it is also equal to $$\frac{3q-p}{p-q}\ ,$$ which is a quotient of positive integers with smaller denominator.

• And this generalizes fairly easily to a proof for any non-square. – marty cohen Jan 4 '17 at 23:07

Lemma: $a^2$ is divisible by $3$ if and only if $a$ is.

Proof: By examining all possible cases:

• If $a$ is divisible by $3$, $a^2$ is, trivially.
• If $a$ is not divisible by $3$, $a^2$ is not, either.

Indeed, if $a$ is not divisible by $3$, then $a=3k\pm1$ for some $k$. Then $$a^2=9k^2\pm6k+1=3(3k^2\pm2k)+1$$ has remainder $1$ upon division by $3$.

• Thanks for proving the lemma in a very clear way. – Bryan Jun 3 '15 at 0:55
• So, for each proof that $\sqrt{p}$ is irrational, you need a new and different lemma. – GEdgar Jun 3 '15 at 13:31
• That's a short and clear proof for the case the O.P. submitted. I wouldn't use it as a general proof. There is a very general proof that doesn't even use the Fundamental theorem of arithmetic, nor Euclid's lemma. It consists in proving that $\sqrt n$ is irrational, unless $n$ is a square in $\mathbf N$ and is just based on the well order of $\mathbf N$. – Bernard Jun 3 '15 at 13:51

Let us try a new one. Assume $a = \sqrt{3}b$ for integers a and b, then $a^2 = 3b^2$. Now use uniqueness of prime factorization and count the occurences the prime 3 has in the numbers. if $a = 3^{d}c$ and $b = 3^{g}f$, then we have that $a^2 = 3^{2d}c^2$ and that $3b^2 = 3^{2g+1}f^2$.

We now see that left hand side has even number of 3-factors but right hand side has odd - contradiction.

Here is a very simple general proof that the square root of any integer that is not a perfect square is irrational. For convenience, write $a|b$ (read "a divides b") for "b is divisible by a". The proof depends on Euclid's Lemma, which states that if $gcd(a, b) = 1$ and $a | bc$, then $a | c$.

For positive integers $a$, $b$, and $n$, assume $(\frac a b)^2 = n$, where $gcd(a, b) = 1$ (i.e., the fraction is in lowest terms). Then $a^2 = b^2n$, so $a | (b^2n)$.

By Euclid's Lemma, $a | bn$, and applying the Lemma again, $a | n$. Since $n$ is divisible by $a$, we may divide both sides of $a^2 = b^2 n$ by $a$ to get $a = b^2(\frac n a)$, where $(\frac n a)$ is an integer.

But this means that $b | a$, so $gcd(a, b) = b$. Since we know $gcd(a, b) = 1$, this means that $b = 1$, which implies, in turn, that $n = a^2$. That is, $n$ is the square of an integer, i.e., a perfect square.

We have just proven that any integer that is the square of a rational number is a perfect square. This is logically equivalent to the assertion that any integer that is not a perfect square is not the square of any rational number, i.e., the square root of any integer that is not a perfect square is irrational.