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 cet article 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$,
- 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 des exemples
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)\\
&=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 :
\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$, si et seulement si, les coefficients du polynôme $P_1-P_2$ sont tous divisibles par $n$ et si $Q$ est un diviseur du polynôme $P_1-P_2.$
Montrer 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, donc tous ses coefficients sont divisibles par $n$, puisque $n\times 0 = 0.$
De même $P-P = Q\times 0$ ce qui prouve que $Q$ est un diviseur de $P-P.$
Par conséquent, $\boxed{P\mathscr{R}P.}$
Montrer 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.$
Les coefficients du polynôme $P_1-P_2$ sont tous divisibles par $n.$
D’une part, comme $P_1-P_2$ est un polynôme à coefficients entiers, il existe un entier naturel $d$ et des entiers $u_0, \dots, u_d$ tels que :
P_1(X)-P_2(X) = \sum_{i=0}^d u_iX^i.L’hypothèse précédente fournit :
\forall i\in\llbracket0, d\rrbracket, n\mid u_i.
Or, pour tout entier $i$ compris entre $0$ et $d$, $-u_i = (-1)\times u_i$ si bien que $u_i\mid -u_i.$ ll s’ensuit que :
\forall i\in\llbracket0, d\rrbracket, n\mid u_i \mid -u_i.
Par transitivité il vient :
\forall i\in\llbracket0, d\rrbracket, n \mid -u_i.
D’autre part :
P_2(X)-P_1(X) = \sum_{i=0}^d (-u_i)X^i.L’entier $n$ divise tous les coefficients du polynôme $P_2-P_1.$
Remarquez maintenant que $P_2-P_1 = (-1)\times (P_1-P_2)$ donc $P_1-P_2\mid P_2-P_1.$ Comme $Q\mid P_1-P_2$ vous déduisez par transitivité que $Q\mid P_2-P_1.$ Ainsi $P_2\mathscr{R} P_1.$
Montrer que la relation $\mathscr{R}$ est transitive
Soient $P_1$, $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.$
D’une part, $Q\mid P_1-P_2$ et $Q\mid P_2-P_3.$ Par somme, vous déduisez $Q\mid (P_1-P_2) + (P_2-P_3)$ soit $Q\mid P_1-P_3.$
D’autre part, $n$ divise tous les coefficients des polynômes $P_1-P_2$ et $P_2-P_3.$
Si $P_1=P_2$ alors $n$ divise tous les coefficients du polynômes $P_1-P_3$ et donc $P_1\mathscr{R}P_3.$
Si $P_2=P_3$ alors $n$ divise encore tous les coefficients du polynômes $P_1-P_3$ et donc $P_1\mathscr{R}P_3.$
Si $P_1\neq P_2$ et si $P_2\neq P_3$ vous notez le maximum des degrés des polynômes $P_1-P_2$ et $P_2-P_3.$ Il existe un entier naturel $d$ et des entiers $u_0,\dots u_d$ ainsi que des entiers $v_0,\dots,v_d$ tels que :
\begin{align*}
P_1(X)-P_2(X) &= \sum_{i=0}^d u_iX^i\\
P_2(X)-P_3(X) &= \sum_{i=0}^d v_iX^i.
\end{align*}
Alors :
\begin{align*}
P_1(X)-P_3(X) &= P_1(X)-P_2(X) + P_2(X)-P_3(X)\\
&=\sum_{i=0}^d u_iX^i + \sum_{i=0}^d v_iX^i\\
&= \sum_{i=0}^d (u_i+ v_i)X^i.
\end{align*}
Or, pour tout entier $i$ compris entre $0$ et $d$, $n\mid u_i$ et $n\mid v_i.$ Par somme, vous déduisez que $n\mid u_i+v_i.$ L’entier $n$ divise tous les coefficients du polynôme $P_1-P_3.$ 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, transitive et symétrique sur $\Z[X]$ 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’équivalences 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$, $P_2$, $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.Vous avez $P_1\mathscr{R}P_2$ autrement dit, $Q\mid P_1-P_2$ et tous les coefficients du polynôme $P_1-P_2$ sont divisibles par $n.$
Vous en déduisez immédiatement que $Q\mid (P_1-P_2)-0$ et que tous les coefficients du polynôme $(P_1-P_2)-0$ sont divisibles par $n.$ Autrement dit $P_1-P_2 \mathscr{R} 0.$
De même, comme $P_3\mathscr{R}P_4$ vous déduisez par symétrie $P_4\mathscr{R}P_3$ puis $P_4-P_3 \mathscr{R} 0.$
Par transitivité, vous déduisez $P_1-P_2\mathscr{R} P_4-P_3.$
Ainsi, $Q$ divise le polynôme $(P_4-P_3)-(P_1-P_2) = (P_2+P_4)-(P_1+P_3).$
L’entier $n$ divise tous les coefficients de $(P_4-P_3)-(P_1-P_2) = (P_2+P_4)-(P_1+P_3).$
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).
D’une part, $Q\mid P_1-P_2.$ Or, $PP_1-PP_2 = P(P_1-P_2)$ si bien que $P_1-P_2 \mid PP_1-PP_2.$ Par transitivité, il vient $Q\mid PP_1-PP_2.$
D’autre part, il existe un entier naturel $d$ et des entiers $u_0,\dots,u_d$ tels que :
P_1(X)-P_2(X) = \sum_{i=0}^d u_i X^i.L’hypothèse $P_1\mathscr{R} P_2$ fournit :
\forall i\in\llbracket 0, d\rrbracket, n\mid u_i.
Il existe un entier naturel $k$ et des entiers $v_0,\dots,v_k$ tels que :
P(X) = \sum_{j=0}^k v_j X^j.Il vient alors :
\begin{align*}
(PP_1-PP_2)(X) &= P(X) (P_1(X)-P_2(X))\\
&= \left(\sum_{j=0}^k v_j X^j\right) \left(\sum_{i=0}^d u_i X^i\right)\\
&= \sum_{j=0}^k\sum_{i=0}^du_iv_j X^{i+j}\\
&= \sum_{\substack{0\leq j \leq k \\ 0\leq i \leq d}}u_iv_j X^{i+j}\\
&=\sum_{\ell = 0}^{k+d} \sum_{\substack{0\leq j \leq k \\ 0\leq i \leq d \\ i+j = \ell}}u_iv_j X^{i+j}\\
&= \sum_{\ell = 0}^{k+d} \left( \sum_{\substack{0\leq j \leq k \\ 0\leq i \leq d \\ i+j = \ell}}u_iv_j\right) X^{\ell}.
\end{align*}Soit $\ell$ un entier compris entre $0$ et $k+d.$
Soient $i$ un entier compris entre $0$ et $d$, puis $j$ un entier compris entre $0$ et $k$ tels que $i+j=\ell.$
Comme $n\mid u_i$ et comme $u_i \mid u_iv_j$ vous déduisez $n\mid u_iv_j.$
Par somme, $n$ divise $\sum_{\substack{0\leq j \leq k \ 0\leq i \leq d \ i+j = \ell}}u_iv_j.$
Il en résulte que tous les coefficients du polynôme $PP_1-PP_2$ sont divisibles par $n.$
Vous déduisez que : $\boxed{PP_1\equiv PP_2 \mod (n,Q).}$
Montrez la compatibilité forte avec le produit
Soient $P_1$, $P_2$, $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 le 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 le 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).}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’équivalences, 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.
