Exercice 10, § 12

Soient t, n, k trois entiers $\geq 1$ tels que $t \leq n$ et que n divise $2^k - 1$. Soit S le plus petit ensemble d’entiers tel que $\{1, t\} \subset S \subset \{1, n\}$ et que la condition « $i \in S,\ 2i \equiv j$ mod. n et $1 \leq j \leq n$ » implique $j \in S$. Posons $m = \mathrm{Card}\ S$. Soit $\xi$ un élément d’ordre n de $\mathbf{F}_{2^k}^*$. Posons $P(X) = \prod_{j \in S} (X - \xi^j)$. a) Prouver que $P(X) \in \mathbf{F}_2[X]$. b) Montrer que si $R(X) \in \mathbf{F}_2[X]$ est de degré < n et est un multiple non nul de P(X), il a strictement plus de t coefficients non nuls. c) En déduire la construction d’une application $\varphi : \mathbf{F}_2^n \to \mathbf{F}_2^m$ telle que si $u,\ v \in \mathbf{F}_2^n$ sont distincts et ont au plus t coordonnées distinctes on ait $\varphi(u) \neq \varphi(v)$. d) Calculer S, m et P lorsque $t = 6,\ n = 15,\ k = 4$.