[FOM] Perfect Powers

[Vaughan Pratt]

On 1/1/2011 9:02 AM, A. Mani wrote:
> I was thinking of the following constructive proof:
>
> Let p^{1/q} = m/n with (m,n) = 1, n>  0;
>
> and c= n(p^{1/q} - f(p^{1/q}))  (f being the floor fn)

But your c is merely what I was calling m mod n.  It seemed clear from 
your mention of "floor" that your proof would have to pass through this 
point at least.

Your proof then continues for a further 8 lines:

 > Since 0 \leq (p^{1/q} - f(p^{1/q}))<  1
 >
 > 0 \leq c<  n   [in other words 0  <=  m mod n  <  n]
 >
 > But c (m/n)^{q-1} = c(p^{1/q})^{q-1} =
 > = n(p^{1/q})^{q} - nf(p^{1/q}) (m/n)^{q-1}
 >
 > Multiplying both sides of the eqn by n^{q-2}, we get
 >
 > (c m^{q-1}) /n  = (n^{q-1})p - f(p^{1/q}) m^{q-1} (an integer)
 >
 > So, n | cm^{q-1} =>  n|c
 >
 > But c \in [0,n) =>  c = 0

when you could have gotten there more "directly" (your word) via my 
argument "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."

 > In that form, the proof does not fit as the equivalence requires
 > existential quantifiers.

Whatever that means, how does it justify your much longer proof?  I had 
never thought of the reduced residue system mod n as being somehow 
either "nonalgebraic" (it is a finite abelian group, how is that 
nonalgebraic?) or "nonconstructive" (for which you offered no criterion 
- what is "nonconstructive" about the Euler totient function when it has 
an explicit recursive formula?).

Vaughan Pratt