[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