¿Un número divisible por todos los factores primos de otro?

Question

Dados dos números $x$ y $y$ cómo comprobar si $x$ es divisible por todo factores primos de $y$ o no?, ¿hay alguna forma de hacerlo sin factorizar $y$ ?.

Answer 1

$x$ es divisible por todos los factores primos de $y$ si y sólo si para algún $n$ , $x^n\equiv0$ modulo $y$ . Se puede calcular $x^n$ modulo $y$ para $n=1$ hasta decir $\log_2(y)$ y ver si $0$ surge como resultado. Para los números grandes, en los que la factorización primaria es difícil, pero la aritmética modular es factible, esto sería más eficiente que la factorización primaria. Yo digo $\log_2(y)$ porque es un límite superior para cualquier exponente de un factor primo de $y$ en la factorización primaria de $y$ . Así que en el momento en que usted ha planteado $x$ a esa potencia, cualquier factor primo de $x$ se elevará entonces a una potencia al menos tan grande como la que podría surgir en la factorización primaria de $y$ .

@Joffan señala en los comentarios que se podría saltar a solo subir a la $\log_2(y)$ poder. Si utilizas la cuadratura repetida, acelera las cosas a $\log_2\log_2(y)$ multiplicaciones modulo $y$ . De hecho, elevando aún más a la siguiente potencia de $2$ ahorra un paso o dos aquí y allá.

Aplicado a los ejemplos de Mark, este proceso sería así: $$\begin{align} x=168,y=132&\rightarrow \lfloor\log_2(y)\rfloor=7\rightarrow\text{8 is the next power of 2}\\ &\phantom{\rightarrow \lfloor\log_2(y)\rfloor=7\rightarrow}\text{Explicitly, $8=2^{\lceil\log_2{ \lfloor\log_2(y)\rfloor}\rceil}$}\\ &\rightarrow 168^8=((168^2)^2)^2\\ &\rightarrow 168^8\equiv(108^2)^2\\ &\rightarrow 168^7\equiv72^2\\ &\rightarrow 168^7\equiv144\\ \end{align}$$ que utiliza tres cuadrículas mod $y$ para determinar que la respuesta es no. Y $$\begin{align} x=168,y=98&\rightarrow \lfloor\log_2(y)\rfloor=6\rightarrow\text{8 is the next power of 2}\\ &\rightarrow 168^8=((168^2)^2)^2\\ &\rightarrow 168^8=(0^2)^2\\ &\rightarrow 168^8=0^2\\ &\rightarrow 168^8\equiv0\\ \end{align}$$ que técnicamente utiliza tres escuadras si no vemos los primeros $0$ para determinar que la respuesta es sí. (O puede hacer que el algoritmo compruebe cada paso para ver si hay ceros tempranos si lo desea--no se ahorra mucho tiempo sin embargo al evitar algunos cálculos de $0^2$ .)

Answer 2

Si $x$ es divisible por todos los factores primos de $y$ entonces también lo es el mayor factor común $h_1$ de $x$ y $y$ .

Para comprobar si $y$ tiene un factor primo $p$ que no es un factor de $x$ - entonces $p$ no es un factor de $h_1$ pero será un factor de $y_1$ donde $y=y_1h_1$ . Sea $h_2$ sea el mayor factor común de $h_1$ y $y_1$ y $y_1=h_2y_2$ . Entonces $y_2$ conservará cualquier factor primo $p$ que no es un factor de $x$ y esto no será un factor de $h_2$ .

El $h_i$ son enteros positivos decrecientes, por lo que el proceso termina. Si algún $h_i=1$ con $y_i\gt 1$ entonces $y$ tiene un factor primo que $x$ no lo hace. En caso contrario, todos los factores primos de $y$ también deben ser factores primos de $y$ .

---

Para ilustrar con $x=168, y=132$ tenemos $h_1=12, y_1=11$ y $h_2=1, y_2=11$ detecta un problema.

Con $x=168, y=98$ tenemos $h_1=14, y_1=7$ y luego $h_2=7, y_2=1$ y $h_3=1, y_3=1$ y todos los factores primos de $y$ son factores de $x$ .

Obsérvese que el hcf se puede determinar por el algoritmo euclidiano, sin factorizar $y$ .

Answer 3

Hay un algoritmo bastante sencillo basado en gcd.

1. $c := \gcd(x,y)$ .
2. $z := y / c$ .
3. Si $z = 1$ terminar. Todos los factores primos de y estaban también en $x$ .
4. $c := \gcd(x,z)$ .
5. Si $c = 1$ terminar. $z > 1$ y $z$ divide $y$ pero ningún factor primo de $z$ divide $x$ .
6. $z := z / c$ .
7. Ir a 3. $z$ dimite en cada iteración, por lo que se garantiza la terminación.