Show that for all $k\geq 1$, we have $$|S_{\mathrm{prim}}(p^{2k})| \geq \frac{1}{2}p^{2k}.$$

Let $(u,v)\in\mathbb{Z}^2\setminus(0,0)$. Let $p$ be a prime number congruent to 1 modulo 4 and $\alpha\geq 2$. Show that $L(u,v,p^\alpha)=0$ as soon as $p^{\alpha-1}$ does not divide $u^2+v^2$. Deduce that if $\alpha\geq 3$, then $L_{\mathrm{prim}}(u,v,p^\alpha)=0$ as soon as $p^{\alpha-2}$ does not divide $u^2+v^2$.

Let $(u,v)\in\mathbb{Z}^2\setminus(0,0)$ and $p$ a prime number congruent to 1 modulo 4. Show that if $p$ does not divide $u^2+v^2$, then $$|L_{\mathrm{prim}}(u,v,p)| \leq 2 \quad \text{and} \quad |L_{\mathrm{prim}}(u,v,p^2)| \leq 1.$$

For every integer $d\geq 2$, we denote by $\mathcal{P}(d)$ the set of prime numbers dividing $d$.
Show the inequality $$d \geq |\mathcal{P}(d)|!$$ Deduce that $$|\mathcal{P}(d)| = \underset{d\rightarrow+\infty}{o}(\log(d)).$$

Let $d$ be an odd integer. Show that $$|S_{\mathrm{prim}}(d^2)| \geq d^2\, 2^{-|\mathcal{P}(d)|}.$$ Deduce that, for all $\varepsilon>0$, we have $$d^{2-\varepsilon} = \underset{d\rightarrow+\infty}{o}\left(S_{\mathrm{prim}}(d^2)\right).$$

Let $(u,v)\neq(0,0)$. Show the existence of a constant $C$ (depending on $(u,v)$) such that for all $d>0$, $$|L_{\mathrm{prim}}(u,v,d)| \leq C\, 2^{|\mathcal{P}(d)|}.$$ Deduce that, for all $\varepsilon>0$, we have $$|L_{\mathrm{prim}}(u,v,d)| = \underset{d\rightarrow+\infty}{o}\left(d^\varepsilon\right).$$

For every integer $k \geqslant 2$, we set $\zeta(k) = \sum_{n=1}^{+\infty} n^{-k}$. Let $s, n \in \mathbb{N}^*$ with $2 \leqslant s \leqslant n$. We randomly draw $s$ numbers from $\{1, 2, \ldots, n\}$ and we denote $P_n(s)$ the probability that these numbers are coprime. Show that $$\lim_{n \rightarrow +\infty} P_n(s) = \frac{1}{\zeta(s)}$$ and give the value of $\lim_{n \rightarrow +\infty} P_n(s)$ in the case where $s = 2$, then $s = 4$, and finally $s = 6$.

Calculate $$\sum_{\sigma \in \mathfrak{S}_n} \varepsilon(\sigma), \quad \sum_{\sigma \in \mathfrak{S}_n} \varepsilon(\sigma) \nu(\sigma) \quad \text{and} \quad \sum_{\sigma \in \mathfrak{S}_n} \frac{\varepsilon(\sigma)}{\nu(\sigma)+1}.$$

Establish that $$\operatorname{Card}\left\{\sigma \in \mathfrak{S}_n : \varepsilon(\sigma) = 1\right\} = \operatorname{Card}\left\{\sigma \in \mathfrak{S}_n : \varepsilon(\sigma) = -1\right\}$$ and deduce the probability that a permutation of $\mathfrak{S}_n$ drawn uniformly at random has a prescribed signature.

For $\sigma \in \mathfrak{S}_n$, specify the condition on $\nu(\sigma)$ for which $\sigma \in \mathfrak{D}_n$. Deduce that $$\operatorname{Card}\left\{\sigma \in \mathfrak{D}_n : \varepsilon(\sigma) = 1\right\} = \operatorname{Card}\left\{\sigma \in \mathfrak{D}_n : \varepsilon(\sigma) = -1\right\} + (-1)^{n-1}(n-1).$$

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

Let $n$ be a non-zero natural integer. For any permutation $\sigma \in \mathfrak{S}_n$, we recall that there exists, up to order, a unique decomposition $\sigma = c_1 c_2 \cdots c_{\omega(\sigma)}$, where $\omega(\sigma) \in \mathbb{N}^*$ and $c_1, \ldots, c_{\omega(\sigma)}$ are cycles with disjoint supports of respective lengths $\ell_1 \leqslant \ell_2 \leqslant \cdots \leqslant \ell_{\omega(\sigma)}$ and $\ell_1 + \ell_2 + \cdots + \ell_{\omega(\sigma)} = n$. We thus obtain a map $\omega : \mathfrak{S}_n \rightarrow \mathbb{N}$. For an integer $k$ at most $n$, we denote by $s(n,k)$ the number of permutations of $\mathfrak{S}_n$ such that $\omega(\sigma) = k$. We consider, on the probability space $(\mathfrak{S}_n, \mathscr{P}(\mathfrak{S}_n))$ equipped with the uniform probability, the random variable $X_n$ defined by $X_n(\sigma) = \omega(\sigma)$.
Calculate, for $n \in \{2, 3, 4\}$, the quantity $\frac{1}{n!} \sum_{\sigma \in \mathfrak{S}_n} \omega(\sigma)$.

Let $n$ be a non-zero natural integer. For any permutation $\sigma \in \mathfrak{S}_n$, we recall that there exists, up to order, a unique decomposition $\sigma = c_1 c_2 \cdots c_{\omega(\sigma)}$, where $\omega(\sigma) \in \mathbb{N}^*$ and $c_1, \ldots, c_{\omega(\sigma)}$ are cycles with disjoint supports of respective lengths $\ell_1 \leqslant \ell_2 \leqslant \cdots \leqslant \ell_{\omega(\sigma)}$ and $\ell_1 + \ell_2 + \cdots + \ell_{\omega(\sigma)} = n$. For an integer $k$ at most $n$, we denote by $s(n,k)$ the number of permutations of $\mathfrak{S}_n$ such that $\omega(\sigma) = k$.
Specify $s(n,n)$ and $s(n,1)$ then show that, for $2 \leqslant k \leqslant n-1$, we have $$s(n,k) = s(n-1,k-1) + (n-1)s(n-1,k).$$ For $\sigma \in \mathfrak{S}_n$, one may distinguish the cases $\sigma(1) = 1$ and $\sigma(1) \neq 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.$$ Let $\left(a_n\right)_{n \geqslant 2}$ be a sequence of real numbers. For $t \in \mathbb{R}$, we set $A(t) = \sum_{2 \leqslant k \leqslant t} a_k$. Let $b : [2, +\infty[ \rightarrow \mathbb{R}$ be a function of class $\mathscr{C}^1$. Show that for any integer $n \geqslant 2$, $$\sum_{k=2}^{n} a_k b(k) = A(n)b(n) - \int_2^n b'(t) A(t) \, \mathrm{d}t$$

The objective of this question is to prove that if $n$ is a non-zero natural integer, then $\prod_{\substack{p \leqslant n \\ p \text{ prime}}} p \leqslant 4^{n}$.
Handle the cases $n \in \{1, 2, 3\}$.

The objective of this question is to prove that if $n$ is a non-zero natural integer, then $\prod_{\substack{p \leqslant n \\ p \text{ prime}}} p \leqslant 4^n$.
Handle the cases $n \in \{1, 2, 3\}$.

Let $n$ be a non-zero natural integer and let $p$ be a prime number. Justify the formula $\nu_{p}(n!) = \sum_{k=1}^{+\infty} E\left(\frac{n}{p^{k}}\right)$ and show that $$\frac{n}{p} - 1 < \nu_{p}(n!) \leqslant \frac{n}{p} + \frac{n}{p(p-1)}$$

Let $n$ be a non-zero natural integer and let $p$ be a prime number. Justify the formula $\nu_p(n!) = \sum_{k=1}^{+\infty} E\left(\frac{n}{p^k}\right)$ and show that $$\frac{n}{p} - 1 < \nu_p(n!) \leqslant \frac{n}{p} + \frac{n}{p(p-1)}$$

Justify that $n! = \prod_{\substack{p \leqslant n \\ p \text{ prime}}} p^{\nu_{p}(n!)}$ and deduce that $$n \sum_{\substack{p \leqslant n \\ p \text{ prime}}} \frac{\ln(p)}{p} - n\ln(4) < \ln(n!) \leqslant n \sum_{\substack{p \leqslant n \\ p \text{ prime}}} \frac{\ln(p)}{p} + n \sum_{\substack{p \leqslant n \\ p \text{ prime}}} \frac{\ln(p)}{p(p-1)}.$$

Conclude that $\sum_{\substack{p \leqslant n \\ p \text{ prime}}} \frac{\ln(p)}{p} \underset{n \rightarrow +\infty}{=} \ln(n) + O(1)$.

Justify that $n! = \prod_{\substack{p \leqslant n \\ p \text{ prime}}} p^{\nu_p(n!)}$ and deduce that $$n \sum_{\substack{p \leqslant n \\ p \text{ prime}}} \frac{\ln(p)}{p} - n\ln(4) < \ln(n!) \leqslant n \sum_{\substack{p \leqslant n \\ p \text{ prime}}} \frac{\ln(p)}{p} + n \sum_{\substack{p \leqslant n \\ p \text{ prime}}} \frac{\ln(p)}{p(p-1)}.$$

For all real $t \geqslant 2$, we define $$R(t) = \sum_{\substack{p \leqslant t \\ p \text{ prime}}} \frac{\ln(p)}{p} - \ln(t)$$ Show, using the result from question 16, that $$\sum_{\substack{p \leqslant n \\ p \text{ prime}}} \frac{1}{p} = 1 + \ln_{2}(n) - \ln_{2}(2) + \frac{R(n)}{\ln(n)} + \int_{2}^{n} \frac{R(t)}{t(\ln(t))^{2}} \mathrm{~d}t$$

For all real $t \geqslant 2$, we define $$R(t) = \sum_{\substack{p \leqslant t \\ p \text{ prime}}} \frac{\ln(p)}{p} - \ln(t)$$ Justify that the function $t \mapsto \frac{R(t)}{t(\ln(t))^{2}}$ is integrable on $[2, +\infty[$.

For all real $t \geqslant 2$, we define $$R(t) = \sum_{\substack{p \leqslant t \\ p \text{ prime}}} \frac{\ln(p)}{p} - \ln(t)$$ Establish that $\sum_{\substack{p \leqslant n \\ p \text{ prime}}} \frac{1}{p} \underset{n \rightarrow +\infty}{=} \ln_{2}(n) + c_{1} + O\left(\frac{1}{\ln(n)}\right)$, for a real $c_{1} \in \mathbb{R}$ to be determined.

We set, for all real $t \geqslant 2$, $$R(t) = \sum_{\substack{p \leqslant t \\ p \text{ prime}}} \frac{\ln(p)}{p} - \ln(t)$$ Establish that $\sum_{\substack{p \leqslant n \\ p \text{ prime}}} \frac{1}{p} \underset{n \rightarrow +\infty}{=} \ln_2(n) + c_1 + O\left(\frac{1}{\ln(n)}\right)$, for a real $c_1 \in \mathbb{R}$ to be determined.