342. Réduction d’un polynôme, modulo un nombre entier et un autre polynôme

Certains tests de primalité font appel au calcul modulaire. L’objectif est d’éviter d’obtenir des nombres trop importants et des degrés très élevés dans les calculs de polynômes.

Dans ce contenu vous allez aborder :

un calcul modulaire à partir d’exemples pour expliciter les premières démarches,
un calcul explicite du polynôme $(1+X)^{24}$ modulo $24$ et $X^2-1\comma$
une théorie des polynômes à coefficients entiers modulo un entier $n$ non nul et un polynôme $Q$ à coefficients entiers et de degré supérieur ou égal à $1.$

Utilisez le calcul modulaire sur des exemples

Pour deux polynômes $P_1$ et $P_2$ à coefficients entiers, l’écriture $P_1\equiv P_2 \mod (24, X^2-1)$ signifie qu’il existe deux polynômes $A$ et $B$ à coefficients entiers tels que $P_1-P_2 = 24A+(X^2-1)B.$ En pratique, vous pouvez donc retrancher à un coefficient un multiple de $24\comma$ ou remplacer $X^2$ par $1.$ Ces règles de calcul sont justifiées dans la dernière partie.

L’écriture adoptée sera la suivante :

\begin{align*} 25&\equiv 24+1 \mod (24, X^2-1)\\ &\equiv 1 \mod (24, X^2-1). \end{align*}

De même :

\begin{align*} 100X^3+50X^2-44X+29&\equiv (24+24+24+24+4)X^3 +(24+24+2)X^2\\ &\qquad-(24+24-4)X+(24+5) \mod (24, X^2-1)\\ &\equiv 4X^3+2X^2+4X+5 \mod (24, X^2-1)\\ &\equiv 4X(X^2-1+1)+2(X^2-1+1)+4X+5 \mod (24, X^2-1)\\ &\equiv 4X+2+4X+5 \mod (24, X^2-1)\\ &\equiv 8X+7 \mod (24, X^2-1). \end{align*}

Calculez $(X+1)^{24} \mod (24,X^2-1)$

Le calcul va être progressif.

Vous calculez d’abord $(X+1)^2$ comme suit :

\begin{align*} (X+1)^2&\equiv X^2+2X+1 \mod (24, X^2-1) \\ &\equiv (X^2-1)+1+2X+1 \mod (24, X^2-1)\\ &\equiv 2(X+1) \mod (24, X^2-1). \end{align*}

Vous utilisez l’égalité $(X+1)^4 = ((X+1)^2)^2$ ce qui fournit :

\begin{align*} (X+1)^4&\equiv 4(X+1)^2 \mod (24, X^2-1)\\ &\equiv 4\times 2(X+1) \mod (24, X^2-1)\\ &\equiv 8(X+1) \mod (24, X^2-1). \end{align*}

Vous utilisez l’égalité $(X+1)^8 = ((X+1)^4)^2$ ce qui fournit :

\begin{align*} (X+1)^8 &\equiv 64(X+1)^2 \mod (24, X^2-1)\\ &\equiv 64\times 2(X+1) \mod (24, X^2-1)\\ &\equiv128(X+1) \mod (24, X^2-1)\\ &\equiv (24\times 5 + 8)(X+1) \mod (24, X^2-1)\\ &\equiv 8(X+1) \mod (24, X^2-1). \end{align*}

Vous utilisez l’égalité $(X+1)^{16} = ((X+1)^8)^2$ ce qui fournit, par le même calcul :

\begin{align*} (X+1)^{16} &\equiv 64(X+1)^2 \mod (24, X^2-1)\\ &\equiv 8(X+1) \mod (24, X^2-1). \end{align*}

Vous en déduisez que :

\begin{align*} (X+1)^{24} &\equiv (X+1)^{16}(X+1)^{8} \mod (24, X^2-1)\\ &\equiv 8(X+1) \times 8(X+1) \mod (24, X^2-1)\\ &\equiv 64(X+1)^2 \mod (24, X^2-1)\\ &\equiv 8(X+1) \mod (24, X^2-1). \end{align*}

La théorie des polynômes à coefficients entiers modulo $n$ et $Q$

Cette théorie est développée afin de justifier que les calculs menés ci-dessus sont valables.

Soit $n$ un entier naturel non nul et $Q$ un polynôme à coefficients entiers, de degré supérieur ou égal à $1.$

Vous allez munir l’anneau $\Z[X]$ de la relation binaire $\mathscr{R}$ suivante.

Quels que soient les polynômes $P_1$ et $P_2$ à coefficients entiers, vous écrirez $P_1\mathscr{R} P_2\comma$ si et seulement si, il existe deux polynômes $A$ et $B$ à coefficients entiers tels que :

\boxed{P_1-P_2 = nA+QB.}

Note. Deux cas particuliers correspondent aux réductions effectuées dans les exemples. Si $n$ divise tous les coefficients du polynôme $P_1-P_2\comma$ il existe un polynôme $A$ à coefficients entiers tel que $P_1-P_2 = nA\comma$ et en prenant $B=0$ vous avez $P_1\mathscr{R}P_2.$ Si $Q$ divise le polynôme $P_1-P_2\comma$ il existe un polynôme $B$ à coefficients entiers tel que $P_1-P_2 = QB\comma$ et en prenant $A=0$ vous avez encore $P_1\mathscr{R}P_2.$

Montrez que la relation $\mathscr{R}$ est réflexive

Soit $P$ un polynôme à coefficients entiers. Le polynôme $P-P$ est le polynôme nul, qui s’écrit $P-P = n\times 0+Q\times 0.$

Par conséquent, $\boxed{P\mathscr{R}P.}$

Montrez que la relation $\mathscr{R}$ est symétrique

Soient $P_1$ et $P_2$ deux polynômes à coefficients entiers, tels que $P_1\mathscr{R} P_2.$ Il existe deux polynômes $A$ et $B$ à coefficients entiers tels que $P_1-P_2 = nA+QB.$

Alors :

P_2-P_1 = n(-A)+Q(-B).

Comme $-A$ et $-B$ sont des polynômes à coefficients entiers, vous avez $P_2\mathscr{R} P_1.$

Montrez que la relation $\mathscr{R}$ est transitive

Soient $P_1\comma$ $P_2$ et $P_3$ trois polynômes à coefficients entiers, tels que $P_1\mathscr{R} P_2$ et $P_2\mathscr{R}P_3.$ Il existe quatre polynômes $A\comma$ $B\comma$ $A’$ et $B’$ à coefficients entiers tels que :

\begin{align*} P_1-P_2 &= nA+QB\\ P_2-P_3 &= nA'+QB'. \end{align*}

Par somme :

\begin{align*} P_1-P_3 &= (P_1-P_2) + (P_2-P_3)\\ &= n(A+A')+Q(B+B'). \end{align*}

Comme $A+A’$ et $B+B’$ sont des polynômes à coefficients entiers, il en résulte que $P_1\mathscr{R}P_3.$

Passez à l’ensemble quotient $\Z[X] / \mathscr{R}$

La relation $\mathscr{R}$ étant réflexive, symétrique et transitive sur $\Z[X]\comma$ elle est une relation d’équivalence.

Vous notez $\Z[X] / \mathscr{R}$ l’ensemble de toutes les classes d’équivalence obtenues.

Il est rappelé que pour tout polynôme $P$ à coefficients entiers, la classe de $P$ est définie par :

\{A\in\Z[X], A\mathscr{R}P\}.

Notez que, comme $\mathscr{R}$ est réflexive, la classe de $P$ n’est pas vide.

Ainsi, $\Z[X] / \mathscr{R}$ est un ensemble, formé par des classes d’équivalence qui sont toutes non vides.

Pour plus de commodité, quels que soient les polynômes $P_1$ et $P_2$ à coefficients entiers, vous notez $P_1\equiv P_2 \mod (n,Q)$ au lieu de $P_1\mathscr{R} P_2.$

Montrez la compatibilité avec l’addition

Soient $P_1\comma$ $P_2\comma$ $P_3$ et $P_4$ quatre polynômes à coefficients entiers tels que :

\left\{\begin{align*} P_1&\equiv P_2 \mod (n,Q)\\ P_3&\equiv P_4 \mod (n,Q). \end{align*} \right.

Il existe quatre polynômes $A\comma$ $B\comma$ $A’$ et $B’$ à coefficients entiers tels que $P_1-P_2 = nA+QB$ et $P_3-P_4 = nA’+QB’.$ Par somme :

\begin{align*} (P_1+P_3)-(P_2+P_4) &= (P_1-P_2)+(P_3-P_4)\\ &= n(A+A')+Q(B+B'). \end{align*}

Autrement dit, il vient d’être prouvé que $P_1+P_3\mathscr{R} P_2+P_4$ soit :

P_1+P_3 \equiv P_2+P_4 \mod (n,Q).

Montrez la compatibilité faible avec le produit

Pour parvenir à ce résultat, fixez un polynôme $P$ à coefficients entiers.

Soient $P_1$ et $P_2$ deux polynômes à coefficients entiers tels que :

P_1\equiv P_2 \mod (n,Q).

Il existe deux polynômes $A$ et $B$ à coefficients entiers tels que $P_1-P_2 = nA+QB.$ En multipliant par $P\comma$ il vient :

\begin{align*} PP_1-PP_2 &= P(P_1-P_2)\\ &= n(PA)+Q(PB). \end{align*}

Comme $PA$ et $PB$ sont des polynômes à coefficients entiers, vous déduisez que : $\boxed{PP_1\equiv PP_2 \mod (n,Q).}$

Montrez la compatibilité forte avec le produit

Soient $P_1\comma$ $P_2\comma$ $P_3$ et $P_4$ quatre polynômes à coefficients entiers tels que :

\left\{\begin{align*} P_1&\equiv P_2 \mod (n,Q)\\ P_3&\equiv P_4 \mod (n,Q). \end{align*} \right.

D’après la compatibilité faible avec le produit démontrée ci-dessus, en multipliant la première relation par $P_3$ il vient :

P_1P_3 \equiv P_2P_3 \mod (n,Q).

D’après la compatibilité faible avec le produit démontrée ci-dessus, en multipliant la seconde relation par $P_2$ il vient :

P_2P_3 \equiv P_2P_4 \mod (n,Q).

Vous avez ainsi :

\begin{align*} P_1P_3&\mathscr{R}P_2P_3\\ P_2P_3&\mathscr{R}P_2P_4. \end{align*}

Par transitivité, il vient :

P_1P_3\mathscr{R}P_2P_4.

Cela s’écrit :

\boxed{P_1P_3 \equiv P_2P_4 \mod (n,Q).}

Ces compatibilités justifient les calculs des exemples : chaque étape remplace un polynôme par un polynôme qui lui est congru modulo $(24, X^2-1)\comma$ soit en retranchant un multiple de $24$ à un coefficient, soit en ajoutant un multiple de $X^2-1\comma$ et les congruences obtenues peuvent être additionnées, multipliées et élevées à une puissance.

Prolongement

Pour tout polynôme $P$ à coefficients entiers, notez $\varphi(P)$ la classe d’équivalence du polynôme $P.$

Soient $U$ et $V$ deux éléments de $\Z[X] / \mathscr{R}.$ Comme $U$ et $V$ sont des classes d’équivalence, elles ne peuvent pas être vides. Il existe donc $P_U\in\Z[X]$ et $P_V\in\Z[X]$ tels que $U = \varphi(P_U)$ et $V = \varphi(P_V).$

L’addition de $U$ et de $V$ dans $\Z[X] / \mathscr{R}$ est définie par $\varphi(P_U+P_V).$ Cette opération est bien définie : d’après la compatibilité démontrée pour l’addition, l’élément $\varphi(P_U+P_V)$ ne dépend pas du choix des représentants effectué pour $U$ et $V.$

De même, la multiplication de $U$ et de $V$ dans $\Z[X] / \mathscr{R}$ est définie par $\varphi(P_U P_V).$ Cette opération est aussi bien définie : d’après la compatibilité démontrée pour la multiplication, l’élément $\varphi(P_U P_V)$ ne dépend pas non plus du choix des représentants effectué pour $U$ et $V.$

D’après la théorie développée plus haut, justifiez que l’ensemble quotient $\Z[X] / \mathscr{R}$ est un anneau unitaire commutatif muni des deux opérations définies ci-dessus.