Gauss' Lemma Without Explicit Divisibility Arguments
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