[FOM] Perfect Powers

Vaughan Pratt pratt at cs.stanford.edu
Fri Dec 31 01:06:37 EST 2010

What does it mean for a proof to be "algebraic?"

Since the prime factorization theorem can be proved in a couple of 
lines, I'm not sure what to make of your "much simpler."  But from your 
mention of floor I imagine you must have essentially the following proof 
in mind.

Given p^{1/q} = m/n with (m,n) = 1, n > 0, we want to show n = 1.  So 
suppose to the contrary that n >= 2.  Then p = (m/n)^q, so pn^q = m^q. 
Hence m^q mod n = 0.  But since m is in the reduced residue system mod 
n, so is m^q whence it cannot be zero there.  QED.

One does not need the prime factorization theorem to show that the 
reduced residue system mod n forms a group under multiplication.

Vaughan Pratt

On 12/28/2010 2:49 PM, A. Mani wrote:
> Let Q be the ordered field of rationals with usual operations (+, ., -, -1,
> \vee, \wedge, 0, 1) (\vee, \wedge  are used for the total order to make it an
> algebra).
> For p, q \in N, the well known result:
> p^{1/q} is rational iff p is a perfect qth power
> is typically proved via the prime factorization theorem.
> But it can also be proved by much simpler direct methods provided an
> additional 'non-algebraic' function F: Q ->  N is permitted. E.g floor or
> ceiling function (these are not term or polynomial functions w.r.t the basic
> operations assumed).
> Can the latter proof be made algebraic?

More information about the FOM mailing list