Let $f$ be an arithmetic function, $n \in \mathbb{N}^*$ and $g = f * \mu$. We denote $M = \left(m_{ij}\right)$ the matrix of $\mathcal{M}_n(\mathbb{C})$ with general term $m_{ij} = f(i \wedge j)$. We also define the divisor matrix $D = \left(d_{ij}\right)$ by:
$$d_{ij} = \begin{cases} 1 & \text{if } j \text{ divides } i \\ 0 & \text{otherwise} \end{cases}$$
Let $M'$ be the matrix with general term $m_{ij}' = \begin{cases} g(j) & \text{if } j \text{ divides } i, \\ 0 & \text{otherwise.} \end{cases}$
Using the result $M = M' D^\top$, deduce that the determinant of $M$ equals
$$\operatorname{det} M = \prod_{k=1}^{n} g(k)$$

Let $f$ be an arithmetic function. We define, for all real $s$ such that the series converges,
$$L_f(s) = \sum_{k=1}^{\infty} \frac{f(k)}{k^s}$$
We call abscissa of convergence of $L_f$
$$A_c(f) = \inf\left\{s \in \mathbb{R} \mid \text{the series } \sum \frac{f(k)}{k^s} \text{ converges absolutely}\right\}.$$
Show that if $s > A_c(f)$, then the series $\sum \frac{f(k)}{k^s}$ converges absolutely.

Let $f$ and $g$ be two arithmetic functions with finite abscissas of convergence. Show that if, for all $s > \max\left(A_c(f), A_c(g)\right), L_f(s) = L_g(s)$, then $f = g$.

Let $f$ and $g$ be two arithmetic functions with finite abscissas of convergence. Show that, for all $s > \max\left(A_c(f), A_c(g)\right)$,
$$L_{f*g}(s) = L_f(s) L_g(s)$$

Deduce property (S): The permutation matrices $P_\sigma$ and $P_\tau$ are similar if and only if the permutations $\sigma$ and $\tau$ are conjugate.
One may compute $T_\sigma D$ where $T_\sigma$ is the cycle type of $\sigma$ and $D$ is the divisor matrix defined in I.D.

We define the Redheffer matrix by $H_n = \left(h_{ij}\right)_{(i,j) \in \llbracket 1,n \rrbracket^2}$ where
$$h_{ij} = \begin{cases} 1 & \text{if } j = 1 \\ 1 & \text{if } i \text{ divides } j \text{ and } j \neq 1 \\ 0 & \text{otherwise.} \end{cases}$$
We denote $\chi_n$ the characteristic polynomial of $H_n$. For $\lambda$ real distinct from 1, we define by recursion the arithmetic function $\mathbf{b}$, by setting $\mathbf{b}(1) = 1$ and, for all natural integer $j \geq 2$,
$$\mathbf{b}(j) = \frac{1}{\lambda - 1} \sum_{d \mid j, d \neq j} \mathbf{b}(d)$$
We also define the matrix $B_n(\lambda) = \left(b_{ij}\right)_{(i,j) \in \llbracket 1,n \rrbracket^2}$ with general term
$$b_{ij} = \begin{cases} \mathbf{b}(j) & \text{if } i = 1 \\ 1 & \text{if } i = j \\ 0 & \text{otherwise.} \end{cases}$$
By computing the product $B_n(\lambda)\left(\lambda I_n - H_n\right)$, show that
$$\chi_n(\lambda) = (\lambda - 1)^n - (\lambda - 1)^{n-1} \sum_{j=2}^{n} \mathbf{b}(j).$$

In the rest of the problem, we assume that $\lambda$ is a real distinct from 1 and we set $w = \frac{1}{\lambda - 1}$. We further set $\mathbf{f} = (1 + w)\delta - w\mathbf{1}$.
Show that $\mathbf{f} * \mathbf{b} = \delta$.

We assume that $\lambda$ is a real distinct from 1 and we set $w = \frac{1}{\lambda - 1}$. We further set $\mathbf{f} = (1 + w)\delta - w\mathbf{1}$.
Using the notations of Dirichlet series given in subsection I.E, express, for values of the real $s$ to be specified, $L_{\mathbf{f}}(s)$ in terms of $w$ and $L_{\mathbf{1}}(s)$.

We assume that $\lambda$ is a real distinct from 1 and we set $w = \frac{1}{\lambda - 1}$. We further set $\mathbf{f} = (1 + w)\delta - w\mathbf{1}$. We denote $\log_2$ the logarithm function in base 2, defined by $\log_2(x) = \frac{\ln(x)}{\ln(2)}$ for all real $x > 0$.
Show that, for $s$ real sufficiently large,
$$\frac{1}{L_{\mathbf{f}}(s)} = 1 + \sum_{m=2}^{\infty} m^{-s} \sum_{k=1}^{\lfloor \log_2 m \rfloor} w^k D_k(m)$$
where $D_k(m)$ is the number of ways to decompose the integer $m$ into a product of $k$ factors greater than or equal to 2, the order of these factors being important.

We assume that $\lambda$ is a real distinct from 1 and we set $w = \frac{1}{\lambda - 1}$. We denote $\log_2$ the logarithm function in base 2. For $n \geq 1$, we set $S_k(n) = \sum_{m=2}^{n} D_k(m)$. Deduce from the previous question that
$$\chi_n(\lambda) = (\lambda - 1)^n - \sum_{k=1}^{\lfloor \log_2 n \rfloor} (\lambda - 1)^{n-k-1} S_k(n).$$

We define the Redheffer matrix $H_n$ and its characteristic polynomial $\chi_n$. We denote $\log_2$ the logarithm function in base 2.
Finally, show that $H_n$ has 1 as an eigenvalue and that its multiplicity is exactly
$$n - \lfloor \log_2 n \rfloor - 1.$$

Let $s > 1$ be a real number and let $X$ be a random variable taking values in $\mathbb{N}^*$ following the zeta distribution with parameter $s$. If $n \in \mathbb{N}^*$, we denote $\{n \mid X\}$ the event ``$n$ divides $X$'' and $\{n \nmid X\}$ the complementary event.
Calculate $P(n \mid X)$ for $n \in \mathbb{N}^*$.

Let $s > 1$ be a real number and let $X$ be a random variable taking values in $\mathbb{N}^*$ following the zeta distribution with parameter $s$. If $n \in \mathbb{N}^*$, we denote $\{n \mid X\}$ the event ``$n$ divides $X$'' and $\{n \nmid X\}$ the complementary event.
Let $\left(\alpha_i\right)_{i \in \mathbb{N}^*}$ be a sequence of natural integers. Show that the events $$\left\{p_1^{\alpha_1} \mid X\right\}, \left\{p_2^{\alpha_2} \mid X\right\}, \ldots, \left\{p_k^{\alpha_k} \mid X\right\}, \ldots$$ are mutually independent.

If $n \in \mathbb{N}^*$, we denote, for $i \in \{0,1,2,3\}$, $$r_i(n) = \operatorname{Card}\{d \in \mathbb{N} : d \equiv i [4] \text{ and } d \mid n\}$$ We set $g(n) = r_1(n) - r_3(n)$.
Show that if $m$ and $n$ are two nonzero natural integers that are coprime, we have $g(mn) = g(m)g(n)$.

If $n \in \mathbb{N}^*$, we denote, for $i \in \{0,1,2,3\}$, $$r_i(n) = \operatorname{Card}\{d \in \mathbb{N} : d \equiv i [4] \text{ and } d \mid n\}$$ We set $g(n) = r_1(n) - r_3(n)$.
Show that, for all $n \in \mathbb{N}$, and all prime number $p$, we have $$g\left(p^n\right) = \begin{cases} 1 & \text{if } p = 2 \\ n+1 & \text{if } p \equiv 1 [4] \\ \frac{1}{2}\left(1+(-1)^n\right) & \text{if } p \equiv 3 [4] \end{cases}$$

Let $d$ be a nonzero integer and $u$ be an integer. Show that the sum $$\sum_{k\in\mathbb{Z}/d\mathbb{Z}} e^{\frac{2i\pi}{d}ku}$$ equals $d$ if $u\equiv 0\bmod d$ and $0$ otherwise.

Let $n$ be an integer coprime to $d$. Show that the map $$(a,b)\mapsto(na,nb)$$ is a bijection from $S_{\mathrm{prim}}(d)$ to $S_{\mathrm{prim}}(d)$.

Let $d_1$ and $d_2$ be two coprime integers and $m$ and $n$ be two integers such that $md_1+nd_2=1$. Show that the map $$\varphi:\left((a_1,b_1),(a_2,b_2)\right)\mapsto\left(nd_2 a_1+md_1 a_2,\, nd_2 b_1+md_1 b_2\right)$$ is a bijection from $S_{\mathrm{prim}}(d_1)\times S_{\mathrm{prim}}(d_2)$ to $S_{\mathrm{prim}}(d_1 d_2)$.

Let $d_1$ and $d_2$ be two coprime integers. Show that for all $(u,v)\in\mathbb{Z}^2$, $$L_{\mathrm{prim}}(u,v,d_1 d_2) = L_{\mathrm{prim}}(u,v,d_1)\,L_{\mathrm{prim}}(u,v,d_2).$$

Let $p$ be a prime number and $\alpha\geq 1$ be an integer. Show that $$L_{\mathrm{prim}}(u,v,p^\alpha) = L(u,v,p^\alpha) - L(u,v,p^{\alpha-1}).$$

Let $p$ be a prime number. Show that there exists $h\in\mathbb{Z}/p\mathbb{Z}$ such that $h^2=-1$ if and only if $p=2$ or $p\equiv 1\bmod 4$.

Assume that $p$ is a prime number congruent to 1 modulo 4. Show that $(a,b)\in S(p)$ if and only if $$b = ha \quad \text{or} \quad b = -ha$$ where $h$ is a solution of $h^2=-1\bmod p$.

Assume that $p$ is a prime number congruent to 1 modulo 4. Let $\alpha\geq 1$. Show that there exists $j\in\mathbb{Z}/p^\alpha\mathbb{Z}$ such that $j^2=-1$.

Assume that $p$ is a prime number congruent to 1 modulo 4, and fix $j\in\mathbb{Z}/p^\alpha\mathbb{Z}$ such that $j^2=-1$. Let $a\in\mathbb{Z}/p^\alpha\mathbb{Z}$ such that $p$ does not divide $a$. Show that $(a,b)\in S(p^\alpha)$ if and only if $$b = ja \quad \text{or} \quad b = -ja.$$

Assume that $p$ is a prime number congruent to 1 modulo 4, and fix $j\in\mathbb{Z}/p^\alpha\mathbb{Z}$ such that $j^2=-1$. Let $a\in\mathbb{Z}/p^\alpha\mathbb{Z}$ and $k\leq\alpha$ be the largest integer such that $p^k$ divides $a$. Show that if $k<\frac{\alpha}{2}$, then $(a,b)\in S(p^\alpha)$ if and only if $$b\equiv\pm ja\bmod p^{\alpha-k}$$ and that if $k\geq\frac{\alpha}{2}$, then $(a,b)\in S(p^\alpha)$ if and only if $p^{\lceil\frac{\alpha}{2}\rceil}$ divides $b$.