You are told that $n = 110179$ is the product of two primes $p$ and $q$. The number of positive integers less than $n$ that are relatively prime to $n$ (i.e. those $m$ such that $\operatorname{gcd}(m,n) = 1$) is 109480. Write the value of $p + q$. Then write the values of $p$ and $q$.

Let $f ( n )$ denote the number of positive divisors of a natural number $n$, and let $a _ { 1 } , a _ { 2 } , a _ { 3 } , \cdots , a _ { 9 }$ be all positive divisors of 36. What is the value of $\sum _ { k = 1 } ^ { 9 } \left\{ ( - 1 ) ^ { f \left( a _ { k } \right) } \times \log a _ { k } \right\}$? [4 points]
(1) $\log 2 + \log 3$
(2) $2 \log 2 + \log 3$
(3) $\log 2 + 2 \log 3$
(4) $2 \log 2 + 2 \log 3$
(5) $3 \log 2 + 2 \log 3$

Let $X$ be a random variable that follows the zeta distribution with parameter $x > 1$, i.e. $$\forall n \in \mathbb{N}^{*}, \quad \mathbb{P}(X = n) = \frac{1}{\zeta(x) n^{x}}$$ Show that, for all $a \in \mathbb{N}^{*}$, $$\mathbb{P}\left(X \in a\mathbb{N}^{*}\right) = \frac{1}{a^{x}}$$

Justify that, for all $n \in \mathbb{N}^{*}$,
$$( f * g ) ( n ) = \sum _ { \left( d _ { 1 } , d _ { 2 } \right) \in \mathcal { C } _ { n } } f \left( d _ { 1 } \right) g \left( d _ { 2 } \right)$$
where $\mathcal{C}_n = \left\{ \left( d_1, d_2 \right) \in \left( \mathbb{N}^* \right)^2 \mid d_1 d_2 = n \right\}$.

Let $f$ and $g$ be two multiplicative functions. Show that if
$$\forall p \in \mathcal{P}, \quad \forall k \in \mathbb{N}^*, \quad f\left(p^k\right) = g\left(p^k\right)$$
then $f = g$.

Deduce that if $f$ and $g$ are two multiplicative functions, then $f * g$ is still multiplicative.

Let $f$ be a multiplicative function. Show that there exists a multiplicative function $g$ such that, for all $p \in \mathcal{P}$ and all $k \in \mathbb{N}^*$,
$$g\left(p^k\right) = -\sum_{i=1}^{k} f\left(p^i\right) g\left(p^{k-i}\right)$$
and that it satisfies $f * g = \delta$.

Let $\mu$ be the arithmetic function defined by
$$\mu(n) = \begin{cases} 1 & \text{if } n = 1 \\ (-1)^r & \text{if } n \text{ is the product of } r \text{ distinct prime numbers} \\ 0 & \text{otherwise} \end{cases}$$
Show that $\mu$ is multiplicative.

Let $\mu$ be the Möbius function defined by
$$\mu(n) = \begin{cases} 1 & \text{if } n = 1 \\ (-1)^r & \text{if } n \text{ is the product of } r \text{ distinct prime numbers} \\ 0 & \text{otherwise} \end{cases}$$
Show that $\mu * \mathbf{1} = \delta$.

Let $f \in \mathbb{A}$, and let $F \in \mathbb{A}$ such that, for all $n \in \mathbb{N}^*, F(n) = \sum_{d \mid n} f(d)$. Show that, for all $n \in \mathbb{N}^*$,
$$f(n) = \sum_{d \mid n} \mu(d) F\left(\frac{n}{d}\right)$$

We denote $\varphi$ the Euler totient function, defined by:
$$\forall n \in \mathbb{N}^*, \quad \varphi(n) = \operatorname{card}\{k \in \llbracket 1, n \rrbracket \mid k \wedge n = 1\}$$
Prove that $\varphi = \mu * \mathbf{I}$.

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 also define the Mertens function $M$, by setting, for all $n \in \mathbb{N}^*, M(n) = \sum_{k=1}^{n} \mu(k)$ where $\mu$ is the Möbius function.
Let $A_n = \left(a_{ij}\right)_{(i,j) \in \llbracket 1,n \rrbracket^2}$ be the matrix with general term
$$a_{ij} = \begin{cases} \mu(j) & \text{if } i = 1 \\ 1 & \text{if } i = j \\ 0 & \text{otherwise} \end{cases}$$
and $C_n = A_n H_n$. By computing the coefficients of $C_n$, show that $\operatorname{det} H_n = M(n)$.
For the computation of the term with index $(i,j)$ of $C_n$, one may distinguish the case $i = j = 1$, the case $i = 1, j > 1$ and the case $i > 1, j > 1$.

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$.

7. We recall that $\bar{E}_n$ denotes the class of $E_n = \operatorname{Card} \operatorname{MD}(n)$ in $\mathbb{Z}_p$. a. Show that $E_{2n+1} \equiv u_{2n}[p]$, where $u_m$ is the coefficient of the term $X$ in the decomposition of $\delta_{p-1}^m(X)$ in the basis $(X, \ldots, X^{p-1})$. b. Prove that the sequence $(\bar{E}_{2n+1})_{n \in \mathbb{N}}$ is periodic, with minimal period $(p-1)/2$ if $p \equiv 1\,[4]$ and minimal period $(p-1)$ if $p \equiv 3\,[4]$. c. Indicate the modifications to be made to the preceding questions to show an analogous result for the sequence $(\bar{E}_{2n})_{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)$.

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}).$$

For any non-zero natural integer $n$, we set $$\omega(n) = \operatorname{Card}\{p \text{ prime} : p \mid n\} = \sum_{\substack{p \mid n \\ p \text{ prime}}} 1.$$ Prove, using a summation interchange, that $\frac{1}{x} \sum_{n \leqslant x} \omega(n) \underset{x \rightarrow +\infty}{=} \ln_{2}(x) + O(1)$.

For any non-zero natural integer $n$, we set $$\omega(n) = \operatorname{Card}\{p \text{ prime} : p \mid n\} = \sum_{\substack{p \mid n \\ p \text{ prime}}} 1.$$ Show that $$\frac{1}{x} \sum_{n \leqslant x} \left(\omega(n) - \ln_{2}(x)\right)^{2} \underset{x \rightarrow +\infty}{=} \frac{1}{x}\left(\sum_{n \leqslant x} \omega(n)^{2}\right) - \ln_{2}(x)^{2} + O\left(\ln_{2}(x)\right).$$

For any non-zero natural integer $n$, we set $$\omega(n) = \operatorname{Card}\{p \text{ prime} : p \mid n\} = \sum_{\substack{p \mid n \\ p \text{ prime}}} 1.$$ Show that $$\sum_{n \leqslant x} \omega(n)^{2} = \sum_{\substack{p_{1} \leqslant x \\ p_{1} \text{ prime}}} \sum_{\substack{p_{2} \leqslant x \\ p_{2} \text{ prime}}} \operatorname{Card}\left\{n \in \mathbb{N}^{*} : n \leqslant x, p_{1} \mid n \text{ and } p_{2} \mid n\right\}$$

For any non-zero natural integer $n$, we set $$\omega(n) = \operatorname{Card}\{p \text{ prime} : p \mid n\} = \sum_{\substack{p \mid n \\ p \text{ prime}}} 1.$$ Conclude that $\frac{1}{x}\left(\sum_{n \leqslant x} \left(\omega(n) - \ln_{2}(x)\right)^{2}\right) \underset{x \rightarrow +\infty}{=} O\left(\ln_{2}(x)\right)$.

Show that for any non-zero natural integer $n$, $$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.$$

For any non-zero natural integer $n$, we set $$\omega(n) = \operatorname{Card}\{p \text{ prime} : p \mid n\} = \sum_{\substack{p \mid n \\ p \text{ prime}}} 1.$$ Prove, using a change of order of summation, that $\frac{1}{x} \sum_{n \leqslant x} \omega(n) \underset{x \rightarrow +\infty}{=} \ln_2(x) + O(1)$.