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

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

The Möbius function $\mu$ is 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.

The Möbius function $\mu$ is 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)$$

The Euler totient function $\varphi$ is 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$, so that $\chi_n(\lambda) = \operatorname{det}\left(\lambda I_n - H_n\right)$ for all real $\lambda$. 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).$$

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