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.