Глава 8.1

Арифметические функции

[111/99%]

Показать

LaTeX

Показать LaTeX

1 · Задачи о целых частях чисел[11/100%]

Задача 8.1

Пусть $n$ — целое, $x$ — произвольное. Тогда

\left[x+n\right]=\left[x\right]+n .

Задача 8.2

В разложении определителя $n$ -го порядка произведение членов, стоящих в диагоналях, соседних с главной диагональю, имеет знак $(-1)^{\left[\frac{n}{2}\right]}$ .

Задача 8.3

\left[2 x\right]-2 \left[x\right]=0 \text{ или } 1,

смотря по тому, будет ли

x-\left[x\right]<\frac{1}{2} \quad \text{ или } \geqslant \frac{1}{2} .

Задача 8.4

Если $0<\alpha <1$ , то

\left[x\right]-\left[x-\alpha \right]=0 \quad \text{ или } \quad 1,

смотря по тому, будет ли

x-\left[x\right] \geqslant \alpha \text{ или }<\alpha .

Задача 8.5

В предположении, что $x$ не имеет вида $n+\frac{1}{2}$ ( $n$ — целое), выразить ближайшее к $x$ целое число посредством символа $\left[\phantom{x}\right]$ .

Задача 8.6

$\left[x\right]$ можно было бы назвать целым числом, ближайшим слева к $x$ . Выразить посредством символа $\left[\phantom{x}\right]$ целое число, ближайшее справа к $x$ . (Замена данного числа ближайшим справа целым числом — обычный прием мелких торговых расчетов.)

Задача 8.7

$\left[\alpha \right]+\left[\beta \right]$ либо $=\left[\alpha +\beta \right]$ , либо $=\left[\alpha +\beta \right]-1$ , $\left[\alpha \right]-\left[\beta \right]$ либо $=\left[\alpha -\beta \right]$ , либо $=\left[\alpha -\beta \right]+1$ .

Задача 8.8

$\left[2 \alpha \right]+\left[2 \beta \right] \geqslant \left[\alpha \right]+\left[\alpha +\beta \right]+\left[\beta \right]$ .

Задача 8.9

Пусть $n$ — целое положительное число. Тогда

\left[x\right]+\left[x+\frac{1}{n}\right]+\left[x+\frac{2}{n}\right]+\ldots +\left[x+\frac{n-1}{n}\right]=\left[n x\right] .

Примечание.

Ch. Hermite, Acta Math., т. 5, стр. 315, 1884.

Задача 8.10

Пусть $n$ — целое положительное число, $x$ произвольно. Тогда

\left[\frac{\left[n x\right]}{n}\right]=\left[x\right] .

Задача 8.11

Пусть $m$ — целое положительное число. Показать, что наивысшей степенью 2, содержащейся в

\left[(1+\sqrt{3})^{2 m+1}\right],

является $2^{m+1}$ .

Примечание.

J. J. Sylvester, задача, Nouv. Ann., серия 1, т. 16, стр. 125, 1857. Решения — E. Prouhet, Lebesgue, там же, серия 1, т. 16, стр. 184, 262, 1857.

2 · Подсчёт целых точек[9/100%]

Задача 8.12

Пусть $a$ и $n$ — целые положительные числа. Число тех из чисел $1,2,3, \ldots , n$ , которые делятся на $a$ , равно $\left[\frac{n}{a}\right]$ .

Задача 8.13

Сколько нулей имеет функция $\sin x$ в интервале $a<x \leqslant b$ ? Сколько в интервале $a \leqslant x<b$ ?

Задача 8.14

Пусть $0 \leqslant \alpha \leqslant \pi$ . Обозначим через $V_{n}(\alpha )$ число перемен знака в последовательности

1, \quad \cos \alpha , \quad \cos 2 \alpha , \ldots , \quad \cos (n-1) \alpha , \quad \cos n \alpha ;

тогда

\lim _{n \rightarrow \infty } \frac{V_{n}(\alpha )}{n}=\frac{\alpha }{\pi } .

Примечание.

J. König, Math. Ann., т. 9, стр. 530, 1876. Задача; Nouv. Corresp. Math., т. 5, стр. 222, 1879. Решение — Radicke, там же, т. 6, стр. 82, 1880.

Задача 8.15

Пусть $\theta$ — иррациональное число, $0<\theta <1$ и $g_{n}$ равно нулю или единице, смотря по тому, равны между собой или же различны числа $\left[n \theta \right]$ и $\left[(n-1) \theta \right]$ . Показать, что

\lim _{n \rightarrow \infty } \frac{g_{1}+g_{2}+\ldots +g_{n}}{n}=\theta .

Задача 8.16

Определить число $N(r, a, \alpha )$ нулей целой функции $e^{z}-a e^{i \alpha }$ в круге $\left|z\right| \leqslant r$ ( $r, a, \alpha$ — вещественные постоянные числа, $r>0, a>0$ ).

Задача 8.17

Пусть $a$ и $b$ — целые числа, $f(x)$ — функция, определенная и положительная в интервале $a \leqslant x \leqslant b$ . Выразить посредством символа $\left[\phantom{x}\right]$ число целых точек (точек с целочисленными координатами, I 28), находящихся в области, определяемой неравенствами

a \leqslant x \leqslant b, \quad 0<y \leqslant f(x) .

Задача 8.18

Пусть $p$ и $q$ — взаимно простые целые положительные числа. Доказать путем подсчета целых точек формулу

\left[\frac{q}{p}\right]+\left[\frac{2 q}{p}\right]+\left[\frac{3 q}{p}\right]+\ldots +\left[\frac{(p-1) q}{p}\right]=\frac{(p-1)(q-1)}{2} .

Задача 8.19

Пусть $p$ и $q$ — нечетные взаимно простые целые положительные числа. Обозначим $\frac{p-1}{2}=p^{\prime }, \frac{q-1}{2}=q^{\prime }$ . Показать, что

\left(\left[\frac{q}{p}\right]+\left[\frac{2 q}{p}\right]+\ldots +\left[\frac{p^{\prime } q}{p}\right]\right)+\left(\left[\frac{p}{q}\right]+\left[\frac{2 p}{q}\right]+\ldots +\left[\frac{q^{\prime } p}{q}\right]\right)=p^{\prime } q^{\prime } .

Примечание.

Gauss, Theorematis arithmetici demonstratio nova, 1808, Opera omnia, т. 2, стр. 1--8; Göttingen, Königl. Ges. der Wiss., 1863; G. Eisenstein, задача, J. für Math., т. 27, стр. 281, 1844.

Задача 8.20

Для простого числа $p$ вида $4 n+1$ имеет место формула

\left[\sqrt{p}\right]+\left[\sqrt{2 p}\right]+\left[\sqrt{3 p}\right]+\ldots +\left[\sqrt{\frac{p-1}{4} p}\right]=\frac{p^{2}-1}{12} .

Примечание.

V. Bouniakowski, C. R., т. 94, стр. 1459--1461, 1882.

3 · Принцип включения-исключения[14/100%]

Задача 8.21

Пусть дано $N$ любых объектов. Пусть $N_{\alpha }$ — число тех из них, которые обладают некоторым свойством $\alpha$ , $N_{\beta }$ — число тех, которые обладают свойством $\beta , \ldots , N_{\varkappa }$ , соотв. $N_{\lambda }$ , — число тех, которые обладают свойством $\varkappa$ , соотв. $\lambda$ . Аналогично пусть $N_{\alpha \beta }$ , $N_{\alpha \gamma }, \ldots , N_{\alpha \beta \gamma }, \ldots , N_{\alpha \beta \gamma \ldots \varkappa \lambda }$ обозначают число тех из этих объектов, которые одновременно обладают свойствами $\alpha$ и $\beta$ , соотв. $\alpha$ и $\gamma , \ldots$ , соотв. $\alpha , \beta$ и $\gamma , \ldots$ , соотв. $\alpha , \beta , \gamma , \ldots , \varkappa$ и $\lambda$ . Тогда число объектов, которые не обладают ни одним из свойств $\alpha , \beta , \gamma , \ldots , \varkappa , \lambda$ , равно

\begin{aligned} & N-N_{\alpha }-N_{\beta }-N_{\gamma }-\ldots -N_{\varkappa }-N_{\lambda }+ \\ & +N_{\alpha \beta }+N_{\alpha \gamma }+\ldots +N_{\varkappa \lambda }- \\ & -N_{\alpha \beta \gamma }-\ldots + \\ & \ldots \ldots \ldots \ldots \\ & \pm N_{\alpha \beta \gamma \ldots \varkappa \lambda } . \end{aligned}

Примечание.

J. J. Sylvester, C. R., т. 96, стр. 463, 1883.

Задача 8.21.1

(1)(2)(3)

Что представляет собой характеристическая функция

(1)

дополнения множества $A$ ,

(2)

пересечения множеств $A$ и $B$ ,

(3)

объединения множеств $A$ и $B$ ?

Задача 8.21.1

(1)(2)(3)

Что представляет собой характеристическая функция

(1)

дополнения множества $A$ ,

(2)

пересечения множеств $A$ и $B$ ,

(3)

объединения множеств $A$ и $B$ ?

Задача 8.21.2

Дать другое доказательство задачи 21.

Задача 8.21.2

Дать другое доказательство задачи 21.

Задача 8.22

Пусть дано $n$ объектов ( $n>1$ ) и пусть свойством $\alpha$ обладают все кроме первого, свойством $\beta$ — все кроме второго, , свойством $\lambda$ — все кроме последнего, $n$ -го объекта. Что дает 21 в этом случае?

Задача 8.22.1

Доказать задачу I 189 комбинаторным рассуждением (ср. задачу 21 выше и задачу I 192).

Задача 8.22.1

Доказать задачу I 189 комбинаторным рассуждением (ср. задачу 21 выше и задачу I 192).

Задача 8.22.2

Доказать задачу I 208 комбинаторным рассуждением.

Задача 8.22.2

Доказать задачу I 208 комбинаторным рассуждением.

Задача 8.22.3

Доказать, что

\widetilde{S}_k^n = S_k^n - \binom {n}{1}S_{k-1}^{n-1} + \binom {n}{2}S_{k-2}^{n-2} - \cdots + (-1)^n S_{k-n}^0 .

Примечание.

Определения см. I, гл. 4, § 3; если условие $1 \leq k \leq n$ не выполнено, то $S_k^n$ следует считать равным 0.

Задача 8.22.3

Доказать, что

\widetilde{S}_k^n = S_k^n - \binom {n}{1}S_{k-1}^{n-1} + \binom {n}{2}S_{k-2}^{n-2} - \cdots + (-1)^n S_{k-n}^0 .

Примечание.

Определения см. I, гл. 4, § 3; если условие $1 \leq k \leq n$ не выполнено, то $S_k^n$ следует считать равным 0.

Задача 8.23

Сколько из $n!$ членов в разложении определителя $n$ -го порядка обращается в нуль, если положить все элементы главной диагонали равными нулю?

Примечание.

В другой формулировке, как «jeu de rencontre», у Montmort и A. de Moivre. См. Euler, Opera omnia, серия 1, т. 7, стр. 11, Leipzig und Berlin, B. G. Teubner, 1923.

Задача 8.24

Пусть $a, b, c, \ldots , k, l$ — взаимно простые целые положительные числа. Сколько из чисел $1,2,3, \ldots , n$ не делится ни на одно из этих чисел $a, b, c, \ldots , k, l$ ?

Задача 8.25

Пусть $p, q, r, \ldots$ будут различные простые множители числа $n$ . Число чисел, меньших $n$ и взаимно простых с ним, равно

n\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\left(1-\frac{1}{r}\right) \ldots

Примечание.

Euler.

Задача 8.26

Пусть дано $N$ произвольных объектов, могущих, как в 21, обладать свойствами $\alpha , \beta , \gamma , \ldots , \varkappa , \lambda$ . Пусть каждому отдельному объекту приписано некоторое числовое значение. Обозначим через $W_{\alpha }$ сумму числовых значений тех объектов, которые обладают свойством $\alpha$ , через $W_{\beta }$ сумму числовых значений объектов со свойством $\beta$ и т. д. Аналогично будем обозначать через $W_{\alpha \beta }, W_{\alpha \gamma }, \ldots , W_{\alpha \beta \gamma }, \ldots , W_{\alpha \beta \gamma \ldots \varkappa \lambda }$ сумму числовых значений тех объектов, которые одновременно обладают свойствами $\alpha$ и $\beta$ , соотв. $\alpha$ и $\gamma , \ldots$ , соотв. $\alpha , \beta$ и $\gamma , \ldots$ , соотв. $\alpha , \beta , \gamma , \ldots , \varkappa$ и $\lambda$ . Пусть, наконец, $W$ — сумма числовых значений всех объектов. Тогда сумма числовых значений объектов, не обладающих ни одним из свойств $\alpha , \beta , \gamma , \ldots , \varkappa , \lambda$ , будет равна

\begin{aligned} & W-W_{\alpha }-W_{\beta }-W_{\gamma }-\ldots -W_{\varkappa }-W_{\lambda }+ \\ & +W_{\alpha \beta }+W_{\alpha \gamma }+\ldots +W_{\varkappa \lambda }- \\ & -W_{\alpha \beta \gamma }-\ldots + \\ & \ldots \ldots \ldots \ldots \\ & \pm W_{\alpha \beta \gamma \ldots \varkappa \lambda } . \end{aligned}

Задача 8.27

Пусть $r_{1}, r_{2}, \ldots , r_{\varphi (n)}$ — взаимно простые с $n$ числа, меньшие, чем $n$ ( $n>1$ ). Показать, что

r_{1}^{2}+r_{2}^{2}+\ldots +r_{\varphi (n)}^{2}=\frac{\varphi (n)}{3}\left(n^{2}+\frac{(-1)^{\nu }}{2} p q r \ldots \right),

где $p, q, r, \ldots$ — различные простые множители $n$ , а $\nu$ — их число.

Задача 8.27.1

Число $N_0$ , искомое в 21, удовлетворяет соотношениям

\leq N

\geq N - N_\alpha - N_\beta - N_\gamma - \cdots - N_\kappa - N_\lambda

\leq N - N_\alpha - N_\beta - N_\gamma - \cdots - N_\kappa - N_\lambda + N_{\alpha \beta } + N_{\alpha \gamma } + \cdots + N_{\kappa \lambda } .

\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots

Примечание.

Короче говоря, в несколько расширенном смысле этого термина (см. введение к задачам I 140 и I 144), выражение, приведенное в 21, «обвертывает» $N_0$ .

Задача 8.27.1

Число $N_0$ , искомое в 21, удовлетворяет соотношениям

\leq N

\geq N - N_\alpha - N_\beta - N_\gamma - \cdots - N_\kappa - N_\lambda

\leq N - N_\alpha - N_\beta - N_\gamma - \cdots - N_\kappa - N_\lambda + N_{\alpha \beta } + N_{\alpha \gamma } + \cdots + N_{\kappa \lambda } .

\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots

Примечание.

Задача 8.27.2

Пусть $l$ — число свойств, рассматриваемых в 21. Положим

S_0=N, \qquad S_1=N_\alpha +N_\beta +N_\gamma +\cdots +N_\kappa +N_\lambda , \qquad S_2=N_{\alpha \beta }+N_{\alpha \gamma }+\cdots +N_{\kappa \lambda }, \qquad \ldots , \qquad S_l=N_{\alpha \beta \gamma \ldots \kappa \lambda } ,

и пусть $s_k$ обозначает число тех объектов, которые обладают в точности $k$ из рассматриваемых $l$ свойств, $0 \leq k \leq l$ . Легко видеть (обнаружить связь с биномиальными коэффициентами), что

S_0=s_0+s_1+s_2+s_3+\cdots +s_l ,

S_1=\phantom{s_0+{}}s_1+2s_2+3s_3+\cdots +ls_l ,

S_2=\phantom{s_0+s_1+{}}s_2+3s_3+\cdots +\binom {l}{2}s_l ,

S_3=\phantom{s_0+s_1+s_2+{}}s_3+\cdots +\binom {l}{3}s_l ,

\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots

S_l=\phantom{s_0+s_1+s_2+s_3+\cdots +{}}s_l .

Задача 8.27.2

Пусть $l$ — число свойств, рассматриваемых в 21. Положим

S_0=N, \qquad S_1=N_\alpha +N_\beta +N_\gamma +\cdots +N_\kappa +N_\lambda , \qquad S_2=N_{\alpha \beta }+N_{\alpha \gamma }+\cdots +N_{\kappa \lambda }, \qquad \ldots , \qquad S_l=N_{\alpha \beta \gamma \ldots \kappa \lambda } ,

S_0=s_0+s_1+s_2+s_3+\cdots +s_l ,

S_1=\phantom{s_0+{}}s_1+2s_2+3s_3+\cdots +ls_l ,

S_2=\phantom{s_0+s_1+{}}s_2+3s_3+\cdots +\binom {l}{2}s_l ,

S_3=\phantom{s_0+s_1+s_2+{}}s_3+\cdots +\binom {l}{3}s_l ,

\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots

S_l=\phantom{s_0+s_1+s_2+s_3+\cdots +{}}s_l .

4 · Части и делители[10/100%]

Задача 8.28

Пусть $a, b, c, \ldots , k, l$ — произвольные неотрицательные целые числа. Имеем

\begin{aligned} \operatorname {Max}(a, b, c, \ldots , k, l) & =a+b+c+\ldots +k+l- \\ & -\operatorname {Min}(a, b)-\operatorname {Min}(a, c)-\ldots -\operatorname {Min}(k, l)+ \\ & +\operatorname {Min}(a, b, c)+\ldots - \\ & \ldots \ldots \ldots \ldots \\ & \pm \operatorname {Min}(a, b, c, \ldots , k, l) . \end{aligned}

Задача 8.29

Наименьшее общее кратное $M$ целых положительных чисел $a, b, c, \ldots , k, l$ можно представить следующим образом:

M=a b c \ldots k l(a, b)^{-1}(a, c)^{-1} \ldots (k, l)^{-1}(a, b, c) \ldots (a, b, c, \ldots , k, l)^{ \pm 1} .

Задача 8.30

1=\left|\begin{array}{cccccc} 1 & 0 & 0 & 0 & \ldots & 0 \\ 1 & 1 & 0 & 0 & \ldots & 0 \\ 1 & 1 & 1 & 0 & \ldots & 0 \\ 1 & 1 & 1 & 1 & \ldots & 0 \\ . & \ldots & . & . & \ldots & . \\ 1 & 1 & 1 & 1 & \ldots & 1 \end{array}\right|^{2}=\left|\begin{array}{cccccc} 1 & 1 & 1 & 1 & \ldots & 1 \\ 1 & 2 & 2 & 2 & \ldots & 2 \\ 1 & 2 & 3 & 3 & \ldots & 3 \\ 1 & 2 & 3 & 4 & \ldots & 4 \\ . & . . & . & \ldots & \ldots & \ldots . \\ 1 & 2 & 3 & 4 & \ldots & n+1 \end{array}\right| .

Здесь общий элемент первого определителя $\eta_{\lambda \mu }=1$ , когда $\mu$ является частью $\lambda$ (собственной или несобственной), и равен нулю в противном случае; во втором определителе общий элемент $c_{\lambda \mu }$ равен числу общих частей чисел $\lambda$ и $\mu$ , т. е. наименьшему из чисел $\lambda +1$ и $\mu +1$ ( $\lambda , \mu =0,1, \ldots , n$ ).

Задача 8.31

Определитель, общий элемент которого $c_{\lambda \mu }$ равен числу общих делителей чисел $\lambda$ и $\mu$ или, иными словами, числу делителей наибольшего общего делителя чисел $\lambda$ и $\mu$ ( $\lambda , \mu =1,2, \ldots , n$ ), равен единице.

Задача 8.32

Пусть $a_{0}, a_{1}, \ldots , a_{n}$ — произвольные числа и

A_{\nu }=\sum _{t \leqslant \nu } a_{t} \quad (\nu =0,1, \ldots , n) .

Показать, что

\left|\begin{array}{cccccc} A_{0} & A_{0} & A_{0} & A_{0} & \ldots & A_{0} \\ A_{0} & A_{1} & A_{1} & A_{1} & \ldots & A_{1} \\ A_{0} & A_{1} & A_{2} & A_{2} & \ldots & A_{2} \\ A_{0} & A_{1} & A_{2} & A_{3} & \ldots & A_{3} \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ A_{0} & A_{1} & A_{2} & A_{3} & \ldots & A_{n} \end{array}\right|=a_{0} a_{1} a_{2} \ldots a_{n} .

Здесь общий элемент $c_{\lambda \mu }$ определителя равен $A_{r}$ , где $r=\operatorname {Min}(\lambda , \mu )$ ( $\lambda , \mu =0,1, \ldots , n$ ). (Обобщение тождества 30.)

Задача 8.33

Пусть $a_{1}, a_{2}, \ldots , a_{n}$ — произвольные числа и

A_{\nu }=\sum _{t \mid \nu } a_{t} \quad (\nu =1,2, \ldots , n) .

Показать, что

\left|\begin{array}{cccccc} A_{1} & A_{1} & A_{1} & A_{1} & \ldots & A_{1} \\ A_{1} & A_{2} & A_{1} & A_{2} & \ldots & A_{(2, n)} \\ A_{1} & A_{1} & A_{3} & A_{1} & \ldots & A_{(3, n)} \\ A_{1} & A_{2} & A_{1} & A_{4} & \ldots & A_{(4, n)} \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ A_{1} & A_{(n, 2)} & A_{(n, 3)} & A_{(n, 4)} & \ldots & A_{n} \end{array}\right|=a_{1} a_{2} a_{3} \ldots a_{n} .

Здесь общий элемент $c_{\lambda \mu }$ определителя равен $A_{r}$ , где $r=(\lambda , \mu )$ ( $\lambda , \mu =1,2, \ldots , n$ ). (Обобщение теоремы 31.)

Задача 8.34

Если $a_{0}, a_{1}, a_{2}, \ldots$ произвольны и

A_{n}=\sum _{t \leqslant n} a_{t} \quad (n=0,1,2, \ldots ),

то, очевидно,

a_{0}=A_{0}, \quad a_{1}=A_{1}-A_{0}, \quad a_{2}=A_{2}-A_{1}, \ldots , a_{n}=A_{n}-A_{n-1}, \ldots

При произвольных $a_{1}, a_{2}, a_{3}, \ldots$ и

A_{n}=\sum _{t \mid n} a_{t} \quad (n=1,2,3, \ldots )

имеем

\begin{gathered} a_{1}=A_{1}, \quad a_{2}=A_{2}-A_{1}, \quad a_{3}=A_{3}-A_{1}, \quad a_{4}=A_{4}-A_{2}, \\ a_{5}=A_{5}-A_{1}, \quad a_{6}=A_{6}-A_{3}-A_{2}+A_{1}, \ldots \end{gathered}

и вообще

a_{n}=\sum _{t \mid n} \mu (t) A_{\frac{n}{t}} \quad (n=1,2,3, \ldots ),

где $\mu (n)$ — функция Мёбиуса.

Примечание.

Функция Мёбиуса $\mu (n)$ определяется в списке теоретико-числовых функций, открывающем § 5 настоящей главы: $\mu (1)=1$ , $\mu (n)=0$ , если $n$ делится на квадрат какого-либо целого числа (кроме единицы), и $\mu (n)=(-1)^{\nu (n)}$ в остальных случаях, где $\nu (n)$ — число различных простых множителей числа $n$ .

Задача 8.35

Пусть $\psi (y)$ — произвольная функция, определенная в интервале $0 \leqslant y \leqslant 1$ , и

\begin{aligned} & g(n)=\sum _{\nu =1}^{n} \psi \left(\frac{\nu }{n}\right), \\ & f(n)=\sum _{(r, n)=1} \psi \left(\frac{r}{n}\right), \end{aligned}

где последняя сумма распространена на значения $r$ , взаимно простые с $n$ и не превосходящие $n$ . Тогда

f(n)=\sum _{t \mid n} \mu (t) g\left(\frac{n}{t}\right)=\sum _{t \mid n} \mu \left(\frac{n}{t}\right) g(t) .

Примечание.

A. Hurwitz.

Задача 8.36

Как известно,

\prod _{\nu =1}^{n}\left(x-e^{\frac{2 \pi i \nu }{n}}\right)=x^{n}-1 .

Положим

\prod _{(r, n)=1}\left(x-e^{\frac{2 \pi i r}{n}}\right)=K_{n}(x),

где произведение распространено на значения $r$ , взаимно простые с $n$ и не превосходящие $n$ ( $n$ -й полином деления круга). Нулями полинома $x^{n}-1$ служат корни $n$ -й степени из единицы, нулями полинома $K_{n}(x)$ — примитивные корни $n$ -й степени из единицы. Доказать формулу

K_{n}(x)=\prod _{t \mid n}\left(x^{\frac{n}{t}}-1\right)^{\mu (t)} .

Задача 8.37

Показать, что

\sum _{(r, n)=1} e^{\frac{2 \pi i r}{n}}=\mu (n),

где $\mu (n)$ — функция Мёбиуса.

6 · Мультипликативные арифметические функции[30/100%]

Задача 8.43

Показать, что

n^{\alpha }, \sigma _{\alpha }(n), 2^{\nu (n)}, \mu (n), \lambda (n), \varphi (n)

— мультипликативные теоретико-числовые функции.

Задача 8.44

Пусть $n=p_{1}^{k_{1}} p_{2}^{k_{2}} \ldots p_{\nu }^{k_{\nu }}$ , где $p_{1}, p_{2}, \ldots , p_{\nu }$ — отличные друг от друга простые числа. Тогда

\sigma _{\alpha }(n)=\frac{1-p_{1}^{\alpha \left(k_{1}+1\right)}}{1-p_{1}^{\alpha }} \cdot \frac{1-p_{2}^{\alpha \left(k_{2}+1\right)}}{1-p_{2}^{\alpha }} \ldots \frac{1-p_{\nu }^{\alpha \left(k_{\nu }+1\right)}}{1-p_{\nu }^{\alpha }} ;

в частности,

\begin{aligned} & \sigma (n)=\frac{1-p_{1}^{k_{1}+1}}{1-p_{1}} \cdot \frac{1-p_{2}^{k_{2}+1}}{1-p_{2}} \ldots \frac{1-p_{\nu }^{k_{\nu }+1}}{1-p_{\nu }}, \\ & \tau (n)=\left(k_{1}+1\right)\left(k_{2}+1\right) \ldots \left(k_{\nu }+1\right) . \end{aligned}

Задача 8.45

Показать, что при $n>30$

\varphi (n)>\tau (n) .

Задача 8.46

Пусть $a, b, c, d, \ldots , k, l$ — целые положительные числа, $M$ — их наименьшее общее кратное, $(a, b),(a, c), \ldots ,(a, b, c), \ldots$ , как обычно, — наибольший общий делитель чисел $a$ и $b$ , соотв. $a$ и $c, \ldots$ , соотв. $a, b$ и $c, \ldots$ Если $f(n)$ — мультипликативная функция, то

\begin{aligned} & f(M) f((a, b)) f((a, c)) \ldots f((k, l)) f((a, b, c, d)) \ldots = \\ & =f(a) f(b) \ldots f(l) f((a, b, c)) \ldots \end{aligned}

(Аргументами функции $f(n)$ в правой части служат наибольшие общие делители всевозможных комбинаций из нечетного числа чисел $a, b, c, \ldots , k, l$ .)

Задача 8.47

Пусть $f(n)$ — мультипликативная теоретико-числовая функция. Тогда

\sum _{n=1}^{\infty } f(n) n^{-s}=\prod _{p}\left(1^{-s}+f(p) p^{-s}+f\left(p^{2}\right) p^{-2 s}+f\left(p^{3}\right) p^{-3 s}+\ldots \right),

где бесконечное произведение распространено на все простые числа $p$ и раскрывается таким образом, что составляются только произведения из конечного числа множителей, отличных от $1^{-s}$ .

Задача 8.48

$\zeta (s)=\prod_{p} \frac{1}{1-p^{-s}}$ .

Примечание.

Euler, Introductio in analysin infinitorum, т. 1, Opera omnia, серия 1, т. 8, стр. 288, Leipzig und Berlin, B. G. Teubner, 1922¹.

Леонард Эйлер, Введение в анализ бесконечно малых, ОНТИ, 1936. ↩

Задача 8.49

Показать, что

\begin{aligned} & \sum _{n=1}^{\infty } \sigma _{\alpha }(n) n^{-s}=\zeta (s) \zeta (s-\alpha ), \quad \sum _{n=1}^{\infty } 2^{\nu (n)} n^{-s}=\frac{\zeta (s)^{2}}{\zeta (2 s)}, \\ & \sum _{n=1}^{\infty } \lambda (n) n^{-s}=\frac{\zeta (2 s)}{\zeta (s)}, \quad \sum _{n=1}^{\infty } \varphi (n) n^{-s}=\frac{\zeta (s-1)}{\zeta (s)} . \end{aligned}

Задача 8.50

Обозначим через $a(n)$ наибольший нечетный делитель числа $n$ . Показать, что

a(1) 1^{-s}+a(2) 2^{-s}+\ldots +a(n) n^{-s}+\ldots =\frac{1-2^{1-s}}{1-2^{-s}} \zeta (s-1) .

Примечание.

E. Cesàro, задача, Mathesis, т. 6, стр. 192, 1886. Решение — Mantel, там же, т. 8, стр. 208, 1888.

Задача 8.51

Показать, что

\sum _{n=1}^{\infty } \Lambda (n) n^{-s}=\frac{\zeta ^{\prime }(s)}{\zeta (s)} .

Задача 8.52

\sum _{t \mid n} \mu (t)=\begin{cases} 1 & \text{ при } n=1, \\ 0 & \text{ при } n>1 . \end{cases}

Задача 8.53

\sum _{t \mid n} \lambda (t)=\begin{cases} 1, & \text{ если } n \text{ есть точный квадрат, } \\ 0, & \text{ если } n \text{ — не квадрат. } \end{cases}

Задача 8.54

$\sum_{t \mid n} \varphi (t)=n$ .

Задача 8.55

$\sum_{t \mid n} \frac{\mu (t)}{t}=\frac{\varphi (n)}{n}$ .

Задача 8.56

$\sum_{t \mid n} \Lambda (t)=\ln n$ .

Задача 8.57

\left|\begin{array}{cccc} (1,1) & (1,2) & \ldots & (1, n) \\ (2,1) & (2,2) & \ldots & (2, n) \\ \ldots & \ldots & \ldots & \ldots \\ (n, 1) & (n, 2) & \ldots & (n, n) \end{array}\right|=\varphi (1) \varphi (2) \ldots \varphi (n) .

Задача 8.58

Рассмотрим все возможные разложения $n=\alpha \beta$ четного числа $n$ такие, что $\alpha$ — нечетное (включая $\alpha =1$ ), $\beta$ — четное. Показать, что разность

\sum \beta -\sum \alpha

равна сумме делителей числа $\frac{n}{2}$ .

Примечание.

Jacobi, задача, Nouv. Ann., т. 11, стр. 45, 1852. Решение — A. Dallot и др., там же, т. 11, стр. 126, 186, 1852.

Задача 8.58.1

Пусть $P(n,k)$ обозначает число разложений числа $n$ в произведение $k$ множителей; в качестве множителей допускаются лишь целые положительные числа, большие 1, а два разложения считаются равными тогда и только тогда, когда они состоят из одних и тех же множителей, взятых в одном и том же порядке. Например, $P(12,2)=4$ и $P(12,3)=3$ , так как

12 = 2\cdot 6 = 6\cdot 2 = 3\cdot 4 = 4\cdot 3 = 3\cdot 2\cdot 2 = 2\cdot 3\cdot 2 = 2\cdot 2\cdot 3 .

Показать, что при $n\geq 2$

\mu (n) = -P(n,1)+P(n,2)-P(n,3)+\cdots ,

т. е. разность между числом «четных» и «нечетных» разложений, иными словами, разложений на четное и соответственно нечетное число множителей. Например,

\mu (12) = -1+4-3 = 0 .

Задача 8.58.1

12 = 2\cdot 6 = 6\cdot 2 = 3\cdot 4 = 4\cdot 3 = 3\cdot 2\cdot 2 = 2\cdot 3\cdot 2 = 2\cdot 2\cdot 3 .

Показать, что при $n\geq 2$

\mu (n) = -P(n,1)+P(n,2)-P(n,3)+\cdots ,

\mu (12) = -1+4-3 = 0 .

Задача 8.58.2

(Продолжение.) Показать, что

P(n,1) - \tfrac 12 P(n,2) + \tfrac 13 P(n,3) - \cdots

равно $1/m$ , если $n=p^m$ — $m$ -я степень простого числа $p$ , и равно 0, если $n$ делится более чем на одно простое число. В случае $n=12$ имеем

1 - \tfrac 42 + \tfrac 33 = 0 .

Задача 8.58.2

(Продолжение.) Показать, что

P(n,1) - \tfrac 12 P(n,2) + \tfrac 13 P(n,3) - \cdots

1 - \tfrac 42 + \tfrac 33 = 0 .

Задача 8.58.3

(Продолжение.) Если $n$ есть произведение $m$ различных простых множителей, то

P(n,k) = k!S_k^m

(ср. введение к задаче I 186).

Задача 8.58.3

(Продолжение.) Если $n$ есть произведение $m$ различных простых множителей, то

P(n,k) = k!S_k^m

(ср. введение к задаче I 186).

Задача 8.58.4

Если $p$ — простое число, а $m$ — целое положительное, то

P(p^m,k) = \binom {m-1}{k-1} .

(Для этого частного случая проверить 58.1 с помощью биномиальной теоремы; ср. также 58.2 с задачей I 38.)

Задача 8.58.4

Если $p$ — простое число, а $m$ — целое положительное, то

P(p^m,k) = \binom {m-1}{k-1} .

(Для этого частного случая проверить 58.1 с помощью биномиальной теоремы; ср. также 58.2 с задачей I 38.)

Задача 8.58.5

Пусть при $n>1$ через $Q(n)$ обозначено число различных разложений целого числа $n$ в произведение целых чисел, больших 1; два разложения не считаются различными, если они состоят из одних и тех же множителей, так что порядок множителей роли не играет (в противоположность 58.1); положим $Q(1)=1$ . Например, $Q(12)=4$ . Если $n$ есть произведение $m$ различных простых множителей, то

Q(n) = T_m

(ср. введение к задаче I 186).

Задача 8.58.5

Q(n) = T_m

(ср. введение к задаче I 186).

Задача 8.58.6

(Продолжение.) Показать, что

\sum _{n=1}^\infty Q(n)n^{-s} = \exp \left(\sum _{n=1}^\infty (\zeta (ns)-1)/n\right) .

Задача 8.58.6

(Продолжение.) Показать, что

\sum _{n=1}^\infty Q(n)n^{-s} = \exp \left(\sum _{n=1}^\infty (\zeta (ns)-1)/n\right) .

Задача 8.58.7

Пусть $n$ — целое положительное число,

n = 2^j p_1^{k_1}p_2^{k_2}\cdots p_\mu ^{k_\mu }q_1^{l_1}q_2^{l_2}\cdots q_\nu ^{l_\nu } ,

где $2, p_1,\ldots ,p_\mu ,q_1,\ldots ,q_\nu$ — отличные друг от друга простые числа, $p_1\equiv \cdots \equiv p_\mu \equiv 1$ , $q_1\equiv \cdots \equiv q_\nu \equiv 3 \pmod4$ . Положим

\delta (n) = (k_1+1)(k_2+1)\cdots (k_\mu +1) ,

если $l_1,l_2,\ldots ,l_\nu$ все четны, и $\delta (n)=0$ в остальных случаях. Показать, что $\delta (n)$ есть в действительности разность между числами делителей числа $n$ двух различных родов:

\delta (n) = \sum _{t'\mid n} (-1)^{(t'-1)/2} ,

где суммирование распространено на нечетные делители $t'$ числа $n$ .

( $4\delta (n)$ — число целых точек на окружности $x^2+y^2=n$ . Этот факт был открыт Гауссом.)

Задача 8.58.7

Пусть $n$ — целое положительное число,

n = 2^j p_1^{k_1}p_2^{k_2}\cdots p_\mu ^{k_\mu }q_1^{l_1}q_2^{l_2}\cdots q_\nu ^{l_\nu } ,

\delta (n) = (k_1+1)(k_2+1)\cdots (k_\mu +1) ,

\delta (n) = \sum _{t'\mid n} (-1)^{(t'-1)/2} ,

где суммирование распространено на нечетные делители $t'$ числа $n$ .

( $4\delta (n)$ — число целых точек на окружности $x^2+y^2=n$ . Этот факт был открыт Гауссом.)

Задача 8.58.8

Какие из функций $P(n,2), P(n,3), \ldots , Q(n)$ и $\delta (n)$ мультипликативны?

Задача 8.58.8

Какие из функций $P(n,2), P(n,3), \ldots , Q(n)$ и $\delta (n)$ мультипликативны?

Задача 8.59

Пусть $f(n)$ и $g(n)$ — мультипликативные теоретико-числовые функции. Тогда теоретико-числовая функция

h(n)=\sum _{t \mid n} f(t) g\left(\frac{n}{t}\right)

также мультипликативна.

Задача 8.60

Число различных правильных замкнутых $n$ -угольников равно $\frac{1}{2} \varphi (n)$ .

Задача 8.61

Сумма всех положительных правильных дробей, имеющих в несократимой форме знаменатель $n$ , равна $\frac{1}{2} \varphi (n)$ ( $n \geqslant 2$ ).

Задача 8.62

Пусть $a, b, c$ — целые положительные числа. Если $(a, b, c)=1$ , то между $c$ дробями

\frac{a}{c}, \frac{a+b}{c}, \frac{a+2 b}{c}, \ldots , \frac{a+(c-1) b}{c}

имеется $\frac{\varphi (b c)}{\varphi (b)}$ несократимых. Если $(a, b, c)>1$ , то все указанные дроби, очевидно, сократимы.

Примечание.

G. Frobenius; см. A. Errera, Rend. Palermo, т. 35, стр. 110, 1913.

Задача 8.63

Сколько несократимых имеется среди $n^{2}$ дробей

\begin{aligned} & \frac{1}{1}, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \ldots , \frac{1}{n}, \\ & \frac{2}{1}, \frac{2}{2}, \frac{2}{3}, \frac{2}{4}, \ldots , \frac{2}{n}, \\ & \frac{3}{1}, \frac{3}{2}, \frac{3}{3}, \frac{3}{4}, \ldots , \frac{3}{n}, \\ & \frac{n}{1}, \frac{n}{2}, \frac{n}{3}, \frac{n}{4}, \ldots , \frac{n}{n} ? \end{aligned}

Задача 8.64

(1)(2)(3)(4)

Обозначим через $\Phi (n)$ число несократимых среди следующих $n^{2}$ дробей:

\begin{array}{cccc} \frac{1+i}{n}, & \frac{1+2 i}{n}, & \ldots , & \frac{1+n i}{n}, \\ \frac{2+i}{n}, & \frac{2+2 i}{n}, & \ldots , & \frac{2+n i}{n}, \\ \ldots & \ldots & \ldots & \ldots \\ \frac{n+i}{n}, & \frac{n+2 i}{n}, & \ldots , & \frac{n+n i}{n} . \end{array}

( $i=\sqrt{-1}$ ; дробь $\frac{a+i b}{n}$ называется сократимой, если $(a, b, n)>1$ , и несократимой, если $(a, b, n)=1$ .) Функция $\Phi (n)$ обладает следующими свойствами:

(1)

$\Phi (m) \Phi (n)=\Phi (m n)$ для $(m, n)=1$ , $\Phi (1)=1$ , $\Phi \left(p^{k}\right)=p^{2 k}-p^{2 k-2}$ , если $p$ — простое число ( $k=1,2,3, \ldots$ );

(2)

$\Phi (n)=n^{2}\left(1-\frac{1}{p^{2}}\right)\left(1-\frac{1}{q^{2}}\right)\left(1-\frac{1}{r^{2}}\right) \ldots$ , где $p, q, r, \ldots$ — различные простые множители числа $n$ ;

(3)

$\sum_{t \mid n} \Phi (t)=n^{2}$ ;

(4)

$\sum_{n=1}^{\infty } \Phi (n) n^{-s}=\frac{\zeta (s-2)}{\zeta (s)}$ .

Доказать свойства (1), (2), (3) независимо друг от друга, исходя непосредственно из определения. Показать, кроме того¹, что

\begin{aligned} & (1) \Rightarrow (4),(2) \Rightarrow (4),(3) \Rightarrow (4), \\ & (4) \Rightarrow (1),(4) \Rightarrow (2),(4) \Rightarrow (3) . \end{aligned}

То есть из (1) следует (4), из (2) следует (4) и т. д. ↩

7 · Ряды Ламберта и смежные вопросы[24/100%]

Задача 8.65

Из тождества

\zeta (s) \sum _{n=1}^{\infty } a_{n} n^{-s}=\sum _{n=1}^{\infty } A_{n} n^{-s},

где $a_{1}, a_{2}, a_{3}, \ldots$ и $A_{1}, A_{2}, A_{3}, \ldots$ — постоянные коэффициенты, вытекает

\sum _{n=1}^{\infty } \frac{a_{n} x^{n}}{1-x^{n}}=\sum _{n=1}^{\infty } A_{n} x^{n}

и обратно. (В левой части второго равенства стоит так называемый ряд Ламберта.)

Задача 8.66

Тождества

\begin{gathered} \zeta (s)\left(1-2^{1-s}\right) \sum _{n=1}^{\infty } a_{n} n^{-s}=\sum _{n=1}^{\infty } B_{n} n^{-s}, \\ \sum _{n=1}^{\infty } \frac{a_{n} x^{n}}{1+x^{n}}=\sum _{n=1}^{\infty } B_{n} x^{n} \end{gathered}

равносильны.

Задача 8.67

Пусть между числами $a_{1}, a_{2}, a_{3}, \ldots$ и $A_{1}, A_{2}, A_{3}, \ldots$ имеет место то же соотношение, что и в задаче 65. Тогда

\prod _{n=1}^{\infty }\left(\frac{n}{x} \sin \frac{x}{n}\right)^{a_{n}}=\prod _{n=1}^{\infty }\left(1-\frac{x^{2}}{n^{2} \pi ^{2}}\right)^{A_{n}} .

Задача 8.68

Пусть между числами $a_{1}, a_{2}, a_{3}, \ldots$ и $B_{1}, B_{2}, B_{3}, \ldots$ имеет место то же соотношение, что и в задаче 66. Тогда

\prod _{n=1}^{\infty }\left(\frac{x}{2 n} \operatorname {ctg} \frac{x}{2 n}\right)^{a_{n}}=\prod _{n=1}^{\infty }\left(1-\frac{x^{2}}{n^{2} \pi ^{2}}\right)^{B_{n}} .

Задача 8.68.1

Положим

f(x)+f(2x)+\cdots +f(nx)+\cdots = F(x) .

Тогда, в обозначениях 65,

\sum _{n=1}^\infty a_nF(nx) = \sum _{n=1}^\infty A_nf(nx) .

(Как связан этот результат с 65 и 67?)

Задача 8.68.1

Положим

f(x)+f(2x)+\cdots +f(nx)+\cdots = F(x) .

Тогда, в обозначениях 65,

\sum _{n=1}^\infty a_nF(nx) = \sum _{n=1}^\infty A_nf(nx) .

(Как связан этот результат с 65 и 67?)

Задача 8.68.2

Положим

f(x)-f(2x)+\cdots +(-1)^{n-1}f(nx)+\cdots = G(x) .

Тогда, в обозначениях 66,

\sum _{n=1}^\infty a_nG(nx) = \sum _{n=1}^\infty B_nf(nx) .

(Как связан этот результат с 66 и 68?)

Задача 8.68.2

Положим

f(x)-f(2x)+\cdots +(-1)^{n-1}f(nx)+\cdots = G(x) .

Тогда, в обозначениях 66,

\sum _{n=1}^\infty a_nG(nx) = \sum _{n=1}^\infty B_nf(nx) .

(Как связан этот результат с 66 и 68?)

Задача 8.68.3

Каждое из следующих двух равенств влечет за собой другое:

F(x) = \sum _{n=1}^\infty f(nx) , \qquad f(x) = \sum _{n=1}^\infty \mu (n)F(nx) .

Задача 8.68.3

Каждое из следующих двух равенств влечет за собой другое:

F(x) = \sum _{n=1}^\infty f(nx) , \qquad f(x) = \sum _{n=1}^\infty \mu (n)F(nx) .

Задача 8.69

Показать, что

\sum _{n=1}^{\infty } \frac{\mu (n) x^{n}}{1-x^{n}} \text{ и } \sum _{n=1}^{\infty } \frac{\varphi (n) x^{n}}{1-x^{n}}

являются рациональными функциями от $x$ . Какими именно?

Задача 8.70

$\sum_{n=1}^{\infty } \frac{\lambda (n) x^{n}}{1-x^{n}}=x+x^{4}+x^{9}+x^{16}+x^{25}+\ldots$

Примечание.

Baschwitz, задача, Mathesis (2), т. 3, стр. 80, 1893. Решение — E. Cesàro, там же (2), т. 3, стр. 205, 1893; Laguerre, Oeuvres, т. 1, стр. 216, Paris, Gauthier-Villars, 1898.

Задача 8.71

Показать, что

\sum _{n=1}^{\infty } \frac{\mu (n) x^{n}}{1+x^{n}}=x-2 x^{2}, \quad \sum _{n=1}^{\infty } \frac{\varphi (n) x^{n}}{1+x^{n}}=x \frac{1+x^{2}}{\left(1-x^{2}\right)^{2}} .

Задача 8.72

\sum _{n=1}^{\infty } \lambda (n) \frac{x^{n}}{1+x^{n}}=x-2 x^{2}+x^{4}-2 x^{8}+x^{9}+x^{16}-2 x^{13}+x^{25}-\ldots =\sum _{n=1}^{\infty } b_{n} x^{n},

где $b_{n}=1$ , если $n$ — квадрат, $b_{n}=-2$ , если $n$ — удвоенный квадрат, и $b_{n}=0$ во всех остальных случаях.

Задача 8.72.1

\prod _{1}^\infty \left(1-x^n\right)^{\frac{\mu (n)}{n}} = e^{-x} , \qquad \prod _{1}^\infty \left(1-x^n\right)^{\frac{\varphi (n)}{n}} = e^{-\frac{x}{1-x}} .

Задача 8.72.1

\prod _{1}^\infty \left(1-x^n\right)^{\frac{\mu (n)}{n}} = e^{-x} , \qquad \prod _{1}^\infty \left(1-x^n\right)^{\frac{\varphi (n)}{n}} = e^{-\frac{x}{1-x}} .

Задача 8.73

\sum _{n=1}^{\infty } \Phi (n) \frac{x^{n}}{1-x^{n}}=x \frac{1+x}{(1-x)^{3}},

\sum _{n=1}^{\infty } \Phi (n) \frac{x^{n}}{1+x^{n}}=x \frac{1+2 x+6 x^{2}+2 x^{3}+x^{4}}{\left(1-x^{2}\right)^{3}} .

Задача 8.74

$\sum_{n=1}^{\infty } \tau (n) x^{n}=\sum_{n=1}^{\infty } \frac{x^{n}}{1-x^{n}}=x \frac{1+x}{1-x}+x^{4} \frac{1+x^{2}}{1-x^{2}}+x^{9} \frac{1+x^{3}}{1-x^{3}}+\ldots$

Задача 8.74.1

\sum _{n=1}^\infty \delta (n)x^n = \frac{x}{1-x}-\frac{x^3}{1-x^3}+\frac{x^5}{1-x^5}-\frac{x^7}{1-x^7}+\cdots .

Примечание.

Ср. задачу 58.7.

Задача 8.74.1

\sum _{n=1}^\infty \delta (n)x^n = \frac{x}{1-x}-\frac{x^3}{1-x^3}+\frac{x^5}{1-x^5}-\frac{x^7}{1-x^7}+\cdots .

Примечание.

Ср. задачу 58.7.

Задача 8.75

$\sum_{n=1}^{\infty } \sigma (n) x^{n}=\sum_{n=1}^{\infty } n \frac{x^{n}}{1-x^{n}}=\frac{x}{(1-x)^{2}}+\frac{x^{3}}{\left(1-x^{2}\right)^{2}}+$

+\frac{x^{3}}{\left(1-x^{3}\right)^{2}}+\ldots =\frac{x+2 x^{2}-5 x^{5}-7 x^{7}+\ldots }{1-x-x^{2}+x^{5}+x^{7}-\ldots } .

Показатели степеней в последней дроби составлены по формуле $\frac{1}{2}\left(3 k^{2} \pm k\right)$ . [I 54.] Вывести отсюда рекуррентную формулу для $\sigma (n)$ .

Примечание.

Euler, Opera omnia, серия 1, т. 2, стр. 373, Leipzig, B. G. Teubner, 1915.

Задача 8.75.1

\sum _{n=1}^\infty \sigma (n)x^n = \frac{x+2x^2-5x^5-7x^7+{+}-{-}\cdots }{1-x-x^2+x^5+x^7-{-}+{+}\cdots } .

Примечание.

Ср. задачу I 54.

Задача 8.75.1

\sum _{n=1}^\infty \sigma (n)x^n = \frac{x+2x^2-5x^5-7x^7+{+}-{-}\cdots }{1-x-x^2+x^5+x^7-{-}+{+}\cdots } .

Примечание.

Ср. задачу I 54.

Задача 8.75.2

3\sum _{n=1}^\infty \sigma (n)x^n = \frac{3x-15x^3+42x^6-90x^{10}+\cdots }{1-3x+5x^3-7x^6+9x^{10}-\cdots } .

Задача 8.75.2

3\sum _{n=1}^\infty \sigma (n)x^n = \frac{3x-15x^3+42x^6-90x^{10}+\cdots }{1-3x+5x^3-7x^6+9x^{10}-\cdots } .

Задача 8.75.3

\sigma (n) = \sigma (n-1)+\sigma (n-2)-\sigma (n-5)-\sigma (n-7)+{+}-{-}\cdots .

Члены в правой части имеют вид

(-1)^{k-1}\sigma \left(n-\frac{3k^2\pm k}{2}\right) , \qquad \text{где} \quad 1\leq \frac{3k^2\pm k}{2}\leq n .

Там, где встречается до сих пор не определенный символ $\sigma (0)$ , следует подставить вместо него $n$ .

Задача 8.75.3

\sigma (n) = \sigma (n-1)+\sigma (n-2)-\sigma (n-5)-\sigma (n-7)+{+}-{-}\cdots .

Члены в правой части имеют вид

(-1)^{k-1}\sigma \left(n-\frac{3k^2\pm k}{2}\right) , \qquad \text{где} \quad 1\leq \frac{3k^2\pm k}{2}\leq n .

Там, где встречается до сих пор не определенный символ $\sigma (0)$ , следует подставить вместо него $n$ .

Задача 8.75.4

\sigma (n) = 3\sigma (n-1)-5\sigma (n-3)+7\sigma (n-6)-9\sigma (n-10)+{-}\cdots .

Члены в правой части имеют вид

(-1)^{k-1}(2k+1)\sigma \left(n-\frac{k(k+1)}{2}\right) , \qquad \text{где} \quad 1\leq \frac{k(k+1)}{2}\leq n .

Там, где встречается символ $\sigma (0)$ , следует подставить вместо него $n/3$ .

Задача 8.75.4

\sigma (n) = 3\sigma (n-1)-5\sigma (n-3)+7\sigma (n-6)-9\sigma (n-10)+{-}\cdots .

Члены в правой части имеют вид

(-1)^{k-1}(2k+1)\sigma \left(n-\frac{k(k+1)}{2}\right) , \qquad \text{где} \quad 1\leq \frac{k(k+1)}{2}\leq n .

Там, где встречается символ $\sigma (0)$ , следует подставить вместо него $n/3$ .

Задача 8.75.5

Пользуясь определением числа $p(n)$ разбиений числа $n$ , данным в задаче I 20.1 (Приложение), доказать, что

\sigma (n)+\sigma (n-1)+2\sigma (n-2)+\cdots +p(n-1)\sigma (1) = \sum _{k=0}^{n-1} p(k)\sigma (n-k) = np(n) .

Задача 8.75.5

Пользуясь определением числа $p(n)$ разбиений числа $n$ , данным в задаче I 20.1 (Приложение), доказать, что

\sigma (n)+\sigma (n-1)+2\sigma (n-2)+\cdots +p(n-1)\sigma (1) = \sum _{k=0}^{n-1} p(k)\sigma (n-k) = np(n) .

Задача 8.76

Значение выражения

\frac{1}{1-q}+\frac{p}{1-q x}+\frac{p^{2}}{1-q x^{2}}+\frac{p^{3}}{1-q x^{3}}+\ldots

не изменяется при перестановке чисел $p$ и $q$ .

Задача 8.77

$\frac{x}{1+x^{2}}+\frac{x^{3}}{1+x^{4}}+\frac{x^{3}}{1+x^{6}}+\frac{x^{4}}{1+x^{8}}+\ldots =$

=\frac{x}{1-x}-\frac{x^{3}}{1-x^{3}}+\frac{x^{5}}{1-x^{5}}-\frac{x^{7}}{1-x^{7}}+\ldots

Задача 8.78

$\frac{x}{1-x}=\frac{x}{1-x^{2}}+\frac{x^{2}}{1-x^{4}}+\frac{x^{4}}{1-x^{8}}+\frac{x^{8}}{1-x^{16}}+\ldots =$

=\frac{x}{1+x}+\frac{2 x^{2}}{1+x^{2}}+\frac{4 x^{4}}{1+x^{4}}+\frac{8 x^{8}}{1+x^{8}}+\ldots

8 · Дальнейшие задачи о подсчёте целых точек[7/86%]

Задача 8.79

Показать, что

\tau (1)+\tau (2)+\ldots +\tau (n)=\left[\frac{n}{1}\right]+\left[\frac{n}{2}\right]+\ldots +\left[\frac{n}{n}\right] .

Примечание.

Обе части представляют число целых точек, заключенных в фигуре $x>0, y>0, x y \leqslant n$ ¹.

Разобранную в задачах 28–42 аналогию (часть, делитель) можно было бы здесь проследить несколько дальше. ↩

Задача 8.80

Пусть $\nu =\left[\sqrt{n}\right]$ . Показать, что

\tau (1)+\tau (2)+\ldots +\tau (n)=2 \left[\frac{n}{1}\right]+2 \left[\frac{n}{2}\right]+\ldots +2 \left[\frac{n}{\nu }\right]-\nu ^{2} .

Задача 8.80.1

Пусть $U(n)$ обозначает наименьшее общее кратное чисел $1,2,3,\ldots ,n$ . Показать, что

\Lambda (1)+\Lambda (2)+\Lambda (3)+\cdots +\Lambda (n) = \log U(n) .

Задача 8.80.1

Пусть $U(n)$ обозначает наименьшее общее кратное чисел $1,2,3,\ldots ,n$ . Показать, что

\Lambda (1)+\Lambda (2)+\Lambda (3)+\cdots +\Lambda (n) = \log U(n) .

Задача 8.80.2

Обозначим через $\pi (x)$ число простых чисел, не превосходящих $x$ . Так, $\pi (1)=0$ , $\pi (10)=4$ , $\pi (100)=25$ . Показать, что

\Lambda (1)+\Lambda (2)+\cdots +\Lambda (n) \leq \pi (n)\log n .

Задача 8.80.2

Обозначим через $\pi (x)$ число простых чисел, не превосходящих $x$ . Так, $\pi (1)=0$ , $\pi (10)=4$ , $\pi (100)=25$ . Показать, что

\Lambda (1)+\Lambda (2)+\cdots +\Lambda (n) \leq \pi (n)\log n .

Задача 8.81

Пусть

\sum _{k=1}^{\infty } a_{k} k^{-s} \sum _{l=1}^{\infty } b_{l} l^{-s}=\sum _{n=1}^{\infty } c_{n} n^{-s} .

Тогда между суммами коэффициентов

\begin{gathered} a_{1}+a_{2}+\ldots +a_{n}=A_{n}, \quad b_{1}+b_{2}+\ldots +b_{n}=B_{n}, \\ c_{1}+c_{2}+\ldots +c_{n}=\Gamma _{n} \end{gathered}

имеет место следующее соотношение:

\Gamma _{n}=\sum _{r=1}^{n} a_{r} B_{\left[\frac{n}{r}\right]}=\sum _{s=1}^{n} b_{s} A_{\left[\frac{n}{s}\right]} .

Задача 8.82

Показать, что

\ln n!=\sum _{p \leqslant n} \ln p\left(\left[\frac{n}{p}\right]+\left[\frac{n}{p^{2}}\right]+\left[\frac{n}{p^{3}}\right]+\ldots \right),

где суммирование распространяется на все простые числа $p$ , не превосходящие $n$ .

Задача 8.83

В обозначениях задачи 81 имеет место также соотношение

\Gamma _{n}=\sum _{r=1}^{\nu } a_{r} B_{\left[\frac{n}{r}\right]}+\sum _{s=1}^{\nu } b_{s} A_{\left[\frac{n}{s}\right]}-A_{\nu } B_{\nu },

где $\nu =\left[\sqrt{n}\right]$ .

Арифметические функции

Footnotes

Footnotes

Footnotes