Conspectus materiae tomi XXX, fasciculi 3

<table><thead><tr><th></th><th>Pagina</th></tr></thead><tbody><tr><td>S. Agou, Critères d'irréductibilité des polynômes composés à coefficients dans un corps fini</td><td>213-223</td></tr><tr><td>B. Richter, Über die Monotonie von Differenzenfolgen</td><td>225-227</td></tr><tr><td>J. H. Conway and A. J. Jones, Trigonometric diophantine equations (On vanishing sums of roots of unity)</td><td>229-240</td></tr><tr><td>R. Terras, A stopping time problem on the positive integers</td><td>241-252</td></tr><tr><td>J. H. E. Cohn, The diophantine equations (x³-c)² = (t²±2)y²+1</td><td>253-255</td></tr><tr><td>P. Erdös and T. N. Shorey, On the greatest prime factor of 2p-1 for a prime p and other expressions</td><td>257-265</td></tr><tr><td>D. F. Coray, Algebraic points on cubic hypersurfaces</td><td>267-296</td></tr><tr><td>M. Bruneau, Comportement local des fonctions à série de Fourier lacunaire</td><td>297-305</td></tr></tbody></table>

La revue est consacrée à la Théorie des Nombres

The journal publishes papers on the Theory of Numbers

Die Zeitschrift veröffentlicht Arbeiten aus der Zahlentheorie

Журнал посвящен теории чисел

L'adresse de
la Rédaction
et de l'échange

Address of the
Editorial Board
and of the exchange

Die Adresse der
Schriftleitung und
des Austausches

Адрес редакции
и книгообмена

ACTA ARITHMETICA

ul. Śniadeckich 8, 00-950 Warszawa

Les auteurs sont priés d'envoyer leurs manuscrits en deux exemplaires

The authors are requested to submit papers in two copies

Die Autoren sind geboten um Zusendung von 2 Exemplaren jeder Arbeit

Рукописи статей редакция просит предлагать в двух эквомилярах

PRINTED IN POLAND

WROCLAWSKA DRUKARNIA NAUKOWA

Critères d'irréductibilite des polynômes
composés à coefficients dans un corps fini

par

SIMON AGOU (Lyon)

Dans ce qui suit, on considère un polynôme irréductible monique $f \in F_q[X]$, où $F_q$ est le corps fini ayant $q = p^s$ éléments, où $p$ est premier. On étudie l'irréductibilité des polynômes composés $f(g(X))$, obtenus en substituant divers polynômes moniques $g(X) \in F_q[X]$ à $X$ dans $f(X)$.

Je remercie M. L. Carlitz pour les suggestions et les indications bibliographiques qu'il m'a communiquées au cours de la rédaction de cet article.

1. Un lemme fondamental.

1.1. LEMME. Soient $f, g \in F_q[X]$ des polynômes moniques de degrés respectifs $n \ge 1$ et $m \ge 1$; on suppose $f$ irréductible. Pour que le polynôme $f(g(X))$ soit irréductible dans $F_q[X]$, il faut et il suffit que les coefficients dans $F_q[X]$ du polynôme

$$h(X, Y) = \prod_{k=0}^{m-1} (Y - X^{q^{kn}}) - g(Y) + g(0) - (-1)^m X^{\frac{(q^{mn}-1)(q^n-1)}{2}} \in F_q[X][Y]$$

appartiennent à l'vidéal $f(g(X)) F_q[X]$.

On note $\bar{F}_p$ la clôture algébrique $\bigcup_{r>0} F_{pr}$ de $F_p$.

Montrons que la condition est nécessaire. Comme $f$ et $f(g(X))$ sont irréductibles, il existe $\theta \in F_q^n$ et $\xi \in F_q^{mn}$ tels que

$$f(X) = \prod_{j=0}^{n-1} (X - \theta^{q^j}) \quad \text{et} \quad f(g(X)) = \prod_{i=0}^{mn-1} (X - \xi^{q^i}).$$

Puisque $\xi$ est racine de

$$f(g(X)) = \prod_{j=0}^{n-1} (g(X) - \theta^{q^j}),$$
il existe un unique $j$ tel que $0 \le j \le n-1$ et tel que $g(\xi) = \theta^{\theta^j}$. Les racines de $g(X) - \theta^{\theta^j}$ sont les $\xi^{q^{kn}}$ ($0 \le k \le m-1$); on a ainsi

$$g(X) - \theta^{\theta^j} = \prod_{k=0}^{m-1} (X - \xi^{q^{kn}}), \quad \theta^{\theta^j} = g(0) - (-1)^m N_{F_q^{mn}/F_q^n}(\xi)$$

et

$$g(X) - \theta^{\theta^j} = g(X) - g(0) + (-1)^m N_{F_q^{mn}/F_q^n}(\xi).$$

Ceci montre que $h(\xi, Y) = 0$. Les coefficients dans $F_q[X]$ du polynôme $h$ ont donc $\xi$ pour racine et, par suite, sont divisibles dans $F_q[X]$ par le polynôme minimal $f(g(X))$ de $\xi$ sur $F_q$.

La condition est suffisante. Soit $\xi \in \bar{F}_p$ une racine du polynôme $f(g(X))$. On a par hypothèse $h(\xi, Y) = 0$, c'est-à-dire $\prod_{k=0}^{m-1} (X - \xi^{q^{kn}}) = g(X) - \theta$, en posant $\theta = g(0) - (-1)^m \xi^{(q^{mn}-1)/(q^n-1)}$. Les coefficients du polynôme $g(X) - \theta$ appartiennent à $F_q$, à l'exception peut-être du terme constant $g(0) - \theta$. Par suite, pour tout $j \ge 0$, on a $g(X) - \theta^{\theta^j} = \prod_{k=0}^{m-1} (X - \xi^{q^j+kn})$. Comme $f(g(\xi)) = 0$ et $g(\xi) = \theta$, les racines de $f(X)$ dans $F_q^n$ sont $\theta, \theta^q, \dots, \theta^{q^{n-1}}$ et on a ainsi

$$f(g(X)) = \prod_{j=0}^{n-1} (g(X) - \theta^{\theta^j}) = \prod_{i=0}^{mn-1} (X - \xi^{\xi^i}).$$

Posons $g(X) = X^m + aX^{m-1} + \dots$. D'après l'hypothèse, $f(g(X))$ divise le coefficient dominant (dans $F_q[X]$) de $h[X, Y]$, qui est $-(a + \sum_{k=0}^{m-1} X^{q^{kn}})$; les racines de ce dernier polynôme sont simples puisque sa dérivée est $-1$. Par suite $f(g(X))$ est le polynôme minimal de $\xi$ sur $F_q$. D'où l'assertion.

**1.2.** Voici deux applications du lemme précédent. Soit $f(X) = X^3 + X^2 + 1 \in F_2[X]$; $f$ est irréductible. Soit $g(X) = X^3 + X^2 \in F_2[X]$. Avec les notations de 1.1, on a

$$f(g(X)) = X^9 + X^7 + X^5 + X^3 + 1$$

et

$$h(X, Y) = (X^{64} + X^8 + X) Y^2 + (X^{72} + X^{65} + X^9 + 1) Y.$$

Modulo $f(g(X))$, on a $X^9 \equiv X^7 + X^5 + X^3 + 1$; d'où l'on déduit facilement que

$$X^{64} \equiv X^8 + X \quad \text{et} \quad X^{72} \equiv X^{65} + X^9 + 1$$

et, par suite, que

$$X^{64} + X^8 + X \equiv 0 \quad \text{et} \quad X^{72} + X^{65} + X^9 + 1 \equiv 0.$$

Donc, $X^9 + X^7 + X^5 + X^3 + 1$ est irréductible sur $F_2$.

Soient maintenant $f(X) = X^2 + 1 \in F_3[X]$ et $g(X) = X^2 + X \in F_3[X]$. Avec les notations de 1.1, on a

$$f(g(X)) = X^4 + 2X^3 + X^2 + 1 \quad \text{et} \quad h(X, Y) = -Y(X^9 + X + 1).$$

Modulo $f(g(X))$, on a $X^9 \equiv 2X + 2$. D'après le lemme 1.1, $X^4 + 2X^3 + X^2 + 1$ est irréductible sur $F_3$.

**1.3. THÉORÈME.** Soit $u \in F_q[X]$ un polynôme monique et irréductible et soit $m$ un diviseur $> 0$ de $\deg(u)$. Pour qu'il existe des polynômes moniques $f, g \in F_q[X]$ tels que $u(X) = f(g(X))$ et $\deg(g) = m$, il faut et il suffit que dans $F_q[X]$,

$$-( -1)^m X^{(q^{\deg(u)-1})(q^{\deg(u)}/m-1)}$$

soit congru modulo $u(X)$ à un polynôme monique de degré $m$ de $F_q[X]$, ayant 0 pour racine.

La condition est nécessaire. Avec les notations de l'énoncé, soit $u = f(g(X))$ cet irréductible et soit $n = \deg(f)$. On a $\deg(u) = mn$. D'après le lemme 1.1, le polynôme $-g(X) + g(0) - (-1)^m X^{(q^{mn}-1)/(q^n-1)}$ appartient à l'idéal $u(X)$ $F_q[X]$.

La condition est suffisante. Soit $n = \deg(u)/m$ et soit $g \in F_q[X]$ un polynôme monique de degré $m$ tel que

$$g(X) - g(0) \equiv -(-1)^m X^{(q^{mn}-1)/(q^n-1)} \mod u(X).$$

Soit $\xi$ une racine de $u$ dans $F_q^{mn}$, on a $g(\xi) \in F_q^n$. Le polynôme

$$f(X) = \prod_{j=0}^{n-1} (X - (g(\xi))^{\theta^j})$$

appartient à $F_q[X]$. $f(g(X))$ est un polynôme monique, de degré $mn$, de $F_q[X]$, dont $\xi$ est une racine. Donc $f(g(X))$ est divisible dans $F_q[X]$ par le polynôme minimal $u(X)$ de cette racine. Donc $u = f(g(X))$.

**1.4.** Voici une application de ce résultat (cf. infra 3.1).

Soit

$$u(X) = X^6 + X^5 + X^3 + X^2 + 1 \in F_2[X];$$

ce polynôme est irréductible sur $F_2$. Avec les notations de 1.3, prenons $m=2$. On a

$$X^{(2^6-1)/(3^3-1)} = X^9.$$

Mais, modulo $u(X)$, on a :

$$X^6 \equiv X^5 + X^3 + X^2 + 1;$$

on en déduit que

$$X^3 \equiv X + 1,$$
donc que

$$X^9 \equiv X^2 + X.$$

Il existe par conséquent un polynôme irréductible $f(X) \in F_2[X]$ de degré 3 et $a \in F_2$ tels que:

$$u(X) = f(X^2 + X + a).$$

En posant $f(X) = X^3 + aX^2 + \beta X + \gamma$, $f_1(X) = X^2 + \beta$, $f_2(X) = X + a$ et $f_3(X) = 1$ on a:

$$u(X) = f(a) + (X^2 + X)f_1(a) + (X^2 + X)^2 f_2(a) + (X^2 + X)^3 f_3(a).$$

Par identification, on voit que

$$u(X) = (X^2 + X)^3 + (X^2 + X)^2 + 1 = (X^2 + X + 1)^3 + (X^2 + X + 1) + 1.$$

(On observera que la congruence $X^8 + X + 1 \equiv 0 \pmod{u(X)}$ redonne, dans ce cas particulier, du même coup, l'irréductibilité de $u(X)$ sur $F_2$.)

Dans les paragraphes suivants, nous allons donner d'autres applications de 1.1, retrouvant là et améliorant des résultats contenus dans [2], [3], [4] et [6].

## 2. Irréductibilité des polynômes $f(X^m)$ (cf. [3], § 34).

**2.1. LEMME.** Soient $f \in F_q[X]$ un polynôme de degré $n$ tel que $f(X) \neq X$ et $m$ un entier $> 0$ divisant $q^n - 1$.

(a) Les conditions suivantes sont équivalentes :

(i) Les coefficients dans $F_q[X]$ de

$$\prod_{k=0}^{m-1} (Y - X^{q^{kn}}) - Y^m - (-1)^m X^{(q^{mn}-1)/(q^n-1)} \in F_q[X, Y]$$

appartiennent à l'idéal $f(X^m) F_q[X]$;

(ii) Les coefficients dans $F_q[X]$ de

$$u(X, Y) = \prod_{k=0}^{m-1} (Y - X^{q^{kn}-1}) - Y^m - (-1)^m X^{(q^{mn}-1)/(q^n-1)-m}$$

appartiennent à $f(X^m) F_q[X]$;

(iii) Les coefficients de

$$v(X, Y) = \prod_{k=0}^{m-1} (Y - X^{(q^{kn}-1)/m}) - Y^m - (-1)^m X^{((q^{mn}-1)/(q^n-1)-m)/m}$$

appartiennent à $f(X) F_q[X]$.

(b) De plus, si l'on suppose $f$ irréductible sur $F_q$ et si $\xi \in \bar{F}_p$ est une racine de $f(X^m)$, ces conditions sont équivalentes à

(iv) $u(\xi, Y) = 0$.

(a) Comme $f(X) \neq X$, (i) et (ii) sont équivalentes. D'autre part, si $u, v$ et $w \in F_q[X]$ et si $w$ n'est pas constant, il est clair que, pour que $u$ divise $v$, il faut et il suffit que $u(w(X))$ divise $v(w(X))$. Cette remarque montre que (ii) et (iii) sont équivalentes.

(b) Il est clair que (ii) entraine (iv). Inversement, supposons (iv) vérifié. Les coefficients dans $F_q[X]$ de $v(X, Y)$ ont pour racine $\xi^m$, qui est racine du polynôme irréductible $f(X)$. D'où (iii).

**2.2. THÉORÈME.** Soit $f \in F_q[X]$ un polynôme monique, irréductible, de degré $n$ et d'exposant $e^{(1)}$ et soit $m$ un entier $> 0$ divisant $q^n - 1$ et tel que $(m, \frac{q^n-1}{e}) = 1$. Alors $f(X^m)$ est irréductible sur $F_q$.

On va montrer que $f$ vérifie la condition (iv) de 2.1. S'il en est ainsi, $f$ vérifie la condition (i) c'est-à-dire le lemme 1.1, où l'on fait $g(X) = X^m$, ce qui entraine alors le théorème.

Soient $d = \frac{q^n-1}{e}$, $\xi \in \bar{F}_p$ une racine de $f(X^m)$ et $\gamma$ un générateur de $F_q^*$. Comme $\xi^m \in F_q^*$, on a $\xi^m = \gamma^{ad}$ et on a $(a, m) = 1$. Donc $\eta = \gamma^{ad(q^n-1)/m}$ est une racine $m$-ème de 1 dans $F_q^*$, d'ordre $m$.

Comme $\xi^{q^{kn}-1} = \eta^k$, on a

$$\prod_{k=0}^{m-1} (Y - \xi^{q^{kn}-1}) = \prod_{k=0}^{m-1} (Y - \eta^k) = Y^m - 1.$$

De plus, si $a = \xi^{(q^{mn}-1)/(q^n-1)-m}$ on a

$$a = -(-1)^m.$$

Mais alors, avec les notations de 2.1, on a $u(\xi, Y) = -1 - (-1)^m \alpha = 0$. ■

**3. Irréductibilité des polynômes $f(X^p - X - b)$**. On rappelle que l'on a posé $q = p^s$.

**3.1. THÉORÈME.** Soit $f(X) = X^n + aX^{n-1} + \dots + a_n$ un polynôme irréductible de $F_q[X]$ et soit $b \in F_q$. Pour que le polynôme $f(X^p - X - b)$ soit irréductible, il faut et il suffit que

$$\mathrm{Tr}_{F_q/F_p}(a) \neq n \mathrm{Tr}_{F_q/F_p}(b).$$

Pour abréger, posons, pour $x \in F_q$,

$$\mathrm{Tr}(x) = \mathrm{Tr}_{F_q/F_p}(x) = x + w^p + \dots + w^{p^{s-1}}.$$

<footnote>(c) $e$ est, par définition, le plus petit entier $> 0$ tel que $f(X)$ divise $X^e - 1$ dans $F_q[X]$.</footnote>
(a) Dans $F_q[X, Y]$, on a

$$ \prod_{k=0}^{p-1} (Y - X - k \operatorname{Tr}(nb - a)) = (Y - X) \prod_{k=1}^{p-1} (Y - X - k \operatorname{Tr}(nb - a)) \\ = Y^p - X^p - (Y - X) (\operatorname{Tr}(nb - a))^{p-1}. $$

(b) Posons $T(X) = X + X^q + \dots + X^{q^{n-1}}$ et, pour $k > 0$,

$$ \Psi_k(X) = \sum_{i=0}^{kn s-1} X^{p^i}. $$

On a

$$ \Psi_k(X) = \sum_{i=0}^{s-1} (T(X)^{p^i} + \dots + T(X)^{p^{(k-1)s} + l}). $$

Puisque $f(X)$ est irréductible, on sait que $a+T(X) \equiv 0 \pmod{f(X)}$.
Donc

$$ \Psi_k(X) \equiv -k \operatorname{Tr}(a) \pmod{f(X)}. $$

Pour $k > 0$, on a

$$ \begin{aligned} X^{p^{kn s}} &\equiv \left( \sum_{i=0}^{kn s-1} (X^p - X - b)^{p^i} \right) + X + \operatorname{Tr}_{F_q(kn/p^i)}(b) \\ &\equiv \Psi_k(X^p - X - b) + X + kn \operatorname{Tr}(b). \end{aligned} $$

Par suite, pour $k \ge 0$, on a

$$ X^{p^{kn s}} \equiv X + k \operatorname{Tr}(nb - a) \pmod{f(X^p - X - b)}. $$

(c) D'après 1.1, pour que $f(X^p - X - b)$ soit irréductible, il faut et il suffit que les coefficients dans $F_q[X]$ du polynôme

$$ \prod_{k=0}^{p-1} (Y - X^q^{kn}) - (Y^p - Y) - (-1)^p X^{1+q^{n+\dots+q^{(p-1)n}}} \\ = \prod_{k=0}^{p-1} (Y - X^{p^{kn s}}) - (Y^p - Y) - (-1)^p \prod_{k=0}^{p-1} X^{p^{kn s}} $$

soient congrus à 0 modulo $f(X^p - X - b)$. D'après (a), cette condition est équivalente à la suivante:

$f(X^p - X - b)$ divise $1 - (\operatorname{Tr}(nb - a))^{p-1}$, ou encore $(\operatorname{Tr}(nb - a))^{p-1} = 1$, c'est-à-dire $\operatorname{Tr}(nb) \neq \operatorname{Tr}(a)$.

**3.2.** Le théorème 3.1 permet de retrouver divers résultats de L. E. Dickson.

En prenant $f(X) = X$, le théorème 3.1 redonne le résultat cité dans [3], p. 29.

En prenant $b=0$, on retrouve celui donné dans [3], p. 34.

Enfin, soient $f = X^n + aX^{n-1} + \dots \in F_q[X]$ un polynôme irréductible et $b \in F_q$. La méthode utilisée pour démontrer 3.1 permet de démontrer facilement les résultats suivants.

Pour que $f(X^q - X - b)$ soit irréductible, il faut et il suffit que $q = p$ et que $a \neq nb$; cf. [3], p. 30.

Pour que $f(X^q - X - b)$ soit irréductible, il faut et il suffit que $n = 1$, $q = p$ et $a \neq b$, par suite que $f(X^q - X - b) = X^p - X - b + a$.

Ce dernier résultat peut se déduire d'un théorème dû à A. F. Long ([4], p. 307); on notera que la condition $a \neq b$ est indispensable dans ce résultat. Nous allons développer ces dernières remarques.

**4.** **Irréductibilité des polynômes $f(X^p - X)$**. On pose toujours $q = p^s$.

**4.1.** **LEMME.** Soit $f \in F_q[X]$ un polynôme irréductible, de degré $n$. Soient $r$ un entier $> 0$ et $\mu = \text{ppcm}(r, ns)$. Alors on a

$$ X^{p^{\mu p}} - X \equiv 0 \pmod{f(X^p - X)}. $$

$f(X)$ divise $X^{p^{ns}} - X$ dans $F_q[X]$. Par suite, $f(X^p - X)$ divise $(X^p - X)^{p^{ns}} - (X^p - X)$ et donc $(X^{p^{ns}} - X)^{p^r} - (X^{p^{ns}} - X)$.

Les congruences suivantes sont écrites dans $F_q[X]$ modulo $f(X^p - X)$. Par récurrence sur $k \ge 0$, ce qui précède montre que

$$ (X^{p^{ns}} - X)^{p^{kr}} \equiv X^{p^{ns}} - X. $$

D'où, en faisant $k = \mu/r$,

$$ (X^{p^{ns}} - X)^{p^{\mu}} \equiv X^{p^{ns}} - X $$

et, pour tout $h \ge 0$ :

$$ X^{p^{hns+\mu}} \equiv X^{p^{hns}} + X^{p^{\mu}} - X. $$

En faisant $h = r/(r, sn)$, on a donc

$$ X^{p^{2\mu}} \equiv 2(X^{p\mu} - X) + X. $$

D'où, par récurrence sur $k \ge 0$ :

$$ (4.1.1) \qquad X^{p^{k\mu}} - X \equiv k(X^{p\mu} - X). $$

D'où le lemme, en faisant $k = p$.

**4.2.** **LEMME.** Soit $f \in F_q[X]$ un polynôme monique irréductible de degré $n$ et $r$ un entier $> 0$. Si $f(X^p - X)$ est irréductible sur $F_q$, alors $(r, ns) = 1$.

Soit $d$ un diviseur de $(r, ns)$.

(a) On a $X^p - X = (X^{p^d(r/d-1)} + \dots + X)^{p^d} - (X^{p^d(r/d-1)} + \dots + X)$. Donc $f(X^p - X)$ est irréductible aussi.
(b) Pour que $f(X^p - X)$ soit irréductible, il faut et il suffit, d'après 1.1, que la condition suivante soit vérifiée: les coefficients dans $F_q[X]$ de

$$ \prod_{k=0}^{p^d-1} (Y - X^{p^k n_s}) - (Y^{p^d} - Y) - (-1)^{p^d} X^{(p^{p^d n_s} - 1)/(p^{n_s} - 1)} $$

sont dans l'idéal $f(X^p - X) F_q[X]$.

(c) D'après (4.1.1), on a, pour $k \ge 0$,

$$ X^{p^{kns}} = X + k(X^{pn_s} - X) \mod f(X^p - X), $$

puisque le ppm de $\bar{d}$ et de $\bar{sn}$ est $\bar{sn}$.

D'autre part, dans $F_p[Y, Z]$, on a (théorème de Gauss-Wilson)

$$ \prod_{k=0}^{p^d-1} (Y - kZ) = Y^{p^d} - (Z^{p^d} Y)^{p^d-1}. $$

En substituant $X^{pn_s} - X$ à $Z$, on voit que la condition de (b) s'écrit encore: les coefficients dans $F_q[X]$ de $Y - Y^{p^d-1}(X^{pn_s} - X)^{(p-1)p^d-1}$ sont congrus à 0 modulo $f(X^p - X)$. Cette dernière condition est équivalente à $\bar{d} = 1$ et $(X^{pn_s} - X)^{p-1} \equiv 1 \mod f(X^p - X)$ ou encore à $\bar{d} = 1$ et $f(X^p - X)$ est irréductible.

$$ \text{D'où } (r, ns) = 1. $$

**4.3.** Le lemme 4.1 donne des précisions supplémentaires. En effet, avec les notations de ce lemme, $f(X^p - X)$ divise $X^{p^d} - X$. Comme $p^n$ divise $\frac{\mu p}{s} = \frac{npr}{(r, ns)}$, puisque $f(X^p - X)$ est irréductible, on a $p^{r-1} = r$. Mais alors on a $r = 1$ ou bien $p = 2, r = 2$ et $ns$ est impair. D'où le théorème suivant.

**4.4.** **THÉORÈME.** Soit $f \in F_q[X]$ un polynôme monique de degré $n$ et soit $r$ un entier $> 0$.

On suppose que $f(X^p - X)$ est irréductible sur $F_q$.

Pour que $f(X^p - X)$ soit irréductible, il faut et il suffit que l'une des deux conditions suivantes soit vérifiée:

(i) $r = 1$;

(ii) $p = 2, r = 2$ et $ns$ est impair.

Compte tenu de ce qui précède, il reste à prouver que si $ns$ est impair, $f(X^q - X)$ est irréductible sur $F_{2s}$. Or ceci résulte de 3.1, car $X^q - X = (X^2 - X)^2 - (X^2 - X)$ dans $F_{2s}[X]$ et le coefficient de $X^{2n-1}$ dans $f(X^2 - X)$ est $n$.

**4.5.** Comme il m'a été signalé par le rapporteur de cet article, ce résultat se déduit facilement de théorèmes dûs à A. F. Long [5], p. 65, th. 5.1 et 5.2, en procédant de la manière suivante:

Avec les notations de [5], pour que $f(X^p - X)$ soit irréductible, il est nécessaire que $r' = 1$. Mais alors la seule valeur de $t$ est $t = 1$ et donc $N(1, p^d)/1 = p^d$; mais $p^d \ne 1$ pour $d \ge 1$. Les conditions du théorème 5.1 ne sont donc pas réalisées.

Dans le théorème 5.2, nous devons avoir $l = 1$ et par suite $t = 1$. Pour établir que $f(X^p - X)$ est irréductible, nous devons écrire que

$$ N(1, p^k d) / p^{k+1} = 1. $$

Alors $p^k d = k+1$ et nous obtenons les deux solutions, en remarquant que $\bar{d} = (r, ns)$:

(a) $k=0, \bar{d}=1, r=1$;

(b) $p=2, k=1, \bar{d}=1$ et $r=2$.

Ce qui donne les conditions du théorème 4.4.

**5. Irréductibilité des polynômes $f(X^q - aX)$.**

**5.1.** Nous allons maintenant généraliser un résultat de O. Öre ([6], p. 262).

**THÉORÈME.** Soient $f \in F_q[X]$ un polynôme monique, irréductible, de degré $n$ et $a \in F_q^*$. Pour que $f(X^q - aX)$ soit irréductible, il faut et il suffit que $s = 1, a^n = 1$ et que $f(X)$ ne divise pas

$$ X^{p^{n-1}} + aX^{p^{n-2}} + \dots + a^{n-1}X. $$

(a) Par hypothèse $f(X)$ divise $X^q - X$; donc

$$ (X^q - aX)^{q^n} - (X^q - aX) \equiv 0 \mod f(X^q - aX). $$

On en déduit par récurrence sur $k \ge 0$ les congruences suivantes modulo $f(X^q - aX)$:

$$ X^{q^{kn}} \equiv \begin{cases} \frac{a^{kn}-1}{a^n-1} X^{qn} - \frac{a^{kn}-a^n}{a^n-1} X & \text{si } a^n \ne 1, \\ X + k(X^q - X) & \text{si } a^n = 1. \end{cases} $$

(b) Supposons $a^n \ne 1$ (donc $q \ne 2$). Supposons $f(X^q - aX)$ irréductible. Le lemme 1.1 montre alors que

$$ \sum_{k=0}^{q-1} X^{q^{kn}} \equiv 0 \mod f(X^q - aX). $$

D'après (a), modulo $f(X^q - aX)$ on a $\sum_{k=0}^{q-1} X^{q^{kn}} \equiv \frac{X^{q^n} - X}{a^n - 1}$; on a donc $X^{q^n} - X \equiv 0$, ce qui est absurde. Donc $a^n = 1$.
Plaçons nous dans ce cas. Pour que $f(X^2 - aX)$ soit irréductible, il faut et il suffit, d'après (1.1), que les coefficients dans $F_q[X]$ de

$$ \prod_{k=0}^{q-1} (Y - X^{q^{kn}}) - (Y^q - aY) - (-1)^q X^{(q^n q - 1)/(q^n - 1)} $$

soient congrus à 0 modulo $f(X^2 - aX)$.

Compte tenu de (a) et du théorème de Gauss-Wilson, cette condition est équivalente à la suivante: les coefficients dans $F_q[X]$ de $aY - (X^q - X)^{(p-1)p^{s-1}} Y^{p^{s-1}}$ sont congrus à 0 modulo $f(X^q - aX)$ c'est-à-dire à $s=1$ et

$$ (X^{p^n} - X)^{p-1} \equiv a \mod f(X^p - aX). $$

Posons alors

$$ u(X) = X^{p^{n-1}} + aX^{p^{n-2}} + \dots + a^{n-1}X; $$

on a

$$ u(X)^p - au(X) \equiv X^{p^n} - X = u(X^p - aX). $$

La condition précédente s'écrit encore

$$ u(X^p - aX)^{p-1} \equiv a \mod f(X^p - aX), $$

c'est-à-dire

$$ u(X)^{p-1} \equiv a \mod f(X) $$

ou encore $f(X)$ ne divise pas $u(X)$. ■

**5.2. THÉORÈME.** On suppose s pair. Soit $f(X) = X^n - aX^{n-1} - \dots - a_n$ un polynôme irréductible de $F_q[X]$. Pour que $f(X^p + X)$ soit irréductible sur $F_q$, il faut et il suffit que

$$ \sum_{j=1}^{s} (-1)^{j-1} a^{p^{s-j}} \neq 0. $$

(a) On a

$$ X^{q^n} = \left( \sum_{k=0}^{n s - 1} (-1)^{n s - k + 1} (X^p + X)^{p^k} \right) + (-1)^n X. $$

Posons

$$ u(X) = \sum_{k=0}^{n s - 1} (-1)^{n s - k + 1} X^{p^k}, $$

$$ b = \sum_{j=1}^{s} (-1)^{j-1} a^{p^s-j} \quad \text{et} \quad T(X) = \sum_{k=0}^{n-1} X^{p^k s}. $$

On a

$$ u(X) = \sum_{j=1}^{s} (-1)^{j-1} T(X)^{p^{s-j}}. $$

On a donc, modulo $f(X^p + X)$,

$$ X^{p^{ns}} \equiv b + X; $$

d'où, pour $k \ge 0$

$$ X^{p^{kn s}} \equiv k b + X. $$

D'autre part, le théorème de Wilson montre que

$$ \prod_{k=0}^{p-1} (Y - X^{p^{kn s}}) \equiv Y^p - X^p - (Y - X)b^{p-1} \mod f(X^p + X). $$

(b) D'après 1.1, pour que le polynôme $f(X^p + X)$ soit irréductible, il faut et il suffit que les coefficients dans $F_q[X]$ de

$$ \prod_{k=0}^{p-1} (Y - X^{q^{kn}}) - Y^p - Y - (-1)^p X^{1+\dots+q^{n(p-1)}} $$

soient congrus à 0 mod $f(X^p+X)$. D'après (a), cette condition s'écrit $b^{p-1}+1=0$, ce qui équivaut à $b \neq 0$, puisque $b^p+b=0$.

**5.3.** Les résultats obtenus dans les paragraphes 3, 4 et 5 sont liés à l'observation suivante: le problème essentiel est d'exprimer le reste dans la division euclidienne de $X^{p^{kn s}}$ par $f(g(X))$. Ceci est théoriquement possible [1], mais les formules obtenues sont compliquées. Cependant, si $X^{p^{en}} = u(g(X)) + v(X)$ (où $u, v \in F_q[X]$, $u \neq 0$, $v=0$ ou $\deg(v) < \deg(u)$) et si $u(X) \equiv 0 \mod f(X)$, on a alors $X^{p^{kn s}} = v^k(X)^{(2)}$ (modulo $f(g(X))$) pour tout $k > 0$; on obtient alors des expressions plus ou moins maniables pour ledit reste, selon que les coefficients dans $F_q[X]$ de $\prod_{k=0}^{m-1} (Y - v^k(X))$ s'expriment plus ou moins facilement modulo $f(g(X))$.

$$ (2) \quad v^k(X) \text{ signifie } v(v \dots v(X)). $$

Bibliographie

[1] S. Agou, Formules explicites intervenant dans la division euclidienne des polynômes à coefficients dans un anneau unitaire et applications diverses, Public. Départ. Math. (Lyon), 8. 1 (1971), p. 107-121.

[2] A. A. Albert, *Fundamental Concepts of Higher Algebra*, London 1956.

[3] L. E. Dickson, *Linear Groups with an Exposition of the Galois Field Theory*, New-York 1958.

[4] A. F. Long, *Classification of irreducible factorable polynomials over a finite field*, Acta Arith. 12 (1967), p. 301-313.

[5] — *Factorisation of irreducible polynomials over a finite field with the substitution X^p - X for X*, Duke Math. Journ. 40 (1) (1973), p. 63-76.

[6] O. Öre, *Contributions to the theory of finite fields*, Trans. Amer. Math. Soc. 36 (1934), p. 243-274.

DÉPARTEMENT DE MATHÉMATIQUES
UNIVERSITE DE LYON 1

Reçu le 7. 6. 1974
et dans la forme modifiée le 21. 2. 1975