# Determine if $(p/q)^{a/b}$ is rational

I know, in general, that it isn't true. ${\frac{2}{1}}^{1/2}$ is irrational. I'm only interested in this where $\frac{p}{q}$ and $\frac{a}{b}$ are positive, but to make this even simpler, lets just say that $a,b,p,q \in \mathbb{N}$.

I'm curious to know if there's an algorithm for figuring it out within the bounds I've mentioned, but I'm even more curious to know if it's true in general if you place additional constraints on the numbers.

-
Yep. If $(p, q) = 1$ and $(a, b) = 1$ then this is true if and only if every exponent in the prime factorization of both $p$ and $q$ are divisible by $b$, and this is straightforward to prove using prime factorization. – Qiaochu Yuan Mar 30 '12 at 22:17
I'm not sure what you mean by putting them in parentheses like that. – Andy Shulman Mar 30 '12 at 22:18
It refers to the greatest common divisor: en.wikipedia.org/wiki/Greatest_common_divisor – Qiaochu Yuan Mar 30 '12 at 22:23
He means the fractions $p/q$ and $a/b$ are in lowest terms. But of course he writes it in a way that non-mathematicians don't understand. – GEdgar Mar 30 '12 at 23:40
In fairness, I use that notation so often that I've completely forgotten how obnoxious I thought it was when I first saw it :) – Ben Millwood Jun 3 '12 at 8:52

Assume that $p$, $q$, $a$, and $b$ are positive integers. By dividing $a$ and $b$ by $\gcd(a,b)$ (found, say, by using the Euclidean Algorithm), we may further assume that $a$ and $b$ are relatively prime. Similarly, we may also assume that $p$ and $q$ are relatively prime. If they are not, first divide each by $\gcd(p,q)$.

So from now on assume that $\gcd(a,b)=\gcd(p,q)=1$.

Then $\left(\dfrac{p}{q}\right)^{a/b}$ is a rational number if and only if the exponent of each prime in the prime factorization of $p$ and of $q$ is divisible by $b$. Equivalently, $\left(\dfrac{p}{q}\right)^{a/b}$ is a rational number iff each of $p$ and $q$ is a perfect $b$-th power.

The Euclidean Algorithm is cheap and fast. That is not the case for factorization. However, by a suitable adaptation of Newton's Method, we can find out efficiently whether $p$ and $q$ are perfect $b$-th powers. We can also do it by adapting the old algorithm for square root that used to be taught in the schools. Detecting whether something is a $b$-th power can be done in not much more than linear time.

-
But there's really no way to efficiently figure out the prime factorization of a number... – Andy Shulman Mar 30 '12 at 22:22
@Andy: mathematicians distinguish between "algorithm" and "efficient algorithm." If you want an efficient algorithm, you have to ask us for an efficient algorithm! – Qiaochu Yuan Mar 30 '12 at 22:24
My apologies! I don't really need something efficient, per se, just something that won't take twenty times the lifetime of the sun for a 4000-bit number :) – Andy Shulman Mar 30 '12 at 22:25
Andy: There is no known efficient way to factor, but there is an efficient way to check if a number is a perfect power, and answer whether $(a/b)^{p/q}$ is rational given $a,b,p,q$. To check if $n$ is a perfect power, check for every $b=2,3,\dots,\log_2 n$ whether there is an integer $a$ such that $n=a^b$, using e.g. binary search in $[1,n]$. – sdcvvc Mar 30 '12 at 22:30
Irrationality is all around us. The only thing I can suggest is to delay evaluations as long as possible. – André Nicolas Mar 30 '12 at 23:08

André's answer shows that this is true if and only if $p$ and $q$ are both $b^{th}$ powers, so the problem reduces to the following problem: how do you tell if a positive integer $p$ is a $b^{th}$ power for a particular value of $b$?

Fortunately, you can do this efficiently and without factoring $p$, the key identity being $$p^{ \frac{1}{b} } = e^{ \frac{\ln p}{b} }.$$

If you have an efficient method for computing logarithms (and I assume these are easy to find even though I'm not familiar with them) then you just need to compute $\ln p$ to enough precision that you can get a reasonably good estimate of $e^{ \frac{\ln p}{b} }$. From there, you can round to the nearest two integers and take those integers to the power of $b$, then compare them to $p$. If either of them is equal to $p$, then $p$ is a $b^{th}$ power, but if $p$ is between them, then it isn't.

-

Hint $\$ By lemma below $\rm\:(P/Q)^{A/B}\in\mathbb Q\iff (P/Q)^{\:\!1/B}\in\mathbb Q\iff \smash[b]{\dfrac{P}Q = \dfrac{M^B}{N^B}}\:$ for $\rm\:M,N\in\mathbb Z$

Lemma $\$ Let $\rm\:A,B\in \mathbb Z.\:$ Then $\rm\ C, C^{A/B}\in \mathbb Q\iff C^{1/B}\in \mathbb Q\ \$ for $\rm\ C\ne 0$

Proof $\rm\ (\Leftarrow)\ \ \ C^{\:\!1/B}\in\mathbb Q\ \Rightarrow\ C = (C^{\:\!1/B})^B\in\mathbb Q,\:$ and $\rm\: C^{A/B} = (C^{\:\!1/B})^A\in\mathbb Q$

$\rm (\Rightarrow)\ Wlog\ (A,B)=1\:$ so Bezout $\rm\Rightarrow\ J\:A+K\:B = 1\:$ for some $\rm\:J,K\in \mathbb Z.\:$ Therefore

$$\rm C^{\:\!1/B} = C^{(JA+KB)/B} = (C^{A/B})^J C^K \in \mathbb Q\ \ \ by\ \ \ C^{A/B},\ C\in\mathbb Q\qquad QED$$

Remark $\$ The Lemma uses only the multiplicative group structure of $\mathbb Q,\:$ so it generalizes to any multiplicative subgroup $\rm Q$ of $\mathbb C$.

-