One way of proving the irrationality of the square root of 2 is to suppose q is the smallest positive integer such that q*sqrt(2) is an integer, from which it follows that q*(sqrt(2)-1) is a smaller positive integer with the same property - a contradiction. Of course, this method relies on the fact that 1 < Sqrt(2) < 2, but this doesn't mean that it's applicability is limited to just the square root of 2. Indeed, the same approach proves that the square root of ANY non-square integer is irrational. PROOF: Let C be any non-square positive integer, and let M be the largest integer less than sqrt(C). If sqrt(C) is rational there exists a smallest positive integer N such that N sqrt(C) is an integer. It follows that N' = N [sqrt(C) - M] is a positive integer less than N, and clearly N' sqrt(C) = N [sqrt(C) - M] sqrt(C) = N C - M [N sqrt(C)] is an integer, contradicting the fact that N is the smallest such integer. DONE. Of course, the more general fact that the kth root of any non-kth- power must be irrational follows instantly from unique factorization of integers, because if p/q = N^(1/k) then p^k = N q^k, which is impossible unless N is a kth power. Nevertheless, the above proof is interesting because it doesn't rely explicitly on unique factorization or divisibility arguments. (Needless to say, if unique factorization didn't hold, then the theorem wouldn't be true, so in a sense we require unique factorization, regardless of how we carry out the proof. However, the idea is to prove the theorem without explicitly invoking the fundamental theorem of arithmetic or some equivalent of it.) Is it possible to give a proof of the general proposition for kth roots without invoking divisibility arguments? By analogy with the above proof for square roots, we might try to generalize the argument as follows: PROOF: We've seen that the square of a rational non-integer r cannot be an integer, and we can use this to start an induction, showing that if no r^(k-1) can be an integer, then no r^k can be an integer. Consider a polynomial of the form f(x) = x^k - C where C is an integer, and suppose r is a positive non-integer rational root of f. We know that r^(k-1) is not an integer, so there must exist an integer M such that 0 < [r^(k-1) - M] < 1 Also, since r^(k-1) is rational, there exists a smallest positive integer N such that N r^(k-1) is an integer. But this implies the quantity N' = N [r^(k-1) - M] is also a positive integer, and it is smaller than N. Further, we have N' r^(k-1) = N [ r^(k-1) - M ] r^(k-1) = N [ r^(2(k-1)) - M r^(k-1) ] = [ N r^(k-2) ] C - M [ N r^(k-1) ] which is an integer. (Notice that if N r^(k-1) is an integer, then so is N r^(k-2).) But since N' < N, this contradicts the premise that N is the smallest integer such that N r^(k-1) is an integer. DONE. Admittedly the integer character of N r^(k-2) is most easily seen by divisibility considerations, but we can also use an induction to avoid explicit reference to unique factorization. We could also consider the more general question of whether it's possible to prove, without invoking unique factorization, that any root of a monic polynomial f(x) of degree k with integer coefficients must either be an integer or irrational (which is essentially Gauss' Lemma). Note that if f(x) has constant coefficient C, then we can define a polynomial g(x) of degree k-1 as follows g(x) = ( f(x) - C ) / x If r is a non-integer rational root of f, then f(r) = 0 and so we have g(r) = -C/r. As before, we can use an induction based on the fact that no algebraic integer of degree k-1 is rational and non-integer, and then show that this applies to algebraic integers of degree k as well. Thus, since g(r) is of degree k-1 we know that g(r) is not an integer (because if it was an integer, r would be of degree k-1 rather than of degree k), so we can choose an integer M such that 0 < (g(r) - M) < 1 Then since g(r) is clearly rational, there must be a smallest integer N such that N g(r) is an integer. In fact, this implies that N times ANY polynomial in r of degree k-1 is an integer (because if an integer N can clear the fractions of g(r) it can also clear the fractions of any polynomial in r of the same degree). From this it's clear that N' = N (g(r) - M) is also an integer, and it is smaller than N. Furthermore, we have N' g(r) = N (g(r) - M) g(r) = N g(r)^2 - M N g(r) We can say this is an integer because we can express g(r)^2 as a polynomial of degree k-1 simply substituting for the highest term from f(r). For example, if f(x) = x^3 - 3x^2 + 7x - 5 then we have g(x) = x^2 - 3x + 7 Also, if r is a root of f, then we have r^3 = 3r^2 - 7r + 5 and so the expression g(r)^2 can be reduced to a polynomial of degree 2 as follows g(r)^2 = r^4 - 6r^3 + 23r^2 - 42r + 49 = r^3 ( r - 6 ) + 23r^2 - 42r + 49 = [3r^2 - 7r + 5](r-6) + 23r^2 - 42r + 49 = (3r^3 - 25r^2 + 47r - 30) + 23r^2 - 42r + 49 = 3[3r^2 - 7r + 5] - 2r^2 + 5r + 19 = 7r^2 - 16r + 34 Basically this is just evaluating the polynomial modulo f(x) (which is just algebra, not a divisibility argument per se) and the same applies to any polynomial in r. Consequently our value of N' gives a contradiction. DONE Incidentally, if we are willing to invoke divisibility arguments, another way of showing that g(r) is not an integer is to note that g(r) = C/r, so it is not an integer iff the *numerator* of r does not divide the constant coefficient C. It isn't immediately obvious how to rule this out (aside from the argument given above). However, since f is monic, the "reversed" polynomial with roots 1/r has a constant coefficient of C=1, and so we can prove that 1/r is irrational assuming the *denominator* of r does not divide 1, which is certainly true if the denominator is greater than 1, i.e., if r is not an integer. Thus, we've proven Gauss's lemma...with and without explicit divisibility arguments.

Return to MathPages Main Menu