Let $n \in \mathbb { N }$ and $\gamma = \left( \gamma _ { 1 } , \ldots , \gamma _ { 2 n + 2 } \right)$ be a Dyck path of length $2 n + 2$. Let $r = \max \left\{ i \in \llbracket 0 , n \rrbracket \mid s _ { \gamma } ( 2 i ) = 0 \right\}$. We assume $0 < r < n$ and we consider the paths $\alpha = \left( \gamma _ { 1 } , \ldots , \gamma _ { 2 r } \right)$ and $\beta = \left( \gamma _ { 2 r + 2 } , \ldots , \gamma _ { 2 n + 1 } \right)$. Justify using a figure that $\gamma _ { 2 r + 1 } = 1 , \gamma _ { 2 n + 2 } = - 1$ and that $\alpha$ and $\beta$ are Dyck paths.

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

Show that, for every natural integer $n$, $$C_{n} = \frac{(2n)!}{(n+1)! \, n!}$$

Show that, for every natural integer $n$, $$C_{n} = \frac{(2n)!}{(n+1)! \, n!}$$

Deduce $\forall n \in \mathbb { N } , C _ { n } = \frac { 1 } { n + 1 } \binom { 2 n } { n }$.

We call a cycle of length $k$ with values in $\llbracket 1,n \rrbracket$, any $(k+1)$-tuple $\vec{\imath} = (i_{1}, i_{2}, \ldots, i_{k}, i_{1})$ of elements of $\llbracket 1,n \rrbracket$. We denote $|\vec{\imath}|$ the number of distinct vertices of the cycle $\vec{\imath}$.
Show that the number of cycles of length $k$ in $\llbracket 1,n \rrbracket$ passing through $\ell$ distinct vertices is at most $n^{\ell} \ell^{k}$.

Show that the number of cycles of length $k$ in $\llbracket 1,n \rrbracket$ passing through $\ell$ distinct vertices is at most $n^{\ell} \ell^{k}$.

We classify cycles of length $k$ into three subsets:

• the set $\mathcal{A}_{k}$, consisting of cycles where at least one edge appears only once;
• the set $\mathcal{B}_{k}$, consisting of cycles where all edges appear exactly twice;
• the set $\mathcal{C}_{k}$, consisting of cycles where all edges appear at least twice and there exists at least one that appears at least three times.

Show that, for every cycle $\vec{\imath}$ belonging to $\mathcal{C}_{k}$, $|\vec{\imath}| \leqslant \frac{k+1}{2}$.

Cycles of length $k$ are classified into three subsets: the set $\mathcal{A}_{k}$, consisting of cycles where at least one edge appears only once; the set $\mathcal{B}_{k}$, consisting of cycles where all edges appear exactly twice; the set $\mathcal{C}_{k}$, consisting of cycles where all edges appear at least twice and there exists at least one that appears at least three times.
Show that, for any cycle $\vec{\imath}$ belonging to $\mathcal{C}_{k}$, $|\vec{\imath}| \leqslant \frac{k+1}{2}$.

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

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