Encontrar número de divisores comunes de 463050 y 2425500

Question

Soy nuevo en la combinatoria (segunda lección del curso) y me preguntaba cómo resolver el siguiente problema de la forma más elegante:

Encontrar el número de divisores comunes para 463050 y 2425500?

Mi intuición me dice que dividir ambos números por 10 que me llevará a la 5 y la 2, pero tengo la sensación de que hay alguna otra manera.

Gracias a toda la clase ayudantes.

p.s agradezco respuesta sencilla, y se aprecia aún más una guía sobre cómo resolver este tipo de problemas en el futuro.

Answer 1

Estrategia: Cada divisor común es un divisor el máximo común divisor, por lo que debemos encontrar el máximo común divisor, a continuación, determinar cómo muchos factores que tiene.

1. Usar el Algoritmo de Euclides para encontrar el máximo común divisor.
2. Factor el máximo común divisor en números primos.
3. Si el máximo común divisor tiene la factorización prima $$p_1^{\alpha_1}p_2^{\alpha_2} \ldots p_n^{\alpha_n}$$ a continuación, un divisor común ha factorización $$p_1^{\beta_1}p_2^{\beta_2} \ldots p_n^{\beta_n}$$ donde$0 \leq \beta_k \leq \alpha_k$$1 \leq k \leq n$, por lo que el número de divisores del máximo común divisor es $$(\alpha_1 + 1)(\alpha_2 + 1) \ldots (\alpha_n + 1)$$

Answer 2

Entre todos los divisores comunes de los dos números hay uno mayor, y esto se puede calcular fácilmente:$$\gcd(463050, 2425500)=22050$ $ La factorización primaria de este número es$$22050=2^13^25^27^2$ $ por lo que el número de divisores comunes es$$\tau(22050)=(1+1)(2+1)(2+1)(2+1)=54$ $ Donde$\tau(n)$ es la función número de divisores.

Answer 3

El simple algoritmo de Euclides da el máximo común divisor (mcd) de dos números:

$\begin{array}{r|cc} n\quad & q \\ \hline 2425500 & \\ 463050 & 5 \\ 110250 & 4 \\ 22050 & 5 \\ 0 & \\ \end{array}$

con $q$, siendo la división de enteros de la actual y anterior $n$ valores que indica el múltiplo de los más pequeños de la resta formar la más grande para llegar a la próxima $n$ valor, por ejemplo. $463050 - 4\times 110250 = 22050$. El último número antes de llegar a $0$ es el máximo común divisor. Un número se divide este número, $22050$, si y sólo si ese número se divide tanto a a$2425500$$463020$.

Luego, afortunadamente, de factorización $22050$ es fácil por la prueba de la división, dando a $22050 = 2\cdot 3^2\cdot 5^2\cdot 7^2$ y el número de divisores para este número puede obtenerse en la forma habitual por el producto de uno más de cada primer exponente, $2\cdot3\cdot 3\cdot 3=54$

En este caso, el factoring por la división de juicios podrían haber sido utilizados en los números originales también, y el menos común de primer poderes ofrecen otra ruta para obtener el mcd.