Je crois que l'on sait démontrer que pour tout $n$ il existe des polynômes irréductibles de $\mathbb F_p[X]$ de degré $n$. En revanche, est-qu'on sait donner un tel polynôme explicitement ?
@michal: La construction suivante ne répond pas totalement à la question, mais bon, je n'ai pas réfléchi à la question très longtemps...On se fixe $n\geq 2$ (si $n=1$, il suffit de prendre $X\in\mathbb{F}_p[X]$.)
Soit $n=2^{r_0}p_1^{r_1}\cdots p_r^{r_s},p_i$ impair, et on considère $m=2p_1^{r_1+2}\cdots p_r^{r_s+1}$. Alors, $\Q(\zeta_m)/\Q$ contient une sous-extension cyclique $L/\Q$ de degré $n$.Soit $f$ le polynôme minimal d'un élément primitif de $L/\Q$.
Pour tout $p$ premier engendrant $(\Z/m\Z)^\times$, $p$ est inerte dans cette extension, donc $f$ est un polynôme irréductible de degré $n$ qui reste irréductible modulo $p$.
Donc à $n$ fixé, cela donne une infinité de premiers $p$ pour lesquels tu as un polynôme irréductible de degré $n$ modulo $p$. On doit pouvoir faire beaucoup mieux, mais je n'ai pas trop le temps de m'y atteler maintenant.
En fait, il suffirait de pouvoir répondre à la question suivante; étant donné $n\geq 2$ et $p$ premier, construire une extension cyclique $L/\Q$ de degré $n$ dans laquelle $p$ reste inerte. Le polynôme minimal d'un élément primitif de $L/\Q$ sera alors polynôme irréductible de degré $n$ qui reste irréductible modulo $p$.
En fait, je me demande si c'est aussi facile que ça. D'autant plus que je ne sais pas à quel point tu veux un exemple explicite.
Je pense qu'il y a un moyen simple de s'en sortir dans certains cas en considérant $f=X^n-a\in\mathbb{F}_p[X]$.
Soit $n \in \N^*$, dans la décomposition en facteurs irréductibles de $X^{p^n-1}-1 \in \mathbb F_p[X]$, il y a forcément un facteur de degré $n$ (polynôme minimal d'un élément primitif de $\mathbb F_{p^n}$). Cette décomposition est algorithmique vu qu'on est dans un corps fini (au pire essayer tous les facteurs de degré $\leq n$).
Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
Je reviens avec une question proche. Est-ce qu'il existe pour $n$ quelconque ($\neq 1$)), un polynôme de $\mathbb F_p[X]$ sans racines. Si $n\geqslant p$, je peux considérer $$
P=X^{n-p}\prod_{x\in \mathbb F_p} (X-x)+1
$$ qui répond à la question, mais pour $n<p$, je ne vois pas.
Au fait : si le polynôme n'est pas explicite, ce n'est finalement pas grave. Je voudrais son existence par une méthode moins lourde que l'existence d'un irréductible.
Réponses
http://www.les-mathematiques.net/phorum/read.php?2,126966
Soit $n=2^{r_0}p_1^{r_1}\cdots p_r^{r_s},p_i$ impair, et on considère $m=2p_1^{r_1+2}\cdots p_r^{r_s+1}$. Alors, $\Q(\zeta_m)/\Q$ contient une sous-extension cyclique $L/\Q$ de degré $n$.Soit $f$ le polynôme minimal d'un élément primitif de $L/\Q$.
Pour tout $p$ premier engendrant $(\Z/m\Z)^\times$, $p$ est inerte dans cette extension, donc $f$ est un polynôme irréductible de degré $n$ qui reste irréductible modulo $p$.
Donc à $n$ fixé, cela donne une infinité de premiers $p$ pour lesquels tu as un polynôme irréductible de degré $n$ modulo $p$. On doit pouvoir faire beaucoup mieux, mais je n'ai pas trop le temps de m'y atteler maintenant.
En fait, il suffirait de pouvoir répondre à la question suivante; étant donné $n\geq 2$ et $p$ premier, construire une extension cyclique $L/\Q$ de degré $n$ dans laquelle $p$ reste inerte. Le polynôme minimal d'un élément primitif de $L/\Q$ sera alors polynôme irréductible de degré $n$ qui reste irréductible modulo $p$.
Je suis certain à $99 \%$ que c'est possible.
Je pense qu'il y a un moyen simple de s'en sortir dans certains cas en considérant $f=X^n-a\in\mathbb{F}_p[X]$.
Ici, c'est du huit ans d'âge...
Amicalement.
Je reviens avec une question proche. Est-ce qu'il existe pour $n$ quelconque ($\neq 1$)), un polynôme de $\mathbb F_p[X]$ sans racines. Si $n\geqslant p$, je peux considérer $$
P=X^{n-p}\prod_{x\in \mathbb F_p} (X-x)+1
$$ qui répond à la question, mais pour $n<p$, je ne vois pas.
Merci d'avance, Michal
Reste le cas $n$ impair, $p>2$.
EDIT : Désolé, je n'avais pas vu que la question avait changé.