(a) Show that if $\alpha \in \mathbb { Q }$ is an algebraic integer, then $\alpha \in \mathbb { Z }$.
(b) Show that if $\alpha \in \mathbb { C }$ is an algebraic integer then $\Pi _ { \alpha } \in \mathbb { Z } [ X ]$.
Hint: use the theorem admitted in the introduction (the set of algebraic integers is a subring of $\mathbb{C}$) as well as question 5a.

(a) Let $\alpha \in \mathbb { C }$ be an algebraic integer of degree 2 and of modulus 1. Show that $\alpha$ is a root of unity.
(b) Show that $\frac { 3 + 4 i } { 5 }$ is an algebraic number of degree 2 and of modulus 1 but is not a root of unity.

Show that for all $n \geq 1$ we have $$X ^ { n } - 1 = \prod _ { d \mid n } \Phi _ { d }$$ the product being taken over the set of positive integers $d$ dividing $n$, where $\Phi_n = \prod_{z \in \mathbb{P}_n}(X - z)$ and $\mathbb{P}_n$ is the set of primitive $n$-th roots of unity.

Let $n$ be a non-zero natural number. We set $$\Phi_n : \left\lvert\, \begin{aligned} \{0,1\}^n &\rightarrow \llbracket 0, 2^n - 1 \rrbracket \\ (x_j)_{j \in \llbracket 1,n \rrbracket} &\mapsto \sum_{j=1}^{n} x_j 2^{n-j} \end{aligned} \right.$$
Show that $\Phi_n$ is well-defined by verifying $\operatorname{Im} \Phi_n \subset \llbracket 0, 2^n - 1 \rrbracket$.

(a) Show that if $p$ is a prime number and $k \geq 1$ is an integer, then $$\Phi _ { p ^ { k } } = X ^ { ( p - 1 ) p ^ { k - 1 } } + X ^ { ( p - 2 ) p ^ { k - 1 } } + \cdots + X ^ { p ^ { k - 1 } } + 1$$ (b) Calculate $\Phi _ { n }$ for $n = 1,2,3,4,5,6$.

Let $n$ be a non-zero natural number. We set $$\Phi_n : \left|\, \begin{aligned} \{0,1\}^n &\rightarrow \llbracket 0, 2^n - 1 \rrbracket \\ (x_j)_{j \in \llbracket 1,n \rrbracket} &\mapsto \sum_{j=1}^{n} x_j 2^{n-j} \end{aligned} \right.$$
Show that $\Phi_n$ is well-defined by verifying $\operatorname{Im} \Phi_n \subset \llbracket 0, 2^n - 1 \rrbracket$.

We fix an integer $n \geq 2$.
(a) Calculate $\Phi _ { n } ( 0 )$.
(b) Calculate $\Phi _ { n } ( 1 )$ as a function of the prime factorization of $n$. Hint: reason by induction on $n$, using question 7.

Show that $\Phi _ { n } \in \mathbb { Z } [ X ]$.

Let $P \in \mathbb { Z } [ X ]$ be a monic polynomial of degree $n \geq 1$, irreducible in $\mathbb { Q } [ X ]$ and all of whose complex roots have modulus 1. Let $z _ { 1 } , \ldots , z _ { n }$ be the complex roots of $P$ counted with their multiplicities, so that $P = \prod _ { i = 1 } ^ { n } \left( X - z _ { i } \right)$. For every integer $k \geq 0$ we denote $a _ { k } = z _ { 1 } ^ { k } + z _ { 2 } ^ { k } + \cdots + z _ { n } ^ { k }$.
(a) Show that the series $\sum _ { k \geq 0 } a _ { k } z ^ { k }$ converges for all $z \in \mathbb { C }$ such that $| z | < 1$.
(b) Let $z \in \mathbb { C }$ be non-zero such that $| z | < 1$ and let $f ( z )$ be the sum of the series $\sum _ { k \geq 0 } a _ { k } z ^ { k }$. Show that $$z f ( z ) P \left( \frac { 1 } { z } \right) = P ^ { \prime } \left( \frac { 1 } { z } \right)$$ (c) Deduce that $a _ { k } \in \mathbb { Z }$ for all $k \geq 0$.

Let $P \in \mathbb { Z } [ X ]$ be a monic polynomial of degree $n \geq 1$, irreducible in $\mathbb { Q } [ X ]$ and all of whose complex roots have modulus 1. Let $z _ { 1 } , \ldots , z _ { n }$ be the complex roots of $P$ counted with their multiplicities. For every integer $k \geq 0$ we denote $a _ { k } = z _ { 1 } ^ { k } + z _ { 2 } ^ { k } + \cdots + z _ { n } ^ { k }$.
(a) Show that there exist two integers $0 \leq k < l$ such that $a _ { k + i } = a _ { l + i }$ for all $i \in \{ 0,1 , \ldots , n \}$. We fix two such integers $k , l$ in questions 12b and 12c.
(b) Show that $\sum _ { i = 1 } ^ { n } F \left( z _ { i } \right) \left( z _ { i } ^ { l } - z _ { i } ^ { k } \right) = 0$ for every polynomial $F \in \mathbb { C } [ X ]$ of degree at most $n$.
(c) Show that $z _ { 1 } , z _ { 2 } , \ldots , z _ { n }$ are pairwise distinct. Deduce that $z _ { i } ^ { l - k } = 1$ for all $i \in \{ 1,2 , \ldots , n \}$ and conclude.

Let $z \in \mathbb { P } _ { n }$ and let $p$ be a prime number not dividing $n$.
(a) Let $F , G \in \mathbb { Z } [ X ]$. Show that there exists $H \in \mathbb { Z } [ X ]$ such that $$( F + G ) ^ { p } = F ^ { p } + G ^ { p } + p H$$ (b) Show that $\Pi _ { z } \in \mathbb { Z } [ X ]$ and deduce the existence of a polynomial $F \in \mathbb { Z } [ X ]$ such that $$\Pi _ { z } \left( X ^ { p } \right) = \Pi _ { z } ( X ) ^ { p } + p F ( X )$$ (c) Show that $\frac { \Pi _ { z } \left( z ^ { p } \right) } { p }$ is an algebraic integer.

Let $z \in \mathbb { P } _ { n }$ and let $p$ be a prime number not dividing $n$.
(a) Express as a function of $n$ the number $\prod _ { 1 \leq i < j \leq n } \left( z _ { i } - z _ { j } \right) ^ { 2 }$, where $z _ { 1 } , z _ { 2 } , \ldots , z _ { n }$ are the roots of the polynomial $P = X ^ { n } - 1$. Hint: One may consider the numbers $P ^ { \prime } \left( z _ { i } \right)$.
(b) Show that $\Pi _ { z } \left( z ^ { p } \right) = 0$. Hint: show that if $\Pi _ { z } \left( z ^ { p } \right) \neq 0$, then there exists an algebraic integer $u$ such that $n ^ { n } = u \cdot \Pi _ { z } \left( z ^ { p } \right)$.
(c) Conclude that $\Phi _ { n } = \Pi _ { z }$.

We denote by $\mathcal { S }$ the set of real numbers $\alpha \in ] 1 , + \infty [$ which are also algebraic integers of degree at least 2 and which satisfy $\max _ { \gamma \in C ( \alpha ) } | \gamma | = 1$.
Let $\alpha$ be an element of $\mathcal { S }$ and let $\gamma \in C ( \alpha )$ have modulus 1.
(a) Show that the minimal polynomial of $\alpha$ is reciprocal and that $\frac { 1 } { \alpha }$ is a conjugate of $\alpha$.
(b) Show that $\gamma$ is not a root of unity.
(c) Show that all conjugates of $\alpha$ other than $\frac { 1 } { \alpha }$ have modulus 1.

We denote by $\mathcal { S }$ the set of real numbers $\alpha \in ] 1 , + \infty [$ which are also algebraic integers of degree at least 2 and which satisfy $\max _ { \gamma \in C ( \alpha ) } | \gamma | = 1$.
Show that the degree of every element of $\mathcal { S }$ is an even integer, greater than or equal to 4.

For every integer $n > 1$, we define $P _ { n } \in \mathbb { Z } [ X ]$ by $$P _ { n } = X ^ { 4 } - ( 6 + n ) X ^ { 3 } + ( 10 + n ) X ^ { 2 } - ( 6 + n ) X + 1 .$$ Verify that $P _ { n }$ has no root in $\mathbb { Q }$ and that $P _ { n }$ has at least one real root strictly greater than 1. We fix such a root $\alpha _ { n }$ in the sequel.

We have $D = \bigcup_{n \in \mathbb{N}^{\star}} D_n$ where $D_n = \left\{\sum_{j=1}^{n} \frac{x_j}{2^j}, (x_j)_{j \in \llbracket 1,n \rrbracket} \in \{0,1\}^n\right\}$.
Is the set $D$ countable?

We denote $D = \bigcup_{n \in \mathbb{N}^{\star}} D_n$ where $D_n = \left\{ \sum_{j=1}^{n} \frac{x_j}{2^j},\, (x_j)_{j \in \llbracket 1,n \rrbracket} \in \{0,1\}^n \right\}$.
Is the set $D$ countable?

Suppose that there exists $f : \mathbb{N} \rightarrow \mathcal{P}(\mathbb{N})$ bijective. By considering $A = \{x \in \mathbb{N} \mid x \notin f(x)\}$, establish a contradiction.

Using the results of the previous questions (in particular that $\Lambda$ is a bijection from $\{0,1\}^{\mathbb{N}}$ to $[0,1[$, and that $\mathcal{P}(\mathbb{N})$ is not countable), conclude that $[0,1[$ is not countable.

5. In the remainder of this part, $p$ denotes a fixed odd prime integer. One may use without proof Wilson's theorem: $$(p-1)! + 1 \equiv 0 \quad [p]$$ We denote by $\mathbb{Z}_p$ the field $\mathbb{Z}/p\mathbb{Z}$ and if $a \in \mathbb{Z}$, we denote by $\bar{a}$ its class in $\mathbb{Z}_p$. For $1 \leq k \leq e_p$, we denote by $\mathcal{P}_k$ the set of subsets $P$ with $k$ elements of $\mathbb{Z}_p$ satisfying the condition $$\forall \alpha \in P, \quad \alpha + 1 \notin P.$$ a. For $P = \{\alpha_1, \ldots, \alpha_k\} \in \mathcal{P}_k$ and $\alpha \in \mathbb{Z}_p$, we set $\tau_\alpha(P) = \{\alpha_1 + \alpha, \ldots, \alpha_k + \alpha\}$. Show that the map $\alpha \mapsto \tau_\alpha$ is a homomorphism from $(\mathbb{Z}_p, +)$ to the group of bijections of $\mathcal{P}_k$. b. We define a relation $\mathscr{R}$ between elements of $\mathcal{P}_k$ as follows: if $A, B$ are in $\mathcal{P}_k$, $A \mathscr{R} B$ if and only if there exists $\alpha \in \mathbb{Z}_p$ such that $B = \tau_\alpha(A)$. Show that $\mathscr{R}$ is an equivalence relation on $\mathcal{P}_k$, and that each equivalence class has cardinality $p$ and admits a representative of the form $\{\bar{0}, \bar{a}_2, \ldots, \bar{a}_k\}$ with $0 < a_2 < \cdots < a_k < p$. We choose such a representative for each class and we denote by $R$ the set of representatives thus chosen. c. Prove that $$\overline{c_{p-1,k}} = \sum_{\{0, \ldots, a_k\} \in R} \sum_{1 \leq \ell \leq p-1} \bar{\ell}\, \overline{\ell+1}\, \overline{a_2 + \ell}\, \overline{a_2 + \ell + 1} \cdots \overline{a_k + \ell}\, \overline{a_k + \ell + 1}$$

6. a. For $q \in \mathbb{N}$, we set $S_q = \sum_{\ell=0}^{p-1} \ell^q$. Observe that $p$ divides $\sum_{\ell=0}^{p-1} ((\ell+1)^{q+1} - \ell^{q+1})$ and deduce by recursion that $p$ divides $S_q$ for $0 \leq q \leq p-2$. b. Let $Z = [z_{ij}]$ and $Z' = [z'_{ij}]$ be two square matrices of order $N$ with entries in $\mathbb{Z}$. We define the relation $Z \equiv Z'[p]$ by $z_{ij} \equiv z'_{ij}[p]$ for $1 \leq i, j \leq N$. Prove that $$(M_{p-1})^{(p-1)} \equiv (-1)^{(p-1)/2} \mathrm{Id} \quad [p].$$ c. What can be said about a polynomial $Q$ with integer coefficients such that $Q(M_{p-1}) \equiv 0[p]$?

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

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

The purpose of this question is to show that $\sqrt { 3 }$ is not an eigenvalue of a matrix in $S _ { 2 } ( \mathbb { Q } )$. We assume that there exists $M \in S _ { 2 } ( \mathbb { Q } )$ such that $\sqrt { 3 }$ is an eigenvalue of $M$.
2a. Using the irrationality of $\sqrt { 3 }$, show that the characteristic polynomial of $M$ is $X ^ { 2 } - 3$.
2b. Show that if $n \in \mathbb { Z }$, then $n ^ { 2 }$ is congruent to 0 or 1 modulo 3.
2c. Show that there does not exist a triple of integers $(x, y, z)$ that are coprime as a whole such that $x ^ { 2 } + y ^ { 2 } = 3 z ^ { 2 }$.
2d. Conclude.

The purpose of this question is to show that $\sqrt { 3 }$ is not an eigenvalue of a matrix in $S _ { 2 } ( \mathbb { Q } )$. We assume that there exists $M \in S _ { 2 } ( \mathbb { Q } )$ such that $\sqrt { 3 }$ is an eigenvalue of $M$.
2a. Using the irrationality of $\sqrt { 3 }$, show that the characteristic polynomial of $M$ is $X ^ { 2 } - 3$.
2b. Show that if $n \in \mathbb { Z }$, then $n ^ { 2 }$ is congruent to 0 or 1 modulo 3.
2c. Show that there does not exist a triple of integers $( x , y , z )$ that are coprime as a whole such that $x ^ { 2 } + y ^ { 2 } = 3 z ^ { 2 }$.
2d. Conclude.