Denominadores comunes

Question

¿Existe una función para obtener todos los denominadores comunes (excepto por 1) de dos números? Creo que podría usar la suma, el límite inferior sería 1 y el límite superior sería el máximo común divisor, pero no estoy seguro.

Answer 1

Hay un algoritmo (no una fórmula) para encontrar todos los divisores comunes de dos enteros $a$ y $b$. Se divide en dos partes:

• Encontrar el máximo común divisor de $a$ y $b; esta parte es "fácil" (en el sentido computacional, es un algoritmo 'rápido').
• Encontrar todos los divisores del máximo común divisor; esta parte es computacionalmente difícil en general (toma mucho tiempo para números arbitrarios).

La clave es que el máximo común divisor de $a$ y $b$ satisface una propiedad universal con respecto a todos los divisores comunes: a saber, $d\gt 0$ es el máximo común divisor de $a$ y $b$ si y solo si:

1. $d$ divide $a$ y $d$ divide $b; y
2. Si $c$ es cualquier entero que divide $a$ y también divide $b, entonces también divide a$d$.

Para encontrar $d$, el máximo común divisor, puedes utilizar el Algoritmo de Euclides. Esto no requiere que factorices ni $a$ ni $b, solo realiza restas.

Una vez que encuentres $d$, los divisores comunes de $a$ y $b$ son precisamente los divisores de $d; para encontrar todos los divisores de $d, generalmente se necesita factorizar $d$ en números primos; esto es computacionalmente difícil, pero puede hacerse por muchos métodos conocidos.

Answer 2

En primer lugar, no hay un denominador común más grande (existe el máximo común divisor). Tal vez quisiste decir el denominador común más bajo o el máximo común divisor.

Creo que quisiste decir el segundo, ya que mencionas $1$. Entonces, quieres encontrar todos los divisores comunes de $a,b$. Luego, denota por $c=\gcd(a,b)$. Elige $d |a, d|b$ un divisor común. Entonces $d| ka+lb$ para todos los $k,l \in \Bbb{Z}$. Existe un teorema que afirma que existen $k_0,l_0$ tales que $ak_0+bl_0=c$. Por lo tanto, $d|c$. Todos los divisores comunes son divisores del máximo común divisor. Para encontrarlos todos, no hay una fórmula general, pero si tienes ejemplos concretos, los cálculos no son muy difíciles.

Answer 3

Para obtener los factores comunes (divisores si es necesario) de dos números, un enfoque es tomar sus factorizaciones primas y luego ver qué exponentes tienen en común. Por ejemplo, toma 48 y 180:

• $48 = 2^4 \times 3^1$
• $180 = 2^2 \times 3^2 \times 5^1$

Así que el factor común más alto es $2^2 \times 3^1 \times 5^0 = 12$. Para encontrar todos los factores comunes de 48 y 180 (es decir, los factores de 12), puedes usar exponenciales más bajas de los primos, por lo que puedes elegir $2^0$, $2^1$ o $2^2$, y multiplicar esto por $3^0$ o $3^1$, haciendo seis posibilidades, es decir, $1$, $2$, $3$, $4$, $6$ o $12$.