Dado el MCD y el MCM de n enteros positivos, ¿cuántas soluciones hay?

Question

Dado el MCD y el MCM de n enteros positivos, ¿cuántas soluciones hay?

gcd-y-lcm
Matemáticas
combinatoria
teoría de los números
solicitud de referencia

Benjamín Dickman

Pregunta: Supongamos que sabes $G:=\gcd$ (máximo común divisor) y $L:=\text{lcm}$ (mínimo común múltiplo) de $n$ enteros positivos; ¿Cuántos conjuntos de soluciones existen?

En el caso de $n = 2$ , se encuentra que para el $k$ primos distintos que se dividen $L/G$ , hay un total de $2^{k-1}$ soluciones únicas.

Estoy feliz de escribir una prueba de la $n = 2$ caso si es deseable, pero mi pregunta aquí se refiere a la versión más general. El $n=3$ El caso ya resultó espinoso en mis exploraciones, por lo que me complacería ver casos más pequeños resueltos, incluso si los que responden no están seguros de la generalización completa.

Alternativamente: si ya existe una referencia existente a este problema y su solución, ¡también sería muy bienvenido un indicador de dicha información!

Benjamín Dickman

@Yorch Su comentario solo vincula a la pregunta en el caso de que

n = 2

$n=2$ ; para mí, ¡este caso no fue un problema! Estoy preguntando, específicamente, sobre el caso general : donde tienes números enteros positivos

{a_{1}, \dots, a_{n}}

$\{a_1, \ldots, a_n\}$ .

Asinomás

requieres que el

n

$n$ enteros positivos ser distintos? ¿Estás tratando de contar los conjuntos múltiples? Creo que es la única versión que no he podido resolver.

Benjamín Dickman

@Yorch No se requiere que los enteros sean distintos y/pero (¡idealmente!) que cuenten soluciones distintas. Si cree que puede hacer tracción en una versión modificada (es decir, imponer restricciones adicionales), entonces me complacería ver qué se le ocurre.

Respuestas (2)

Dado el MCD y el MCM de n enteros positivos, ¿cuántas soluciones hay?

@Yorch Su comentario solo vincula a la pregunta en el caso de que $n=2$ ; para mí, ¡este caso no fue un problema! Estoy preguntando, específicamente, sobre el caso general : donde tienes números enteros positivos $\{a_1, \ldots, a_n\}$ .
requieres que el $n$ enteros positivos ser distintos? ¿Estás tratando de contar los conjuntos múltiples? Creo que es la única versión que no he podido resolver.
@Yorch No se requiere que los enteros sean distintos y/pero (¡idealmente!) que cuenten soluciones distintas. Si cree que puede hacer tracción en una versión modificada (es decir, imponer restricciones adicionales), entonces me complacería ver qué se le ocurre.

Asinomás · Answer 1

Si te interesa contar tuplas $(a_1,a_2,\dots,a_n)$ tal que $\gcd(a_1,\dots,a_n) = G$ y $\operatorname{lcm}(a_1,\dots,a_n) = L$ entonces podemos hacerlo de la siguiente manera.

Si $L/G = \prod\limits_{i=1}^s p_i^{x_i}$ entonces cada uno $a_i$ debe ser de la forma $G \prod\limits_{j=1}^s p_i^{y_{i,j}}$ con $0 \leq y_{i,j} \leq x_i$ .

Por lo tanto para cada primo $p_i$ requerimos que la función de $\{1,\dots, n\}$ a $\mathbb N$ que envía $j$ a $y_{i,j}$ ser una función que golpea $0$ y $x_i$ .

El número de tales funciones es fácil por inclusión-exclusión para $x_i \geq 1$ , es $(x_i+1)^n - 2(x_i)^n + (x_i-1)^n$ .

De ello se deduce que el número total de tuplas es $\prod\limits_{i=1}^s ( (x_i+1)^n - 2x_i^n + (x_i-1)^n)$ .

Contando tuplas como en, con repetición, ¿no? P.ej $(1,2)$ y $(2,1)$ ¿Se contaría cada uno en su cálculo? Si es así, ¿no es cierto que (usando su notación) podría asignar el $s$ primos distintos (a sus diversas potencias) como divisores de cualquiera de los $n$ números enteros o un subconjunto de ellos (por ejemplo, a $\{a_1, a_3, a_7\}$ )? Hay $2^n$ subconjuntos de $\{a_1, \ldots, a_n\}$ , pero excluimos el conjunto completo (este es el $\gcd$ ) así como el conjunto vacío para un total de $2^{n} - 2$ subconjuntos Asignación de lo antes mencionado $s$ ahora se pueden hacer números primos en $s^{2^{n} - 2}$ maneras. ¿O he entendido mal?
Sí, eso es lo que parece cuando ningún primo aparece más de una vez en $L/G$ , obtendrías $(2^n-2)^s$ @BenjaminDickman, cuando tienes un número primo con un exponente mayor que $1$ divisor $L/G$ se vuelve más complejo.
No estoy seguro de seguir completamente tu razonamiento. ¿Crees que podrías encontrar un ejemplo concreto (en tu respuesta) para $n=3$ o $n=4$ ? No estoy muy seguro de cómo un número primo que aparece más de una vez altera mi comentario anterior, ni veo con precisión cómo está invocando el IEP. ¡Sería genial si tienes tiempo!
consideremos $G=1$ y $L=8$ y $n = 3$ . Aquí debemos tener que cada $a_i$ es uno de $1,2,4,8$ , y requerimos que al menos uno de ellos sea $1$ y al menos uno de ellos es $8$ , hay $4^3$ tuplas totales, hay $3^3$ tuplas que no alcanzan el valor uno, hay $3^3$ que no alcanza el valor $8$ y aquí están $2^3$ que no golpean etiher, por lo que hay $4^3-2(3^3) + 2^3$ triples totales que funcionan.
¡Genial! También me han señalado esta misma respuesta que el Teorema 2.7 aquí: derby.openrepository.com/handle/10545/583372 (Puedo agregar una respuesta a este efecto)

Benjamín Dickman · Answer 2

(Agregando esta respuesta wiki de la comunidad para señalar una referencia relevante). Recientemente me señalaron el siguiente documento, en el que se proponen y resuelven este y otros problemas relacionados:

Bagdasar, O. (2014.) "Sobre algunas funciones que involucran el mcm y mcd de tuplas enteras". Publicaciones científicas de la Universidad Estatal de Novi Pazar Serie A: Matemáticas aplicadas, informática y mecánica, 6(2):91-100. PDF (sin muro de pago).

El resultado aparece como el Teorema 2.7 (cf. el comentario de Yorch , también):

Dado el MCD y el MCM de n enteros positivos, ¿cuántas soluciones hay?

Benjamín Dickman

Benjamín Dickman

Asinomás

Benjamín Dickman

Respuestas (2)

Asinomás

Benjamín Dickman

Asinomás

Benjamín Dickman

Asinomás

Benjamín Dickman

Asinomás

Benjamín Dickman

¿La Regla de Collatz 3x+53x+53x+5 tiene un sesgo para ciertos bucles, o mis resultados son defectuosos?

Dos relaciones en serie, cada una implica a la otra - del libro de particiones de Andrews

Introducción suave a la teoría algebraica de números

Existencia de un subconjunto tal que el producto de sus elementos es un cuadrado perfecto

¿Cuántos elementos tiene P(A)P(A)\mathcal{P}(A)?

Identidad con factorial descendente

Topología y combinatoria

¿Hay alguna identidad de poder que no pertenezca a esta lista?

¿Alguien sabría de un libro con una prueba para la extensión HNN que sea puramente algebraica?

si |S∩{1,2,3,…,n}|≥un|S∩{1,2,3,…,n}|≥un|S\cap \{1,2,3,\ldots, n\}|\ge un, etc. muestran que Z+⊂S+TZ+⊂S+T\Bbb Z_{+}\subset S+T