relación entre el conjunto de divisores primos de dos enteros positivos

Question

Cómo decir de la manera más eficiente que el conjunto de divisores primos de un entero positivo M es un superconjunto del conjunto de divisores primos de otro entero positivo N donde M y N son números bastante grandes.

Estos conjuntos no contienen ningún duplicado.

Answer 1

Dejemos que $N_0=N$ y $M_0=M$ y $D_0=\gcd(M_0,N_0)$ .

Entonces para $i\ge 1$ , dejemos que $N_i=\frac{N_{i-1}}{D_{i-1}}$ , $M_i=D_{i-1}$ y $D_i=\gcd(M_i,N_i)$ .

Si llegas a $N_i=1$ entonces sí (divisores primos de $M$ son un superconjunto de divisores primos de $N$ ); pero si llega a $D_i=1$ con $N_i\ne 1$ La respuesta es no.

Ejemplo:

$M=30, N=288$

$$\begin{array}{c|c|c} N&M&D\\ \hline 288&30&6\\ 48&6&6\\ 8&6&2\\ 4&2&2\\ 2&2&2\\ 1&2&1 \end{array}$$ Sí: factores primos de $30$ son un superconjunto de factores primos de $288$ .

Ejemplo:

$M=30, N=2520$ $$\begin{array}{c|c|c} N&M&D\\ \hline 2520&30&30\\ 84&30&6\\ 14&6&2\\ 7&2&1\\ \end{array}$$

Factores primos de $30$ no son un superconjunto de factores primos de $2520$ .

Desde $N$ se reduce al menos a la mitad en cada paso, este método parece bastante eficiente.