# Proof by contradiction: $r - \frac{1}{r} =5\Longrightarrow r$ is irrational?

Prove that any positive real number $r$ satisfying:

$r - \frac{1}{r} = 5$ must be irrational.

Using the contradiction that the equation must be rational, we set $r= a/b$, where a,b are positive integers and substitute:

\begin{align*} &\frac{a}{b} - \frac{1}{a/b}\\ &\frac{a}{b} - \frac{b}{a}\\ &\frac{a^2}{ab} - \frac{b^2}{ab}\\ &\frac{a^2-b^2}{ab} \end{align*}

I am unsure what to do next?

-
The main point is that you have only transformed the left hand side, so far. Now use the right hand side and proceed as either of the two answerers suggest. kneidell uses $a^2 - b^2 = (a-b)(a+b)$. – t.b. Feb 17 '11 at 0:29
Thanks you guys, I have to go to work right now, but will look over your answers as soon as I get back. – Mr_CryptoPrime Feb 17 '11 at 0:34
What irrationality proofs have you seen? Do any of them look like they might adapt to this case? – Qiaochu Yuan Feb 17 '11 at 0:43

I think your method is sound: if we assume by contradiction that $r=\frac{a}{b}$ with $a,b$ integers we get that $$\frac{a}{b}-\frac{b}{a}=5$$ since neither $b$ nor $a$ is 0, we can multiply by $ab$ and get $$(a-b)(a+b)=5ab$$ now there are three cases to investigate, i'll just point them out so you can finish it off:

1. If $a$ and $b$ are both odd- look at both sides of the equation (mod2).
2. If either one of them is odd and the other even- try the same trick of (mod 2)
3. lastly- if both are even- you can divide the entire equation by 2 and continue.

hope that helps

-
I've inserted an additional blank line so that your 3 steps are displayed as intended. – t.b. Feb 17 '11 at 0:32
@Theo: thanks, i'll remember to do it next time :) – kneidell Feb 17 '11 at 0:48
Yes, I think this is what I was looking for. The book had something like using odd/even identities? Just to clarify...because when we assume the different cases and they all result in inconsistencies, where odd = even, etc...which is impossible? – Mr_CryptoPrime Feb 17 '11 at 7:02
OH!? We have to assume they are relatively prime: (1) even = even, cannot be true because they would divide each other (same with (3))...and odd cannot equal even, so since all cases are false, then our implication is true! – Mr_CryptoPrime Feb 17 '11 at 7:26

To complete your solution, note that you can, without loss of generality, set $a$ and $b$ to be coprime. So you have $a^2=b^2+5ab=b(b+5a)$. Hence $a$ divides $b(b+5a)$. Euclid's lemma now tells you that $a$ divides $b+5a$ (because $a$ and $b$ are coprime). But then $a$ must divide $b$, which is contradiction with the fact that $a$ and $b$ are coprime.

Here's an alternative: transform it into $r^2-5r-1=0$. What are the real (if any) roots of this equation? The quadratic formula gives you: $r_{12}=5/2\pm \sqrt{29}/2$. Since there are at most two different roots for a quadratic polynomial in $\mathbb{R}$, these are the roots. So your problem comes down to showing that $\sqrt{29}$ is irrational. (In fact, you can prove that the square root of any non-perfect-square number is irrational. This is the number-theoretic part).

-
I have never heard of Euclid's lemma before, but your alternate proof should help me understand it better! Merci. – Mr_CryptoPrime Feb 17 '11 at 6:52
+1 for the second solution. Although it's rather elegant to present a solution directly from the given defining equation, it's much more systematic to just write down the minimal polynomial and apply the rational roots theorem. – Pete L. Clark Aug 2 '11 at 6:14

Below are six methods - whose variety may prove somewhat instructive.

$(0)\$ By the Parity Root Test, $\rm\: x^2-5\:x-1\:$ has no rational roots since it has odd leading coefficient, odd constant term and odd coefficient sum.

$(1)\$ By the Rational Root Test, the only possible rational roots of $\rm\ x^2 -5\ x - 1\$ are $\rm\ x = \pm 1\:.$

$(2)\$ Complete your proof: show that $\rm\ (a,b) = 1\ \Rightarrow\ (ab,\:a^2-b^2) = 1\:.\:$ For example, if the prime $\rm\ p\ |\ a,\ a^2-b^2\$ then $\rm\ p\ |\ b^2\ \Rightarrow\ p\ |\ b\:.\$ Alternatively, since $\rm\ a,\:b\$ are coprime to $\rm\ a-b,\:a+b\$ then their products $\rm\ a\:b,\ a^2-b^2\:,\:$ are also coprime, by Euclid's Lemma.

$(3)\$ Suppose it has a rational root $\rm\: R = A/B\:.\$ Put it into lowest terms, so that $\rm\: B\:$ is minimal. $\rm\ R = 5 + 1/R\ \Rightarrow\ A/B = (5\:A+B)/A\:.\:$ Taking fractional parts yields $\rm\ b/B = a/A\$ for $\rm 0\le b < B\:.\:$ But $\rm\ b\ne0\ \Rightarrow\ A/B = a/b\$ contra minimality of $\rm\:B\:.\:$ So $\rm\:b = 0\:,\:$ i.e. $\rm\ A/B\$ has fractional part $= 0\:,\:$ so $\rm\ R = A/B\$ is an integer. Then so too is $\rm\ 1/R = R-5\:.\:$ So $\rm\ R = \pm 1\:,\:$ contra $\rm\ R^2 - 1 = 5\:R\:.$

$(4)\$ As in $\rm(3),\ \ R = A/B = C/A\:,\:$ with $\rm\:A/B\:$ in lowest terms, i.e. $\rm\:B =\:$ least denominator of $\rm\:R\:.\:$ By unique fractionization, the least denominator divides every denominator, therefore $\rm\:B\ |\ A\:,\:$ which concludes the proof as in $(3)$.

For more on the relationship between $(3)$ and $(4)$, follow the above link, where you'll find my analysis of analogous general square-root irrationality proofs, and links to an interesting discussion of such between John Conway and I.

$(5)\$ As Euclid showed a very long time ago, the Euclidean gcd algorithm works also for rationals, so they too have gcds, and such gcds enjoy the same laws as for integers, e.g. the distributive law. Thus $\rm\ (r,1)^2 = (r^2,r,1) = (5r+1,r,1) = (r,1)\$ so $\rm\ (r,1) = 1\:,\:$ so $\rm\ 1\ |\ r \$ in $\rm\:\mathbb Z\:,\:$ i.e. $\rm\ r\in\mathbb Z\:,\:$ and the proof concludes as above. This is - at the heart - the same proof hinted by Aryabhata using non-termination of the continued-fraction algorithm (a variant of the Euclidean gcd algorithm). Alternatively, scaling the prior equations by $\rm\:b^2\:,\:$ where $\rm\ r = a/b\:,\:$ converts it to one using only integer gcd's, namely $\rm\ 1 = (a,b)^2 = (a^2,ab,b^2) = (5ab+b^2,ab,b^2) = b\:(a,b)\:$ so $\rm\ b\ |\ 1\:.\:$

These are essentially special cases of gcd/ideal-theoretic ways to prove that $\rm\: \mathbb Z\:$ is integrally-closed, i.e. it satisfies the monic Rational Root Test. Namely, a rational root of a monic polynomial $\rm\in\mathbb Z[x]\:$ must be integral. Perhaps the slickest way to prove such results is the elegant one-line proof using Dedekind's notion of conductor ideal. Follow that link (and its links) for much further discussion (both elementary and advanced).

-
Hi, Bill, reading your proofs I come across a white square symbol often. What does it mean? Usually, when I've seen it before, it means "fin", but I don't think that's the sense your using it. – Uticensis Feb 17 '11 at 3:42
@Billare: MathJax problems? Above the vertical bar $\rm\ A\ |\ B\$ means $\rm\:A\:$ divides $\rm\:B\:$ and $\rm\ \pm 1\$ means $\:+1\:$ or $\:-1\:$. If something else is not rendering correctly then you'll need to be more specific. Here's the correctly rendered image i.imgur.com/4Szk7.jpg – Bill Dubuque Feb 17 '11 at 3:47
@Bill Dubuque Perhaps so. I was reading your stuff on an iPad this morning, and now going through it on another computer, can't get what I saw to reproduce. Must be the low memory on the thing. Thanks anyway. – Uticensis Feb 17 '11 at 3:59
@Billare: If the problem persists, try clearing your browser's cache. – t.b. Feb 17 '11 at 4:09
Knowing that people are trying to help prove math problems for me over an iPad just fills me with warm fuzzies! :) Merci. – Mr_CryptoPrime Feb 17 '11 at 6:51

Since you have already seen answers which complete your proof, here is another proof using continued fractions.

If $r$ was rational, it will have a finite continued fraction, say $[a_1, a_2, \dots, a_n]$, but that can be extended to $[5, a_1, a_2, \dots , a_n]$ and $[5,5,a_1, a_2, \dots a_n]$ etc, because $$r = 5 + \frac{1}{r} = 5 + \frac{1}{[a_1, a_2, \dots, a_n]} = [5, a_1, a_2, \dots, a_n]$$

In fact, you can easily give the infinite continued fraction of $r$

$$[5,5,5,5,\dots]$$

-
Since its unlikely the OP knows about continued fractions, I've added to my answer a simplified version using only gcds (the continued fraction algorithm is essentially a variant of the Euclidean gcd algorithm) – Bill Dubuque Feb 17 '11 at 15:52
@Bill: Yes I agree (+1 to your answer). But, this viewpoint is not just for the current OP... – Aryabhata Feb 17 '11 at 16:05
Yes, I certainly agree on that point. I've lost count of the number of times I've said precisely what you say above when some folks object that my answer is over the OP's head. Further, if I had ignored everything over my head when I was a student then I probably would never have truly grokked many beautiful ideas that I learned from many great mathematicians. That why I think that planting germs of advanced concepts is an essential component of successful teaching. – Bill Dubuque Feb 17 '11 at 16:34
+1. I like this answer! – user17762 Feb 22 '11 at 23:59