Number Theory – Rationality Test for a Rational Power of a Rational Number

irrational-numbersnumber theory

It has been known since Pythagoras that 2^(1/2) is irrational. It is also obvious that 4^(1/2) is rational. There is also a fun proof that even the power of two irrational numbers can be rational.

Can you, in general, compute whether the power of two rational numbers is rational?

The reason I am asking, besides curiosity, is that the Fraction-type in Python always returns a float on exponentiation. If there is a quick way to tell if it could be accurately expressed as a fraction, the power function could conceivably only return floats when it has to.

EDIT:
By popular demand, I changed 0.5 to 1/2 to make it clearer that it is a fraction and not a float.

Best Answer

We can do this much quicker than using prime factorization. Below I show how to reduce the problem to testing if an integer is a (specific) perfect power - i.e. an integer perfect power test.

Lemma $\ $ If $\rm\,R\,$ and $\,\rm K/N\:$ are rationals, $\rm\:K,N\in\mathbb Z,\ \gcd(K,N)=1,\,$ then $$\rm\:R^{K/N}\in\Bbb Q\iff R^{1/N}\in \mathbb Q\qquad$$

Proof $\ (\Rightarrow)\ $ If $\,\rm\color{#0a0}{R^{K/N}\in\Bbb Q},\,$ then by $\rm\:gcd(N,K) = 1\:$ we have a Bezout equation

$$\rm 1 = JN+I\:\!K\, \overset{\!\div\ N}\Rightarrow\ 1/N = J + IK/N\ \Rightarrow\ R^{1/N} =\ R^J(\color{#0a0}{R^{K/N}})^I \in \mathbb Q$$

$(\Leftarrow)\ \ \rm\:R^{1/N}\in \mathbb Q\ \Rightarrow\ R^{K/N} = (R^{1/N})^K\in \mathbb Q.\ \ \small\bf QED$

So we've reduced the problem to determining if $\rm\:R^{1/N} = A/B \in \mathbb Q.\,$ If so then $\rm\: R = A^N/B^N\:$ and $\rm\:gcd(A,B)=1\:$ $\Rightarrow$ $\rm\:gcd(A^N,B^N) = 1,\:$ by unique factorization or Euclid's Lemma. By uniqueness of reduced fractions, this is true iff the lowest-terms numerator and denominator of $\rm\:R\:$ are both $\rm\:N'th\:$ powers of integers.

So we reduce to the problem of checking if an integer is a perfect power. This can be done very quickly, even in the general case, see D. J. Bernstein, Detecting powers in almost linear time. 1997.

Related Question