Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In my textbook the following proof is given for the fact that $\sqrt{5}$ is irrational:

$ x = \frac{p}{q}$ and $x^2 = 5$. We choose $p$ and $q$ so that the have no common factors, so we know that $p$ and $q$ aren't both divisible by $5$.

$$\left(\dfrac{p}{q}\right)^2 = 5\\ \text{ so } p^2=5q^2$$

This means that $p^2$ is divisble by 5. But this also means that $p$ is divisible by 5.

$p=5k$, so $p^2=25k^2$ and so $q^2=5k^2$. This means that both $q$ and $p$ are divisible by 5, and since that can't be the case, we've proven that $\sqrt{5}$ is irrational.

What bothers me with this proof is the beginning, in which we choose a $p$ and $q$ so that they haven't got a common factor. How can we know for sure that there exists a $p$ and $q$ with no common factors such that $x=\dfrac{p}{q} = \sqrt{5}$? Because it seems that step could be used for every number

Edit:

I found out what started my confusion: I thought that any fraction with numerator 1 had a common factor, since every integer can be divided by 1. This has given me another question: Are confusions like this the reason why 1 is not considered a prime number?

share|improve this question
3  
A maybe cleaner way to see it: suppose $\sqrt{5}$ is rational, so it equals $\frac{p}{q}$, and thus $p^2 = 5q^2$. The left hand side has an even number of factors of 5, being a square, and the right hand side an odd number (square has even number plus one extra 5), and this is absurd, as they are the same number... –  Henno Brandsma Dec 22 '12 at 21:42
2  
Yes, 1 being counted as prime (or any number with a multiplicative inverse, so we could add it in a product and cancelling it with another term, like -1) would "spoil" a unique prime factorization result... –  Henno Brandsma Dec 22 '12 at 21:44
1  
"How can we know for sure that there exists a p and q with no common factors such that $x=\frac{p}{q}=\sqrt{5}$? Because it seems that step could be used for every number" It might be instructive to try and push the proof through with $x = \frac{p}{q} = \sqrt{4}$ and see where it fails. –  Austin Mohr Dec 23 '12 at 6:31

8 Answers 8

up vote 7 down vote accepted

We know that by the definition of rational numbers, essentially: rationals can be written as $\frac{p}{q}$ for integers $p,q$, $q \neq 0$.

If for some choice they would have a common factor, we could divide it out, with the same quotient (our rational number) remaining, and they would have one factor less in common. As the number of common factors is finite, we have to repeat this at most finitely many times to have a choice of $p$ and $q$ with no common factors.

The proof starts by assuming we have done this step already.

share|improve this answer
    
I think I misunderstood common factor, because I thought numbers like $\dfrac{1}{2}$ have a common factor too (both are divisible by 1) –  JohnPhteven Dec 22 '12 at 21:38
1  
No, 1 does not count. –  Henno Brandsma Dec 22 '12 at 21:40
1  
+1, With the caveat that you must still show that this "dividing out" eventually terminates with $p$ and $q$ relatively prime. –  user7530 Dec 22 '12 at 22:14

if $p,q$ have a common factor, just reduce the fraction and start the proof from scratch. This is a standard technique in such irrationality proofs.

share|improve this answer
1  
I think what the OP is looking for is an understanding of "just reduce the fraction" — that the process in general is always possible, and terminates with a fraction $p/q$ in which $p$ and $q$ have no common factor (greater than $1$). –  ShreevatsaR Dec 23 '12 at 6:24

We're assuming their existence, and reaching something which is absurd. This leads us to conclude that their existence is indeed impossible, whence the result follows.

The core of a proof by contradiction is the following: we assume a premise $p$. With that, we work out conclusions $q,r,s,t$ by means we know are correct, and reach a contradiction $C$, which we know is absurd. Since we are sure all the intermediate steps we took are correct, we must conclude that the premise $p$ was incorrect in the first place.

share|improve this answer

It is clear that neither $p$ nor $q$ can be $0$.

Let $5^k$ be the highest power of $5$ that divides $p$, and let $5^l$ be the highest power of $5$ that divides $q$.

Suppose that $k\le l$. Let $p=5^kp'$ and $q=5^kq'$. Then $\dfrac{p}{q}=\dfrac{p'}{q'}$ and $5$ does not divide $p'$.

Similarly, if $l\le k$, let $p=5^lp'$ and $q=5^lq'$. Then $5$ does not divide $q'$.

Thus the fraction $\dfrac{p}{q}$ can always be replaced by an equivalent fraction $\dfrac{p'}{q'}$ such that $5$ fails to divide at least one of $p'$ or $q'$.

share|improve this answer

Exactly what MSEoris said, you can always reduce a fraction to such a point that they have no common factors, if $\frac{p}{q}$ had a common factor n, then $nk_0 = p$ $nk_1 = q $ then $\frac{p}{q} = \frac{nk_0}{nk_1} = \frac{k_0}{k_1}$, now if $k_0, k_1$ have a common factor do the same and you will eventually get a fraction with no common factor

share|improve this answer

You just stated a proof by contradiction. You assumed that there exists $p$ and $q$ that are relatively prime such that $\frac{p^2}{q^2} = 5$. You came to the conclusion that $p$ and $q$ cannot be relatively prime, contradicting your assumption. Therefore, there are no such $p$ and $q$, and therefore no rational number, whose square is 5.

share|improve this answer

Suppose $\sqrt{5}$ is rational. Then there is a smallest positive integer $q$ such that $\sqrt{5} = p/q$. Then $\sqrt{5} = \sqrt{5}\frac{\sqrt{5}-2}{\sqrt{5}-2} = \frac{5-2\sqrt{5}}{\sqrt{5}-2} = \frac{5-2p/q}{p/q-2} = \frac{5q-2p}{p-2q} $.

Since $2 < \sqrt{5} < 3$, $2 < p/q < 3$, or $2q < p < 3q$, so $0 < p-2q < q$. We have thus found a representation of $\sqrt{5}$ with a smaller denominator, which contradicts the specification of $q$.

Therefore $\sqrt{5}$ is irrational.

This can be easily generalized to prove that if $n$ is a positive integer that is not a square of an integer, then $\sqrt{n}$ is irrational. (Copy, paste, and edit used to create the following.)

Let $k$ be such that $k^2 < n < (k+1)^2$. Suppose $\sqrt{n}$ is rational. Then there is a smallest positive integer $q$ such that $\sqrt{n} = p/q$.

Then $\sqrt{n} = \sqrt{n}\frac{\sqrt{n}-k}{\sqrt{n}-k} = \frac{n-k\sqrt{n}}{\sqrt{n}-k} = \frac{n-kp/q}{p/q-k} = \frac{nq-kp}{p-kq} $.

Since $k < \sqrt{n} < k+1$, $k < p/q < k+1$, or $kq < p < (k+1)q$, so $0 < p-kq < q$. We have thus found a representation of $\sqrt{n}$ with a smaller denominator, which contradicts the specification of $q$.

Note: This is certainly not original - but I had fun working it out based on the proof I know that $\sqrt{2}$ is irrational.

Note 2: It is interesting that this does not use any divisibility properties. Another type of proof can be based on the Pell equation: If there is a solution in positive integers $x$ and $y$ to $x^2-ny^2 = 1$, then $\sqrt{n}$ is irrational. This is done by (1) showing that there are solutions to the equation with arbitrarily large $x$ and $y$; (2) showing that the assumption that $\sqrt{n}$ is rational contradicts (1).

Of course the analysis of the general Pell equation is decidedly non-trivial (at least to me), but solutions for particular values of $n$, such as 2 or 5, are easily generated by hand. Don't try this for $n = 61$, though.

share|improve this answer

One can show a more general result which is the following.

Proposition: If $p$ is a prime number then $\sqrt{p}$ is irrational.

Proof: assume that $\sqrt{p}$ is rational then we must have $$p=\frac{n^2}{m^2}$$ for some positive integers $n,m$ with no common divisors. but then$$n^2=pm^2$$ which implies that $p$ divides $n^2$ but then using "Euclid's Lemma" we must have $p$ divides $n$, which implies that $n=pk$ for some $k\in \Bbb N$, but then $$pm^2=n^2=(pk)^2=p^2k^2$$ which implies$$m^2=pk^2$$ that is $p$ divides $m^2$, again using Euclid's lemma we must have $p$ divides $m$. Thus, we have found a common divisor of $n$ and $m$ which is contrary to the assumption. Thus, we must have $\sqrt{p}$ is irrational.

share|improve this answer

Your Answer

 
discard

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.