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.

  • 1
    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.2012-03-30
  • 0
    I'm not sure what you mean by putting them in parentheses like that.2012-03-30
  • 0
    It refers to the greatest common divisor: http://en.wikipedia.org/wiki/Greatest_common_divisor2012-03-30
  • 0
    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.2012-03-30
  • 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.

  • 0
    But there's really no way to efficiently figure out the prime factorization of a number...2012-03-30
  • 1
    @Andy: mathematicians distinguish between "algorithm" and "efficient algorithm." If you want an efficient algorithm, you have to ask us for an efficient algorithm!2012-03-30
  • 1
    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 :)2012-03-30
  • 0
    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]$.2012-03-30
  • 0
    @Andy: when mathematicians want to talk about the prime factorization of a number, we usually write it as $p_1^{a_1}p_2^{a_2}\dotsb p_k^{a_k}$ where the $p_i$ are prime numbers and the $a_i\geq 1$. This allows us to reason about the prime factors without actually knowing them. If you're looking for a computer implementation asking for a mathematical proof isn't the best way to do so.2012-03-30
  • 0
    @chris, I'm probably capable of developing an implementation from a proof. I'm just not as knowledgeable in the theory.2012-03-30
  • 0
    It's too bad, really. I was working on a complicated numerical problem, and I was hoping to keep the result rational, even after rational exponentiation.2012-03-30
  • 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$.