Determinar si $(p/q)^{a/b}$ es racional

Question

Sé que, en general, que no es cierto. ${\frac{2}{1}}^{1/2}$ es irracional. Sólo estoy interesado en este donde $\frac{p}{q}$ $\frac{a}{b}$ son positivas, pero para hacer esto aún más simple, le acaba de decir que $a,b,p,q \in \mathbb{N}$.

Tengo curiosidad por saber si existe un algoritmo para calcular hacia fuera dentro de los límites que he mencionado, pero estoy aún más la curiosidad de saber si es cierto en general si restricciones adicionales sobre los números.

Answer 1

Suponga que $p$, $q$, $a$, y $b$ son enteros positivos. Dividiendo $a$ $b$ $\gcd(a,b)$ (que se encuentra, por ejemplo, utilizando el Algoritmo de Euclides), que además puede suponer que $a$ $b$ son relativamente primos. Del mismo modo, también podemos suponer que $p$ $q$ son relativamente primos. Si no lo están, primero divide cada uno por $\gcd(p,q)$.

Así que a partir de ahora suponga que $\gcd(a,b)=\gcd(p,q)=1$.

A continuación, $\left(\dfrac{p}{q}\right)^{a/b}$ es un número racional si y sólo si el exponente de cada una de las prime en la factorización prima de $p$ e de $q$ es divisible por $b$. Equivalentemente, $\left(\dfrac{p}{q}\right)^{a/b}$ es un número racional iff cada una de las $p$ $q$ es una perfecta $b$-ésima potencia.

El Algoritmo de Euclides es barato y rápido. Que no es el caso de factorización. Sin embargo, por una adecuada adaptación del Método de Newton, podemos encontrar de manera eficiente si $p$ $q$ son perfectos $b$-th poderes. También podemos hacerlo por la adaptación de la antigua algoritmo de la raíz cuadrada que se enseñaban en las escuelas. Detectar si algo es un $b$-th poder se puede hacer en no mucho más que el tiempo lineal.

Answer 2

André respuesta demuestra que esto es cierto si y sólo si $p$ $q$ ambos $b^{th}$ poderes, por lo que el problema se reduce al siguiente problema: ¿cómo puede usted saber si un entero positivo $p$ $b^{th}$ de la potencia para un determinado valor de $b$?

Afortunadamente, usted puede hacer esto de manera eficiente y sin factoring $p$, la clave de la identidad $$p^{ \frac{1}{b} } = e^{ \frac{\ln p}{b} }.$$

Si usted tiene un método eficaz para calcular logaritmos (y supongo que estos son fáciles de encontrar, incluso aunque no estoy familiarizado con ellos), entonces usted sólo tiene que calcular $\ln p$ a una cantidad suficiente de precisión que se puede obtener una razonablemente buena estimación de $e^{ \frac{\ln p}{b} }$. Desde allí, usted puede redondear a la unidad más cercana de dos enteros y tomar los números enteros a la potencia de $b$, luego compararlas $p$. Si cualquiera de ellos es igual a$p$, $p$ $b^{th}$ de la potencia, pero si $p$ está entre ellos, entonces no lo es.

Answer 3

Sugerencia $\ $ Por lema debajo de $\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}}\:$ $\rm\:M,N\in\mathbb Z$

Lema $\ $ Deje $\rm\:A,B\in \mathbb Z.\:$ $\rm\ C, C^{A/B}\in \mathbb Q\iff C^{1/B}\in \mathbb Q\ \ $ $\rm\ C\ne 0$

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

$\rm (\Rightarrow)\ Wlog\ (A,B)=1\:$ , por lo que Bezout $\rm\Rightarrow\ J\:A+K\:B = 1\:$ algunos $\rm\:J,K\in \mathbb Z.\:$ por lo Tanto

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

Comentario $\ $ El Lema utiliza sólo el multiplicativo grupo de estructura de $\mathbb Q,\:$, por lo que se generaliza a cualquier multiplicativo subgrupo $\rm Q$$ \mathbb C$.