Сколько существует решений, учитывая НОД и НОК n положительных целых чисел?

Question

Сколько существует решений, учитывая НОД и НОК n положительных целых чисел?

Бенджамин Дикман

Вопрос: Предположим, вы знаете $G:=\gcd$ (наибольший общий делитель) и $L:=\text{lcm}$ (наименьшее общее кратное) числа $n$ положительные целые числа; сколько наборов решений существует?

В случае $n = 2$ , обнаруживается, что для $k$ различные простые числа, делящие $L/G$ , всего имеется $2^{k-1}$ уникальные решения.

Я счастлив написать доказательство $n = 2$ случае, если это желательно, но мой вопрос здесь касается более общей версии. $n=3$ случай уже оказался сложным в моих исследованиях, поэтому я был бы рад увидеть, как решены более мелкие случаи, даже если респонденты не уверены в полном обобщении.

В качестве альтернативы: если уже существует ссылка на эту проблему и ее решение, то указатель на такую информацию также будет очень кстати!

Бенджамин Дикман

@Yorch Ваш комментарий ссылается только на вопрос в том случае, если

n = 2

$n=2$ ; для меня этот случай не был проблемой! Я спрашиваю, в частности, об общем случае : где у вас есть положительные целые числа

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

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

Асиномас

Вы требуете, чтобы

n

$n$ положительные целые числа различны? Вы пытаетесь подсчитать мультимножества? Я думаю, что это единственная версия, которую я не смог решить.

Бенджамин Дикман

@Yorch Нет требования, чтобы целые числа были разными и/но (в идеале!) считали разные решения. Если вы считаете, что можете добиться успеха в модифицированной версии (т.е. наложив дополнительные ограничения), то я все равно буду рад увидеть, что вы придумаете.

Ответы (2)

Сколько существует решений, учитывая НОД и НОК n положительных целых чисел?

@Yorch Ваш комментарий ссылается только на вопрос в том случае, если $n=2$ ; для меня этот случай не был проблемой! Я спрашиваю, в частности, об общем случае : где у вас есть положительные целые числа $\{a_1, \ldots, a_n\}$ .
Вы требуете, чтобы $n$ положительные целые числа различны? Вы пытаетесь подсчитать мультимножества? Я думаю, что это единственная версия, которую я не смог решить.
@Yorch Нет требования, чтобы целые числа были разными и/но (в идеале!) считали разные решения. Если вы считаете, что можете добиться успеха в модифицированной версии (т.е. наложив дополнительные ограничения), то я все равно буду рад увидеть, что вы придумаете.

Асиномас · Answer 1

Если вы заинтересованы в подсчете кортежей $(a_1,a_2,\dots,a_n)$ такой, что $\gcd(a_1,\dots,a_n) = G$ и $\operatorname{lcm}(a_1,\dots,a_n) = L$ то мы можем сделать это следующим образом.

Если $L/G = \prod\limits_{i=1}^s p_i^{x_i}$ затем каждый $a_i$ должен быть в форме $G \prod\limits_{j=1}^s p_i^{y_{i,j}}$ с $0 \leq y_{i,j} \leq x_i$ .

Отсюда для каждого простого $p_i$ мы требуем, чтобы функция из $\{1,\dots, n\}$ к $\mathbb N$ который посылает $j$ к $y_{i,j}$ быть функцией, которая попадает $0$ и $x_i$ .

Число таких функций легко определяется включением-исключением для $x_i \geq 1$ , это $(x_i+1)^n - 2(x_i)^n + (x_i-1)^n$ .

Отсюда следует, что общее количество кортежей равно $\prod\limits_{i=1}^s ( (x_i+1)^n - 2x_i^n + (x_i-1)^n)$ .

Подсчет кортежей, как в, с повторением, верно? Например $(1,2)$ и $(2,1)$ каждый из них будет учитываться в ваших вычислениях? Если да, то не так ли (используя вашу запись) вы могли бы назначить $s$ различные простые числа (в их различных степенях) как делители любого из $n$ целые числа или их подмножество (например, для $\{a_1, a_3, a_7\}$ )? Есть $2^n$ подмножества $\{a_1, \ldots, a_n\}$ , но мы исключаем полный набор (это $\gcd$ ), а также пустой набор в сумме $2^{n} - 2$ подмножества. Назначение вышеупомянутого $s$ простые числа теперь можно делать в $s^{2^{n} - 2}$ способы. Или я неправильно понял?
Да, именно так это выглядит, когда ни одно простое число не встречается более одного раза в $L/G$ , вы бы получили $(2^n-2)^s$ @BenjaminDickman, когда у вас есть простое число с показателем больше, чем $1$ разделяющий $L/G$ он становится более сложным.
Я не уверен, что полностью следую вашим рассуждениям. Как вы думаете, вы могли бы разработать конкретный пример (в вашем ответе) для $n=3$ или $n=4$ ? Я не совсем уверен, как штрих, появляющийся более одного раза, меняет мой предыдущий комментарий, и я не понимаю, как именно вы ссылаетесь на IEP. Было бы здорово, если бы у вас было время!
Давайте рассмотрим $G=1$ и $L=8$ и $n = 3$ . Здесь мы должны иметь, что каждый $a_i$ один из $1,2,4,8$ , и мы требуем, чтобы хотя бы один из них был $1$ и хотя бы один из них $8$ , есть $4^3$ всего кортежей, есть $3^3$ кортежи, которые не достигают значения один, есть $3^3$ которые не достигают значения $8$ и здесь $2^3$ которые не попадают ни в один из них, так что есть $4^3-2(3^3) + 2^3$ всего тройки, которые работают.
Ах, здорово! Мне также указали на тот же ответ, что и на теорему 2.7, здесь: derby.openrepository.com/handle/10545/583372 (я могу добавить ответ на этот счет)
Дело $G,L$ то же самое, что и случай $1,L/G$

Бенджамин Дикман · Answer 2

(Добавление этого вики-ответа сообщества , чтобы указать на соответствующую ссылку.) Недавно мне указали на следующую статью, в которой эта и связанные с ней проблемы предлагаются и решаются:

Багдасар, О. (2014 г.) «О некоторых функциях, включающих lcm и gcd целочисленных кортежей». Научные публикации Нови-Пазарского государственного университета Серия А: Прикладная математика, информатика и механика, 6(2):91-100. PDF (без платного доступа).

Результат выглядит как теорема 2.7 (см. также комментарий Yorch ):

Сколько существует решений, учитывая НОД и НОК n положительных целых чисел?

Бенджамин Дикман

Бенджамин Дикман

Асиномас

Бенджамин Дикман

Ответы (2)

Асиномас

Бенджамин Дикман

Асиномас

Бенджамин Дикман

Асиномас

Бенджамин Дикман

Асиномас

Бенджамин Дикман

Имеет ли правило Коллатца 3x+53x+53x+5 смещение для определенных циклов, или мои результаты ошибочны?

Две серии отношений, каждая из которых подразумевает другую - из разделительной книги Эндрюса.

Нежное введение в алгебраическую теорию чисел

Существование подмножества такого, что произведение его элементов является полным квадратом

Сколько элементов имеет P(A)P(A)\mathcal{P}(A)?

Идентичность с падающим факториалом

Топология и комбинаторика

Есть ли какие-либо силовые идентичности, которые не принадлежат этому списку?

Кто-нибудь знает книгу с доказательством расширения HNN, которое в нем чисто алгебраическое?

если |S∩{1,2,3,…,n}|≥un|S∩{1,2,3,…,n}|≥un|S\cap \{1,2,3,\ldots, n\}|\ge un и т. д. показывают, что Z+⊂S+TZ+⊂S+T\Bbb Z_{+}\subset S+T