Diviseurs premiers : Zsigmondy, premiers divisant un polynôme¶

Domaine : Théorie des nombres · Niveau : avancé · Prérequis : Ordre d'un élément, Polynômes à coefficients entiers

L'idée¶

Beaucoup de problèmes se règlent en trouvant un nombre premier bien choisi qui divise une expression : un premier « nouveau », un premier d'une forme particulière, ou un premier qui ne divise pas certains nombres donnés. Voici les outils pour en fabriquer.

Existence. Tout entier $n > 1$ a un diviseur premier : son plus petit diviseur $> 1$. Si $n$ est composé, il a un diviseur premier $\leq \sqrt{n}$.
L'argument d'Euclide. Pour montrer qu'il y a une infinité de premiers ayant une propriété, on suppose qu'il n'y en a que $p_1, \ldots, p_k$, et l'on construit un nombre dont les facteurs premiers ont la propriété mais ne sont aucun des $p_i$.
Premiers divisant un polynôme. Pour tout polynôme $P$ non constant à coefficients entiers, une infinité de nombres premiers divisent au moins une valeur $P(n)$ (théorème de Schur, exemple résolu).
Diviseurs premiers primitifs. Un premier $q$ est un diviseur primitif de $a^n - b^n$ s'il le divise sans diviser aucun $a^k - b^k$ pour $k < n$. Un tel $q$ vérifie $\operatorname{ord}_q(a b^{-1}) = n$, donc $q \equiv 1 \pmod n$ (voir Ordre d'un élément).

Théorème de Zsigmondy

Soient $a > b \geq 1$ premiers entre eux et $n \geq 2$. Alors $a^n - b^n$ a un diviseur premier primitif, sauf dans deux cas : $(a, b, n) = (2, 1, 6)$, et $n = 2$ avec $a + b$ une puissance de $2$.

En olympiade, on peut citer Zsigmondy, mais il est souvent préférable de redémontrer le cas utile, ou de raisonner directement avec l'ordre. Le théorème de Dirichlet (une infinité de premiers dans toute progression $an + b$ avec $\operatorname{pgcd}(a, b) = 1$) se cite aussi, mais sa preuve dépasse largement le niveau olympique.

Exemple résolu¶

Problème (théorème de Schur)

Soit $P$ un polynôme non constant à coefficients entiers. Montrer qu'il existe une infinité de nombres premiers $p$ tels que $p$ divise $P(n)$ pour au moins un entier $n$.

Étape 1 : écarter le cas facile. Si $P(0) = 0$, alors $n$ divise $P(n)$ pour tout $n$, et tout premier $p$ divise $P(p)$. On suppose donc $c = P(0) \neq 0$.

Étape 2 : supposer le contraire. Supposons que seuls les premiers $p_1, \ldots, p_k$ divisent des valeurs de $P$, et posons $m = p_1 p_2 \cdots p_k$.

Étape 3 : fabriquer une valeur sans ces premiers. Pour un entier $t$, on évalue $P$ en $c\,m\,t$. Tous les termes de $P(cmt)$ sauf le terme constant sont divisibles par $c\,m$, donc

\[P(cmt) = c\,\big(1 + m\,t\,R(t)\big)\]

pour un polynôme $R$ à coefficients entiers. Comme $P$ n'est pas constant, $\lvert 1 + m\,t\,R(t) \rvert > 1$ pour $t$ assez grand.

Étape 4 : conclure. Le nombre $1 + mtR(t)$ a alors un diviseur premier $q$. Mais $1 + mtR(t) \equiv 1 \pmod{p_i}$ pour chaque $i$ : $q$ n'est aucun des $p_i$. Pourtant $q$ divise $P(cmt)$, ce qui contredit l'hypothèse.

C'est l'argument d'Euclide, appliqué à un polynôme : on évalue en un multiple de tous les premiers connus, pour que la valeur soit $\equiv$ (constante) modulo chacun d'eux.

Comment le reconnaître¶

On a besoin d'un nombre premier ayant une propriété, sans pouvoir l'écrire explicitement.
On veut montrer qu'il existe une infinité de premiers d'une certaine forme, ou divisant une suite.
Une équation fait intervenir $a^n - b^n$, $a^n - 1$, ou une puissance de premier : par exemple $a^n - 1 = p^k$ ou « $a^n - 1$ n'a que des petits facteurs premiers ».
Une suite dont les termes semblent avoir des facteurs premiers toujours nouveaux.

Techniques classiques¶

Situation	Technique
Il faut un diviseur premier	Le plus petit diviseur $> 1$ ; il est $\leq \sqrt{n}$ si $n$ est composé
Infinité de premiers d'une forme donnée	Argument d'Euclide avec un nombre bien construit
Premiers divisant les valeurs de $P$	Évaluer en un multiple de tous les premiers connus (exemple résolu)
Un premier $\equiv 1 \pmod n$	Un diviseur premier primitif de $a^n - 1$, ou un diviseur premier de $\Phi_n(a)$ qui ne divise pas $n$
Équation $a^n - b^n = $ puissance de premier, ou facteurs premiers contraints	Zsigmondy élimine presque tous les cas ; traiter les exceptions à part
Premiers $\equiv 3 \pmod 4$	Un nombre $\equiv 3 \pmod 4$ a un facteur premier $\equiv 3 \pmod 4$

Exercices d'échauffement¶

Montrer qu'il existe une infinité de nombres premiers $\equiv 3 \pmod 4$. Indication : $4p_1 \cdots p_k - 1$.
Montrer que si $2^n - 1$ est premier, alors $n$ est premier.
Trouver tous les entiers $n \geq 1$ et $k \geq 0$ tels que $2^n - 1 = 3^k$.
Soit $p$ un nombre premier impair. Montrer que tout diviseur premier $q$ de $2^p - 1$ vérifie $q \equiv 1 \pmod{2p}$.
Montrer qu'il existe une infinité de nombres premiers qui divisent au moins un nombre de la forme $n^2 + n + 1$.

Diviseurs premiers dans la shortlist¶

2022 N4, solution 2 : un diviseur premier primitif $q$ de $p^{p-1} - 1$ vérifie $\operatorname{ord}_q(p) = p - 1$.
2020 N2 : à la manière d'Euclide, $(p_1 \cdots p_k)^2 - p_1 \cdots p_k + 1$ fournit un nouveau premier divisant un nombre de la forme $x^2 - x + 1$.
2020 N4 : des PGCD de nombres de Mersenne fournissent une infinité de premiers ayant la propriété voulue.
2016 N8 : on choisit un premier $p$ dans une progression arithmétique, grâce au théorème de Dirichlet.

Pour approfondir : Objectif Olympiades de Mathématiques, tome 5 (M. Aassila), p. 57 à 60 (nombres premiers, décomposition, infinité des premiers, premiers de la forme $4n - 1$ p. 59), p. 255 à 258 (premiers de la forme $4k + 3$ et $3k + 2$), p. 310 à 312 (théorème de Zsigmondy), p. 326 à 328 (premiers en progression arithmétique, théorème de Dirichlet p. 327), p. 329 à 344 (polynômes cyclotomiques).

Problèmes de la shortlist¶

14 problèmes · difficulté moyenne : ★★★★★ (2,9) · dont 2 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 1 · 2 ★ : 5 · 3 ★ : 4 · 4 ★ : 3 · 5 ★ : 1

Problème	Difficulté	Concepts
2020 N2	★☆☆☆☆	Graphes : degrés, chemins, arbres · Résidus quadratiques
2022 N4 · OIM P5	★★☆☆☆	Équations diophantiennes : factorisation et encadrement · Valuations p-adiques et lemme LTE · Congruences, théorèmes de Fermat et d'Euler
2013 N3	★★☆☆☆	Principe extrémal · Divisibilité, PGCD et algorithme d'Euclide
2011 N1	★★☆☆☆	Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs
2011 N2	★★☆☆☆	Valuations p-adiques et lemme LTE · Principe des tiroirs
2009 N2	★★☆☆☆	Principe des tiroirs
2020 N4	★★★☆☆	Ordre d'un élément et racines primitives · Divisibilité, PGCD et algorithme d'Euclide
2012 N5	★★★☆☆	Polynômes à coefficients entiers · Congruences, théorèmes de Fermat et d'Euler
2010 A5	★★★☆☆	Équations fonctionnelles : substitutions, injectivité, surjectivité
2010 N5 · OIM P3	★★★☆☆	Valuations p-adiques et lemme LTE · Équations fonctionnelles : substitutions, injectivité, surjectivité
2014 N7	★★★★☆	Congruences, théorèmes de Fermat et d'Euler · Suites et récurrences · Valuations p-adiques et lemme LTE
2012 N6	★★★★☆	Ordre d'un élément et racines primitives · Résidus quadratiques · Théorème des restes chinois
2008 N5	★★★★☆	Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs
2016 N8	★★★★★	Principe des tiroirs · Polynômes à coefficients entiers · Congruences, théorèmes de Fermat et d'Euler · Polynômes : racines, relations de Viète, factorisation

Situation	Technique
Il faut un diviseur premier	Le plus petit diviseur \(> 1\) ; il est \(\leq \sqrt{n}\) si \(n\) est composé
Infinité de premiers d'une forme donnée	Argument d'Euclide avec un nombre bien construit
Premiers divisant les valeurs de \(P\)	Évaluer en un multiple de tous les premiers connus (exemple résolu)
Un premier \(\equiv 1 \pmod n\)	Un diviseur premier primitif de \(a^n - 1\), ou un diviseur premier de \(\Phi_n(a)\) qui ne divise pas \(n\)
Équation $a^n - b^n = $ puissance de premier, ou facteurs premiers contraints	Zsigmondy élimine presque tous les cas ; traiter les exceptions à part
Premiers \(\equiv 3 \pmod 4\)	Un nombre \(\equiv 3 \pmod 4\) a un facteur premier \(\equiv 3 \pmod 4\)