Recently I’ve had the pleasure of teaching a series of Math and Dinner workshops for the New York Math Circle. The series was on the unique factorization of the integers, aka “the fundamental theorem of arithmetic.” I opened the first session with a problem set intended to get the participants (mostly math teachers) to see how heavily their knowledge about numbers depends on this theorem. One of the problems was to prove the irrationality of root 5. The problem served its purpose during the workshop; participants came up with one proof dependent on unique factorization, and I showed them another as well. But to my surprise, when we went to dinner after the workshop was over, participants showed me three more proofs. Two of them were totally independent of unique factorization. The third involved it, but not in any way I would have expected.
The experience was just a mathematical delight – and I’ll share the proofs in a moment – but it got me thinking about teaching too (doesn’t everything?). I’ve repeatedly made the case (along, I suppose, with NCTM and everyone else) that proof needs to be a much more central part of math education than it is, at every level. This is just an elaboration on that theme. How powerful and illuminating it is to see, and consider simultaneously, multiple proofs of the same result; how each proof shines light on the result from a different angle; how different proofs of the same result may generalize differently and show that several large principles might be at play in one tiny case. How in school I’ve rarely given students two different arguments for a major result, and never asked them to compare the arguments to each other. What a missed opportunity that is.
The closest I came was that when I used to teach Algebra I, I would make three different cases that should be defined as 1: to fit the pattern of multiplication and division; to fit the equations we derived for exponential growth; and because an empty product ought to be the identity since multiplication by it ought to have no effect. However, I never asked kids to entertain the three arguments simultaneously, or to ask if they shed different light on the conclusion, or if they generalized in different ways.
Proof number one: the Euclid-esque one
This is the proof given by a participant in answer to the problem I posed.
If root 5 were rational it could be written as a fraction in lowest terms, i.e. in which and are integers and do not have a common factor other than 1. Then it would be so that
and thus that
This would imply that is a multiple of 5. Since 5 is prime, this implies is a multiple of 5. Thus for some integer , and
Dividing by 5, this means
So is a multiple of 5, and, just as it did for , this means is a multiple of 5. But and were presumed to lack a common factor other than 1, so this is a contradiction, and the fraction for must fail to exist.
The covert reliance on unique prime factorization came out when I pushed the participants to justify the step “if is a multiple of 5, so is ” and they told me it was because ‘s prime factors are exactly ‘s duplicated; thus if 5 is not among ‘s prime factors it cannot be among ‘s. This reliance can be removed from the proof by finding another way to argue this point, but this is how the participants did it.
Proof number two: straight from unique factorization
Once we saw the secret reliance on unique factorization in the above proof, I offered this simpler proof (lifted more or less verbatim from Hardy and Wright’s compendiously awesome An Introduction to the Theory of Numbers):
if is the square root of 5, then is 5. If and are integers, then you can prime factorize the numerator and denominator of this fraction. The whole denominator needs to cancel because the quotient is an integer. Thus all ‘s prime factors are found among ‘s. But prime factorizations for and contain exactly the same primes as the prime factorizations of and (only twice as many of each prime). So all ‘s prime factors are found among ‘s, and is an integer. This is a contradiction since 5 is not the square of an integer. This proof generalizes in a natural way to show that it is not possible for any integer that is not a square to have a rational square root.
That’s as much as happened during the workshop. Everything worked perfectly in terms of my pedagogical intention to have the participants recognize how much they needed unique factorization to know what they know about numbers. This turns out to have been sheer luck. At dinner afterwards…
Proof number three: less than
This one was shown to me by Japheth Wood, a math professor at Bard College, who helped to organize the series.
Suppose is the positive square root of 5 and as in proof 1 suppose and are positive integers and the fraction is in lowest terms. This means is the smallest possible denominator for a fraction equal to root 5.
Now, 5 is between 4 and 9 which means that is between 2 and 3. Multiplying by we find that is between and , and subtracting we find that is between 0 and . In other words, is a positive integer less than b.
You may be able to see where this is headed. The assumption that is a square root of 5 is going to lead to a representation of root 5 as a fraction with in the denominator, which is impossible because was assumed to be in lowest terms, so that was the lowest possible denominator. How this happens is just some algebraic tricksiness:
This last expression was gotten by multiplying by 1 in the form of . But
since is 5, that’s the whole point of a square root. And now we can multiply numerator and denominator by to find
and poof! All this was equal to root 5; but now we have represented root 5 as a fraction with a denominator lower than the lowest possible denominator for such a fraction. This is a contradiction so our representation as a fraction in the first place was impossible.
Proof number four: way less than
This one was passed on to me from a participant named Barry. (Don’t know the last name. Barry if you happen to read this, claim your credit!)
is a positive real number between 0 and 1. Now, consider what happens when you raise it to powers.
On the one hand, since it is positive and less than 1, it will get arbitrarily small. (I.e. given any positive number, if you raise to a high enough power, it will be less than that number.)
But also, it will have the form (integer) + (integer)*.
This is happening because every pair of ‘s in the product make an integer. Thus, to any power must have the form , where and are integers.
All this is actually true about the square root of 5.
Now suppose root 5 could be written as a fraction with and integers. (This time we don’t have to assume lowest terms!) Then any power of would have the form .
The numerator of this fraction is an integer. The denominator is . This means the smallest positive number it can be is (or, if for some crazy reason you decided to use a negative , then ). Thus to any power would be greater than or equal to . But we already know it is capable of getting arbitrarily small by taking a high enough power, since is positive and less than 1. This contradiction proves that the square root of 5 can’t be a fraction.
Proof number five: unique factorization bonanza
This proof was relayed to me by Ted Diament. It’s more technical than the others; sorry about that. It’s using equipment much more powerful than is needed for the task. It is extremely cute though.
This one relies extra much on unique factorization. In fact, not only unique factorization of the integers, but unique factorization of the set of integer polynomials! Like integers, integer polynomials have factorizations into prime (irreducible) polynomials that are unique except for sign. (This fact follows from Gauss’ Lemma.) For example,
with each factor irreducible in the sense that it can’t be factored further (except in pointless ways like ). This factorization is unique in the sense that if you try to factor the original polynomial a different way, you will end up with the same set of factors, except possibly for some pairs of negative signs.
Anyway. Suppose root 5 were rational and equal to a fraction in lowest terms. Then would equal , and so the integer polynomial
Now the first of these factors into
while the second one factors into
But since they are equal, this violates the unique factorization of integer polynomials. Things would be fine if we could keep factoring both sides till they were identical (up to sign), but this isn’t possible: since was in lowest terms, and lack a common factor, so that and are irreducible. Also, is clearly irreducible since 5 is not an integer square. So the two factorizations are irrevocably distinct. Since integer polynomials only factor one way (up to sign), it must be that root 5 wasn’t rational after all.
I hope you enjoyed these. When they were shown to me I was just delighted by how different they all feel. I’d never seen anything except the first two, which feel very number-theory-ish to me. The last two feel much more algebraish. Proof number four even has a whiff of calculus what with all that “arbitrarily small” business. And all that is going on in the single fact of root 5’s irrationality!
Since for some reason this post continues to get a fair amount of traffic, I’ve got one more to add! This one occurred to me the other day as a purely algebraic reformulation of proof number four above (“way less than”). It’s higher-tech than any of the above, so apologies for that. I am adding this note in a hurry so I am not going to try to gloss the advanced concepts, so apologies for that too.
The ring is a finitely generated module over . In fact, it is generated by and . This is just another way of saying that everything that can be produced from integers and out of has the form with integers. This is a slight generalization of what was noted above in proof 4.
Meanwhile, if is any rational number that is not an integer, the ring can never be finitely generated as a -module, because it contains arbitrarily large denominators since has some nontrivial denominator and contains all ‘s powers. Again, this is essentially what was noted in proof 4. Putting these two paragraphs together, it follows that can’t be rational.
Ultimately the reason is finitely generated as a -module is that is an algebraic integer; thus this argument shows that an algebraic integer can never be rational unless it is an actual ordinary integer.