4
$\begingroup$

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.

  • 0
    In fairness, I use that notation so often that I've completely forgotten how obnoxious I thought it was when I first saw it :)2012-06-03

3 Answers 3

7

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.

  • 1
    Irrationality is all around us. The only thing I can suggest is to delay evaluations as long as possible.2012-03-30
3

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.

2

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$.