Доказательство мультипликативности ф-ии через сумму другой

[cxzbsdhwert]

Слушаю данную лекцию по теории чисел.

На временной отметке по ссылке выше, лектор доказал, что функция $f$, заданная через мультипликативную функцию $\theta$ следующим образом: $f(n)=\sum_{d|N}{\theta(d)}$ также мультипликативна, в частности: $f(ab)=f(a)f(b),\space \text{НОД}(a,b)=1$. Далее доказательство этой мультипликативности, которое мне не понятно.

Было доказано, что любой делитель $d$ произведения взаимно простых a и b, по основной теореме арифметики можно разложить на произведение простых $p^k$, но поскольку a и b просты, то каждое такое $p^k$ либо делит $a$ и не делит $b$, либо делит $b$ и не делит $a$, а значит представление делителя $d$ в виде сплошного произведения всех $p^k$ можно заменить на два произведение произведений $p^k$ делящих $a$ и $p^k$ делящих $b$, то есть

$d = \prod_{p|ab}p^{v_p(d)}=\prod_{p|a}p^{v_p(d)}\prod_{p|b}p^{v_p(d)}=d_1d_2$, $v_p(d)$ - степень с которой простое $p$ входит в разложение на простые сомножители $d$.

И далее суть - через эти $d_1$ и $d_2$ была доказана мультипликативность:

$$f(ab)=\sum_{d|ab}\theta(d)=\sum_{d_1|a}\sum_{d_2|b}\theta(d_1\cdot d_2)=\sum_{d_1|a}\sum_{d_2|b}\theta(d_1)\theta(d_2)=\sum_{d_1|a}\theta(d_1)\sum_{d_2|b}\theta(d_2)=f(a)f(b)$$

Вопрос: почему $\sum_{d|ab}\theta(d)$ тождественно всем последующим выражениям (какому-либо из них), следующему например?

Почему следующее выражение, то есть $\sum_{d_1|a}\sum_{d_2|b}\theta(d_1\cdot d_2)$ тождественно всем последующим я полностью понимаю, если понимаю правильно, что имелось в виду под двойной суммой (опускаю $\theta$ для краткости):

Каждый $d_1$ каждого $d$ умножается на каждый $d_2$ каждого $d$ и это всё складывается, то есть (верхний индекс - принадлежность к n-ому делителю $d$, а не степень):

$$(d_{1}^1 d_{2}^1 + d_{1}^1 d_{2}^2 + ... + d_{1}^1 d_{2}^n)+(d_{1}^2 d_{2}^1 + d_{1}^2 d_{2}^2 + ... + d_{1}^2 d_{2}^n)+...+(d_{1}^n d_{2}^1 + d_{1}^n d_{2}^2 + ... + d_{1}^n d_{2}^n)=\sum_{d_1|a}\sum_{d_2|b}d_1 d_2$$

(1)

И это действительно эквивалентно:

$$(d_{1}^1 \cdot d_{1}^2 \cdot ... \cdot d_{1}^n) \cdot (d_{2}^1 \cdot d_{2}^2 \cdot ... \cdot d_{2}^n)=\sum_{d_1|a}d_1\sum_{d_2|b}d_2$$

(2)

Проблема в том, что из всех этих комбинаций, первую сумму, которую далее отождествляли, составляют только n-ые слагаемые в каждой n-ной скобе $(1)$, то есть $\theta(d_{1}^1) \theta(d_{2}^1), \theta(d_{1}^2)\theta(d_{2}^2), ..., \theta(d_{1}^n) \theta(d_{2}^n)$, поскольку именно их суммой является изначальная сумма:

$$\sum_{d|ab}{\theta(d)}=\theta(d_{1}^1 d_{2}^1)+\theta(d_{1}^2 d_{2}^2)+...+\theta(d_{1}^n d_{2}^n)$$

Где гарантия, что все остальные слагаемые $\theta$ с аргументами, состоящими из $d_1$ и $d_2$, входящих в разные $d$ (например $\theta(d_{1}^1)\theta(d_{2}^4)$) в сумме дают ноль, так, чтобы выполнялось равенство? Или они и не дают ноль? Как тогда вообще выполняется равенство?

[mihaild]

cxzbsdhwert в сообщении #1695108 писал(а):

Почему следующее выражение, то есть $\sum_{d_1|a}\sum_{d_2|b}\theta(d_1\cdot d_2)$ тождественно всем последующим я полностью понимаю

Значит вопрос только в первых двух равенствах.

Первое - это просто определение $f$.
Второе - это как раз следствие того, что написано выше: каждый делитель $ab$ однозначно представляется в виде произведения делителя $a$ и делителя $b$.

cxzbsdhwert в сообщении #1695108 писал(а):

Проблема в том, что из всех этих комбинаций первую сумму которую отождествляли составляют только n-ые слагаемые в каждой n-ной скобе $(1)$, то есть $\theta(d_{1}^1) \theta(d_{2}^1), \theta(d_{1}^2)\theta(d_{2}^2), ..., \theta(d_{1}^n) \theta(d_{2}^n)$, поскольку именно их суммой является изначальная сумма:

$$\sum_{d|ab}{\theta(d)}=\theta(d_{1}^1 d_{2}^1)+\theta(d_{1}^2 d_{2}^2)+...+\theta(d_{1}^n d_{2}^n)$$

Нет, с чего Вы это взяли?
Пусть $a = 6$, $b = 35$. Найдите делители $a$, $b$ и $ab$.

[dgwuqtj]

cxzbsdhwert в сообщении #1695108 писал(а):

Каждый $d_1$ каждого $d$ умножается на каждый $d_2$ каждого $d$ и это всё складывается, то есть (верхний индекс - принадлежность к n-ому делителю $d$, а не степень)

Если вы пронумеровали через $d^1, \ldots, d^n$ все делители $a b$, то неверно, что $d_1^k$ пробегает все делители $a$ по одному разу. Есть биекция между делителями $d \mid a b$ и парами $(d_1 \mid a, d_2 \mid b)$.

[cxzbsdhwert]

Цитата:

Нет, с чего Вы это взяли?
Пусть $a = 6$, $b = 35$. Найдите делители $a$, $b$ и $ab$.

Понятно что Вы хотели показать: 6 - 1, 2, 3, 6; 35 - 1, 5, 7, 35; 6*35 - делители 6 и 35 а также произведения каждого с каждым, то есть, например не только первого делителя первого на первый делитель второго, но и на второй делитель второго и на третий и т.д.

Но как это чисто алгебраически получается? У нас $d$ (Вы же под $ab$ - вели аналогию с делителем $d$, а не с изначальным аргументов $f$?) есть произведение двух $d_1$ и $d_2$, которые, в свою очередь, есть произведения простых, делящих $a$ и $b$ соответственно, в степени, в которой они (простые) входят в разложение $d$, одного и того же $d$.

То есть получается, грубо $(x\cdot y)+(z \cdot k)$+..., и мы непонятно на основании чего утверждаем что это равно $(x\cdot k)+(z \cdot y)$, то есть например $(1\cdot 2)+(3\cdot 4)=(1\cdot 4)+(3\cdot 2)$.

Я думаю, что причина моего непонимания (если в лекции всё верно) как-то связана с упусканием того факта что по определению мы суммируем все делители, а все делители представляем через простые, которые, в отличии от всех делителей не составные, и взаимно простые. Я наверное, как-то упускаю, что мы рассматриваем все делители, которые между собой могут не быть взаимно простыми, и там по нескольку раз как-то всё может умножаться.

-- 22.07.2025, 18:30 --

Не очень понятно, что в формулировке Лектора имелось в виду под $d_1$ и $d_2$ в последующем, при доказывании сумм. Это именно составляющие одного конкретного $d$, как я это понял и описал выше, или что-то другое, более "сквозное"

-- 22.07.2025, 18:41 --

dgwuqtj в сообщении #1695112 писал(а):

cxzbsdhwert в сообщении #1695108 писал(а):

Каждый $d_1$ каждого $d$ умножается на каждый $d_2$ каждого $d$ и это всё складывается, то есть (верхний индекс - принадлежность к n-ому делителю $d$, а не степень)

Если вы пронумеровали через $d^1, \ldots, d^n$ все делители $a b$, то неверно, что $d_1^k$ пробегает все делители $a$ по одному разу. Есть биекция между делителями $d \mid a b$ и парами $(d_1 \mid a, d_2 \mid b)$.

"Пробегает" там только $d_1$ каждого $d$ по $d_2$ каждого $d$. То есть, если хотите, имеется неинъективная сюръекция из множества "дэ вторых", сформированных из каждого $d$ в $d_1$ первого $d$. И такая сюръекция на каждый "дэ первый" приходится. Это в случае выражений с двойными суммами. По крайней мере если я так понимаю, что имеется в виду под двойной суммой.

А в первом выражении, с одной суммой, там действительно биекция - каждому $d_2$ соответствует один $d_1$ из того же $d$.

[mihaild]

cxzbsdhwert в сообщении #1695113 писал(а):

Вы же под $ab$ - вели аналогию с делителем $d$, а не с изначальным аргументов $f$?

Именно с изначальным. Дальше нужно найти его делители, и представить каждый делитель $ab$ в виде соответствующего произведения.

Если всё еще непонятно - можно попробовать так. Пусть $D(x)$ - множество делителей числа $x$. По выше доказанному, функция $g: D(a) \times D(b) \leftrightarrow D(ab)$, такая что $g(x, y) = x \cdot y$ - биекция.
Тогда мы можем записать по определению $D$

$$\sum\limits_{d | ab} \theta(d) = \sum\limits_{d \in D(ab)} \theta(d)$$

Поскольку $g$ - биекция, то $d \in D(ab)$ равносильно $\exists d_1 \in D(a) \exists d_2\in D(b): d = g(a, b)$. Значит последнюю сумму можно записать как

$$\sum\limits_{d \in D(ab)} \theta(d) = \sum\limits_{d_1 \in D(a), d_2 \in D(b)} \theta(g(d_1, d_2))$$

А дальше уже дело техники - разбиваем двойную сумму на повторные и подставляем определения $D$ и $g$

$$\sum\limits_{d_1 \in D(a), d_2 \in D(b)} \theta(g(a, b)) = \sum\limits_{d_1 \in D(a)} \sum \limits_{d_2 \in D(b)} \theta(g(d_1, d_2)) = \sum\limits_{d_1 | a} \sum \limits_{d_2 | b} \theta(d_1 \cdot d_2)$$

[cxzbsdhwert]

mihaild в сообщении #1695114 писал(а):

cxzbsdhwert в сообщении #1695113 писал(а):

Вы же под $ab$ - вели аналогию с делителем $d$, а не с изначальным аргументов $f$?

Именно с изначальным. Дальше нужно найти его делители, и представить каждый делитель $ab$ в виде соответствующего произведения.

Если всё еще непонятно - можно попробовать так. Пусть $D(x)$ - множество делителей числа $x$. По выше доказанному, функция $g: D(a) \times D(b) \leftrightarrow D(ab)$, такая что $g(x, y) = x \cdot y$ - биекция.
Тогда мы можем записать по определению $D$

$$\sum\limits_{d | ab} \theta(d) = \sum\limits_{d \in D(ab)} \theta(d)$$

Поскольку $g$ - биекция, то $d \in D(ab)$ равносильно $\exists d_1 \in D(a) \exists d_2\in D(b): d = g(a, b)$. Значит последнюю сумму можно записать как

$$\sum\limits_{d \in D(ab)} \theta(d) = \sum\limits_{d_1 \in D(a), d_2 \in D(b)} \theta(g(d_1, d_2))$$

А дальше уже дело техники - разбиваем двойную сумму на повторные и подставляем определения $D$ и $g$

$$\sum\limits_{d_1 \in D(a), d_2 \in D(b)} \theta(g(a, b)) = \sum\limits_{d_1 \in D(a)} \sum \limits_{d_2 \in D(b)} \theta(g(d_1, d_2)) = \sum\limits_{d_1 | a} \sum \limits_{d_2 | b} \theta(d_1 \cdot d_2)$$

Ладно, если Вы утверждаете, что ошибки нет, то попробую ещё пока сам, не читая Ваше сообщение.

[cxzbsdhwert]

mihaild в сообщении #1695114 писал(а):

cxzbsdhwert в сообщении #1695113 писал(а):

Вы же под $ab$ - вели аналогию с делителем $d$, а не с изначальным аргументов $f$?

Именно с изначальным. Дальше нужно найти его делители, и представить каждый делитель $ab$ в виде соответствующего произведения.

Если всё еще непонятно - можно попробовать так. Пусть $D(x)$ - множество делителей числа $x$. По выше доказанному, функция $g: D(a) \times D(b) \leftrightarrow D(ab)$, такая что $g(x, y) = x \cdot y$ - биекция.
Тогда мы можем записать по определению $D$

$$\sum\limits_{d | ab} \theta(d) = \sum\limits_{d \in D(ab)} \theta(d)$$

Поскольку $g$ - биекция, то $d \in D(ab)$ равносильно $\exists d_1 \in D(a) \exists d_2\in D(b): d = g(a, b)$. Значит последнюю сумму можно записать как

$$\sum\limits_{d \in D(ab)} \theta(d) = \sum\limits_{d_1 \in D(a), d_2 \in D(b)} \theta(g(d_1, d_2))$$

А дальше уже дело техники - разбиваем двойную сумму на повторные и подставляем определения $D$ и $g$

$$\sum\limits_{d_1 \in D(a), d_2 \in D(b)} \theta(g(a, b)) = \sum\limits_{d_1 \in D(a)} \sum \limits_{d_2 \in D(b)} \theta(g(d_1, d_2)) = \sum\limits_{d_1 | a} \sum \limits_{d_2 | b} \theta(d_1 \cdot d_2)$$

Да, причина не понимая была в том, что я почему-то думал что есть какое-то строгое правило компоновки делителей a и b при представлении делителя ab, то есть только какой-то конкретный делитель a умноженный на конкретный делитель b есть делителем ab. Ну и тут в общем-то ничего не правильного не написано, но я как-то не правильно это понимал.

Короче, действительно любой делитель a с любым делителем b.

И ещё вопрос: а точно ли биекция из Декартова произведения делителей a и b в делители ab?

Я понимаю, что по условию, a и b взаимно просты, а значит множество делителей a и множество делителей b не пересекаются, следовательно неинъективное отображение пар делителей за счёт коммутативности исключается (не будет (k,1) и (1,k), например).

Но не могут ли разные пары делителей двух взаимно простых чисел своим умножением давать одинаковый результат? Каково доказательство, что не могут?

Наверное по основной теореме арифметики, а именно единственности разложения числа на простые сомножители. Следовательно, если у нас два разных делителя (некоторый делитель a и некоторый делитель b), которые по условию состоят из произведения разных простых сомножителей, то такие два числа разные, и произведения разных пар являются разными уникальными числами. Правильно?

[mihaild]

Примерно так. Если у нас уже есть понятие НОД, то можно проще: если $d_1 | a$, $d_2 | b$, то они однозначно восстанавливаются из $d_1 \cdot d_2$ как $d_1 = \text{НОД}(a, d_1 \cdot d_2)$ и $d_2 = \text{НОД}(b, d_1 \cdot d_2)$ соответственно.

[cxzbsdhwert]

mihaild в сообщении #1695160 писал(а):

Примерно так. Если у нас уже есть понятие НОД, то можно проще: если $d_1 | a$, $d_2 | b$, то они однозначно восстанавливаются из $d_1 \cdot d_2$ как $d_1 = \text{НОД}(a, d_1 \cdot d_2)$ и $d_2 = \text{НОД}(b, d_1 \cdot d_2)$ соответственно.

А если a и b не взаимно простые, то всегда не будет биекции?

[mihaild]

cxzbsdhwert в сообщении #1695162 писал(а):

А если a и b не взаимно простые, то всегда не будет биекции?

Ага. Если они оба делятся на $p$, то есть представление $p = p \cdot 1 = 1 \cdot p$.

[cxzbsdhwert]

mihaild в сообщении #1695163 писал(а):

cxzbsdhwert в сообщении #1695162 писал(а):

А если a и b не взаимно простые, то всегда не будет биекции?

Ага. Если они оба делятся на $p$, то есть представление $p = p \cdot 1 = 1 \cdot p$.

Спасибо за объяснения

[dgwuqtj]

cxzbsdhwert в сообщении #1695159 писал(а):

Я понимаю, что по условию, a и b взаимно просты, а значит множество делителей a и множество делителей b не пересекаются, следовательно неинъективное отображение пар делителей за счёт коммутативности исключается (не будет (k,1) и (1,k), например).

Но не могут ли разные пары делителей двух взаимно простых чисел своим умножением давать одинаковый результат? Каково доказательство, что не могут?

Они пересекаются, общий делитель $1$. А так если $d_1 \mid a$ и $d_2 \mid b$, то $d_i$ находятся из их произведения $d = d_1 d_2$ по формулам $d_1 = \text{НОД}(d, a)$, $d_2 = \text{НОД}(d, b)$. Потому что $\text{НОД}(d, a) = \text{НОД}(d_1 d_2, a) = d_1 \text{НОД}(d_2, \frac a {d_1})$ и этот последний НОД тривиален в силу $\text{НОД}(d_2, \frac a {d_1}) \leq \text{НОД}(b, a) = 1$.

[cxzbsdhwert]

dgwuqtj в сообщении #1695165 писал(а):

cxzbsdhwert в сообщении #1695159 писал(а):

Я понимаю, что по условию, a и b взаимно просты, а значит множество делителей a и множество делителей b не пересекаются, следовательно неинъективное отображение пар делителей за счёт коммутативности исключается (не будет (k,1) и (1,k), например).

Но не могут ли разные пары делителей двух взаимно простых чисел своим умножением давать одинаковый результат? Каково доказательство, что не могут?

Они пересекаются, общий делитель $1$. А так если $d_1 \mid a$ и $d_2 \mid b$, то $d_i$ находятся из их произведения $d = d_1 d_2$ по формулам $d_1 = \text{НОД}(d, a)$, $d_2 = \text{НОД}(d, b)$. Потому что $\text{НОД}(d, a) = \text{НОД}(d_1 d_2, a) = d_1 \text{НОД}(d_2, \frac a {d_1})$ и этот последний НОД тривиален в силу $\text{НОД}(d_2, \frac a {d_1}) \leq \text{НОД}(b, a) = 1$.

1. Не задумывался о том, что множители аргументов НОД можно так выносить за НОД. Нужно подумать, почему в общем случае такое тождество выполняется.
2. А почему $\text{НОД}(d_2, \frac a {d_1})$ может быть меньше НОД a и b? $d_2$ это множитель $b$, и если $a$ и $b$ взаимно просты, то $d_2$ не является множителем $a$, ну и наверное уж тем более $a$ без какого-то своего множителя $d_1$.

Или это просто частный случай более общего утверждения, не только для двух взаимно простых чисел? Некоторый множитель второго числа может иметь НОД с первым числом без какого-то своего множителя, меньший, чем НОД первого и второго.

Но тут наверное и не обязательно будет меньше если первое число будет на что-то делиться, то есть $\text{НОД}(d_2,a)\leq \text{НОД}(b,a),d_2|b$?

[dgwuqtj]

1. Есть общее тождество $\text{НОД}(x y, x z) = x\,\text{НОД}(y, z)$, оно верно для всех целых значений переменных. Проверяется практически по определению.
2. Опять же есть общий факт $\text{НОД}(x, z) \mid \text{НОД}(x y, z)$. Другими словами, НОД монотонен по каждому аргументу, но в смысле делимости, а не стандартного порядка.

[cxzbsdhwert]

dgwuqtj в сообщении #1695176 писал(а):

2. Опять же есть общий факт $\text{НОД}(x y, z) \mid \text{НОД}(x, z)$. Другими словами, НОД монотонен по каждому аргументу, но в смысле делимости, а не стандартного порядка.

А не наоборот?
Если $z>x$, разве $xy$, в виду умножения $x$ на $y$ не может иметь получить новый делитель, который будет больше чем делитель только $x$, являющийся общим с $z$?
Тривиально, если, как я уже написал, $z>x$, $x|z$ есть $\text{НОД}(x,z)=x$, то взяв $y=\dfrac{z}{x}$, получим новый $\text{НОД}(xy,z)=z$, который больше $\text{НОД}(x,z)=x$ по условию $z>x$, а следовательно $\text{НОД}(x y, z) \nmid \text{НОД}(x, z)$, напротив - $\text{НОД}(x, z) \mid \text{НОД}(xy, z)$