M&A Présentation

Section 13.1 Présentation

Problème 13.1.1.

Une bande de dix-sept pirates possède un trésor constitué de pièces d'or d'égale valeur. Ils projettent de les partager également entre eux, et de donner le reste au cuisinier qui recevrait alors trois pièces. Mais les pirates se querellent, et six d'entre eux sont tués. Désormais, le partage des pirates laisserait quatre pièces au cuisinier. Oui mais voilà, ils font naufrage et seuls le trésor, six pirates et le cuisinier sont sauvés. Le partage donnerait alors cinq pièces d'or à ce dernier. Finalement, le cuisinier décide d'empoisonner le reste des pirates et de garder le trésor pour lui. Sur combien de pièces d'or au minimum peut-il espérer mettre la main?

Si on note \(x\) le nombre de pièces d'or de ce trésor, l'énigme précédente se traduit mathématiquement de la façon suivante.

Problème 13.1.2.

Trouvez le plus petit entier positif \(x\) tel que

le reste de la division euclidienne de \(x\) par \(17\) vaut \(3\text{,}\)
le reste de la division euclidienne de \(x\) par \(11\) vaut \(4\text{,}\)
le reste de la division euclidienne de \(x\) par \(6\) vaut \(5\text{.}\)

Pour résoudre ce problème de façon moderne, il faut un minimum de connaissances en arithmétique modulaire. Commençons par introduire le concept de congruence.

Définition 13.1.3. Congruence dans \(\mathbb{Z}\).

Soit \(a, b\in\mathbb{Z}\) et \(m\in\mathbb{N}^*\text{.}\)

Alors les assertions suivantes sont équivalentes :

\(a\) et \(b\) donnent le même reste quand on les divise par \(m\text{;}\)
\(a-b\) est un multiple de \(m\text{;}\)
\(m\vert (a-b)\text{;}\)
\(\exists k\in\mathbb{Z},\; a=b+mk\text{.}\)

Dans ce cas, on dit que \(a\) et \(b\) sont congrus modulo \(m\) et on note

\begin{equation*} a\equiv b\;\mathrm{mod}\;m. \end{equation*}

Exemple 13.1.4.

Les divisions euclidiennes de \(38\) et \(-107\) par \(5\) donnent respectivement

\begin{equation*} 38=5\cdot 7+3\quad\text{et}\quad -107=5\cdot(-22)+3. \end{equation*}

On a donc \(38\equiv -107\;\mathrm{mod}\;5\text{.}\)
On a \(8\equiv 2\;\mathrm{mod}\;3\) car \((8-2)=6=2\cdot 3\) est un multiple de \(3\text{.}\)
Comme \(12\vert (84-36)=48=12\cdot 4\text{,}\) on a \(84\equiv 36\;\mathrm{mod}\;12\text{.}\)
Puisque \(55=-17+9\cdot 8\text{,}\) on a \(55\equiv -17\;\mathrm{mod}\;8\) ainsi que \(55\equiv -17\;\mathrm{mod}\;9\text{.}\)

On peut maintenant reformuler les problèmes 13.1.1 et 13.1.2 comme suit.

Problème 13.1.5.

Trouvez le plus petit entier positif \(x\) tel que

\begin{equation*} \left\{ \begin{array}{cccl} x&\equiv&3&\text{mod}\; 17,\\ x&\equiv&4&\text{mod}\; 11,\\ x&\equiv&5&\text{mod}\; 6. \end{array} \right. \end{equation*}

Remarque 13.1.6.

Les solutions de l'équation

\begin{equation*} x\equiv 3\;\mathrm{mod}\;17 \end{equation*}

sont les entiers de la progression arithmétique \(\left\{3+17k\,|\,k\in\mathbb{Z}\right\}\text{,}\) soit

\begin{equation*} \ldots,\;-48,\;-31,\;-14,\;3,\;20,\;37,\;54,\;71,\;\ldots \end{equation*}
Les solutions de l'équation

\begin{equation*} x\equiv 4\;\mathrm{mod}\;11 \end{equation*}

sont les entiers de la progression arithmétique \(\left\{4+11k\,|\,k\in\mathbb{Z}\right\}\text{,}\) soit

\begin{equation*} \ldots,\;-29,\;-18,\;-7,\;4,\;15,\;26,\;37,\;48,\;\ldots \end{equation*}
Les solutions de l'équation

\begin{equation*} x\equiv 5\;\mathrm{mod}\;6 \end{equation*}

sont les entiers de la progression arithmétique \(\left\{5+6k\,|\,k\in\mathbb{Z}\right\}\text{,}\) soit

\begin{equation*} \ldots,\;-13,\;-7,\;-1,\;5,\;11,\;17,\;23,\;29,\;\ldots \end{equation*}

Le problème étudié consiste donc à trouver le plus petit entier positif qui appartienne à chacune de ces trois progressions arithmétiques.

Il est loin d'être évident qu'un tel nombre existe! Nous avons besoin d'aller plus loin dans notre compréhension de l'arithmétique modulaire pour le trouver de manière efficace.

Théorème 13.1.7.

Soit \(m\in\mathbb{N}^*\) et \(a, b, c, d\in\mathbb{Z}\text{.}\)

Alors on a les propriétés suivantes.

Réflexivité :

\begin{equation*} a\equiv a\;\mathrm{mod}\;m. \end{equation*}
Symétrie :

\begin{equation*} a\equiv b\;\mathrm{mod}\;m\quad\Leftrightarrow\quad b\equiv a\;\mathrm{mod}\;m. \end{equation*}
Transitivité :

\begin{equation*} a\equiv b\;\mathrm{mod}\;m\quad\text{et}\quad b\equiv c\;\mathrm{mod}\;m\quad\Rightarrow\quad a\equiv c\;\mathrm{mod}\;m. \end{equation*}
Addition / Soustraction :

\begin{equation*} a\equiv b\;\mathrm{mod}\;m\quad\text{et}\quad c\equiv d\;\mathrm{mod}\;m\quad\Rightarrow\quad a\pm c\equiv b\pm d\;\mathrm{mod}\;m. \end{equation*}
Multiplication :

\begin{equation*} a\equiv b\;\mathrm{mod}\;m\quad\text{et}\quad c\equiv d\;\mathrm{mod}\;m\quad\Rightarrow\quad a\cdot c\equiv b\cdot d\;\mathrm{mod}\;m. \end{equation*}
Exponentiation :

\begin{equation*} a\equiv b\;\mathrm{mod}\;m\quad\Rightarrow\quad a^k\equiv b^k\;\mathrm{mod}\;m \end{equation*}

pour tout entier positif \(k\text{.}\)

Démonstration.

C'est un bon exercice de démontrer ces propriétés et c'est l'objet de l'exercice 13.3.10.

Exemple 13.1.8.

Mettons en application les six propriétés ci-dessus.

On a

\begin{equation*} 154\equiv 154\;\mathrm{mod}\;28. \end{equation*}
On a

\begin{equation*} 417\equiv 17\;\mathrm{mod}\;10 \end{equation*}

car \(417-17=400\) est divisible par \(10\text{.}\)

Donc

\begin{equation*} 17\equiv 417\;\mathrm{mod}\;10. \end{equation*}
On a

\begin{equation*} 3\equiv -1\;\mathrm{mod}\;4 \end{equation*}

car \(4\vert (3-(-1))=4\) et

\begin{equation*} -1\equiv 7\;\mathrm{mod}\;4 \end{equation*}

car \(4\vert (-1-7)=-8\text{.}\)

Donc

\begin{equation*} 3\equiv 7\;\mathrm{mod}\;4. \end{equation*}
On a

\begin{equation*} -12\equiv 8\;\mathrm{mod}\;5 \end{equation*}

car \(5\vert (-12-8)=-20\) et

\begin{equation*} 33\equiv 23\;\mathrm{mod}\;5 \end{equation*}

car \(5\vert (33-23)=10\text{.}\)

Donc

\begin{equation*} -12+33\equiv 8+23\;\mathrm{mod}\;5, \end{equation*}

c'est-à-dire

\begin{equation*} 21\equiv 31\;\mathrm{mod}\;5. \end{equation*}
On a

\begin{equation*} -12\equiv 8\;\mathrm{mod}\;5 \end{equation*}

car \(5\vert (-12-8)=-20\) et

\begin{equation*} 33\equiv 23\;\mathrm{mod}\;5 \end{equation*}

car \(5\vert (33-23)=10\text{.}\)

Donc

\begin{equation*} (-12)\cdot 33\equiv 8\cdot 23\;\mathrm{mod}\;5, \end{equation*}

c'est-à-dire

\begin{equation*} -396\equiv 184\;\mathrm{mod}\;5. \end{equation*}
On a

\begin{equation*} 417\equiv 7\;\mathrm{mod}\;10 \end{equation*}

car \(10\vert(417-17)=400\text{.}\)

Donc

\begin{equation*} 417^2\equiv 7^2\;\mathrm{mod}\;10, \end{equation*}

\begin{equation*} 417^3\equiv 7^3\;\mathrm{mod}\;10, \end{equation*}

etc.

Remarque 13.1.9.

Comme pour les matrices, il y a une multiplication mais (pas vraiment) de division.

Avec les matrices, on définit néammoins le concept d'inverse à l'aide du théorème qui suit.

Diviser revient alors à multiplier par la matrice inverse, quand elle existe, de même que diviser un nombre réel par \(5\) revient à le multiplier par \(0{,}2\text{.}\)

Théorème 13.1.10. Inverse d'une matrice.

Soit \(A\in M_n(\mathbb{R})\) une matrice carrée \(n\times n\) à coefficients réels. Alors les propriétés suivantes sont équivalentes :

\(\displaystyle \exists B\in M_n(\mathbb{R}),\;AB=I_n;\)
\(\displaystyle \exists B\in M_n(\mathbb{R}),\;BA=I_n;\)
\(\det(A)\neq 0\text{.}\)

Dans ce cas, une telle matrice \(B\) est unique et on l'appelle l'inverse de \(A\text{.}\)

Démonstration.

Voir votre cours d'algèbre linéaire favori.

Avec les congruences, on va utiliser le résultat suivant.

Théorème 13.1.11. Inverse d'un entier modulo un entier positif.

Soit \(a\in\mathbb{Z}\) et \(m\in\mathbb{N}^*\text{.}\) Alors les assertions suivantes sont équivalentes :

\(\exists u\in\mathbb{Z},\;au\equiv 1\;\mathrm{mod}\;m\text{;}\)
\(\exists(u;v)\in\mathbb{Z}^2,\;au+mv=1\text{;}\)
\(\text{PGCD}(a;m)=1\text{.}\)

Dans ce cas, on dit que \(a\) est inversible modulo \(m\) et on appelle \(u\) un inverse de \(a\) modulo \(m\text{.}\)

De plus, quand on dispose d'un inverse particulier \(u_0\text{,}\) il en existe une infinité qu'on peut paramétrer comme suit :

\begin{equation*} u\text{ est un inverse de }a \text{ modulo }m \quad\Leftrightarrow\quad u=u_0+km\quad\text{où}\;k\in\mathbb{Z}. \end{equation*}

Démonstration.

Commençons par établir l'équivalence des trois propriétés indiquées en montrant que

\begin{equation*} 1\;\Rightarrow\;2\;\Rightarrow\;3\;\Rightarrow\;1. \end{equation*}

1 \(\Rightarrow\) 2 :

Soit \(u\in\mathbb{Z}\) tel que \(au\equiv 1\;\mathrm{mod}\;m\text{.}\) Par la définition 13.1.3 de la congruence, il existe \(k\in\mathbb{Z}\) tel que

\begin{equation*} au=1+km\quad\Rightarrow\quad au+(-k)m=1. \end{equation*}

La propriété 2 est donc vérifiée, avec \(v=-k\text{.}\)
2 \(\Rightarrow\) 3 :

Soit \((u;v)\in\mathbb{Z}^2\) tel que \(au+mv=1\text{.}\) Par le théorème de Bézout 12.1.9, on en déduit que \(\text{PGCD}(a;m)=1\text{.}\)
3 \(\Rightarrow\) 1 :

Supposons que \(\text{PGCD}(a;m)=1\text{.}\) Par le théorème de Bachet-Bézout 12.1.1, on en déduit qu'il existe \((u;v)\in\mathbb{Z}^2\) tel que

\begin{equation*} au+mv=1\quad\Rightarrow\quad au=1+(-v)m \end{equation*}

donc \(au\equiv 1\;\mathrm{mod}\;m\) par la définition 13.1.3 de la congruence.

Supposons maintenant que ces propriétés sont vérifiées et fixons \(u_0\in\mathbb{Z}\) un inverse de \(a\) modulo \(m\text{,}\) de sorte que

\begin{equation*} au_0\equiv 1\;\mathrm{mod}\;m. \end{equation*}

Il ne nous reste plus qu'à établir l'équivalence suivante, pour tout \(u\in\mathbb{Z}\) :

\begin{equation*} au\equiv 1\;\mathrm{mod}\;m\quad\Leftrightarrow\quad u\equiv u_0\;\mathrm{mod}\;m. \end{equation*}

D'une part, on a

\begin{equation*} \begin{array}{ccc} au\equiv 1\;\mathrm{mod}\;m&\Rightarrow&u_0\cdot (au)\equiv u_0\cdot 1\;\mathrm{mod}\;m\\ &\Rightarrow&(u_0a)\cdot u\equiv u_0\;\mathrm{mod}\;m\\ &\Rightarrow&1\cdot u\equiv u_0\;\mathrm{mod}\;m\\ &\Rightarrow&u\equiv u_0\;\mathrm{mod}\;m. \end{array} \end{equation*}

Et réciproquement, on a

\begin{equation*} \begin{array}{ccc} u\equiv u_0\;\mathrm{mod}\;m&\Rightarrow&au\equiv au_0\;\mathrm{mod}\;m\\ &\Rightarrow&au\equiv 1\;\mathrm{mod}\;m. \end{array} \end{equation*}

Exemple 13.1.12.

L'entier \(453\) est-il inversible modulo \(222\text{?}\)

Non, car l'algorithme d'Euclide montre que \(\text{PGCD}(453;222)=3\neq 1\text{.}\)

Remarque 13.1.13.

Supposons que \(a\) soit inversible modulo \(m\text{.}\)

Pour trouver un inverse particulier, il suffit d'appliquer l'algorithme d'Euclide étendu.

En effet, comme \(\text{PGCD}(a;m)=1\text{,}\) ce dernier fournit un couple de coefficients \((u;v)\in\mathbb{Z}^2\) tels que

\begin{equation*} au+mv=1 \end{equation*}

d'où

\begin{equation*} au=1+(-v)m \end{equation*}

et donc

\begin{equation*} au\equiv 1\;\mathrm{mod}\;m \end{equation*}

de sorte que le coefficient \(u\) est un inverse de \(a\) modulo \(m\text{.}\)

Exemple 13.1.14.

L'entier \(453\) est-il inversible modulo \(221\text{?}\)

En appliquant l'algorithme d'Euclide étendu, on obtient

\begin{equation*} \text{PGCD}(453;221)=1\quad\text{et}\quad 1=453\cdot(-20)+221\cdot 41. \end{equation*}

Donc \(453\) est inversible modulo \(221\) et \(-20\) est un inverse car

\begin{equation*} 453\cdot (-20)=1+221\cdot(-41)\equiv 1\;\mathrm{mod}\;221. \end{equation*}

L'ensemble des inverses \(u\) de \(453\) modulo \(221\) est caractérisé par

\begin{equation*} u\equiv -20\;\mathrm{mod}\;221. \end{equation*}

Il s'agit donc de la progression arithmétique

\begin{equation*} \ldots,\;\underbrace{-20-221\cdot 2}_{-662},\;\underbrace{-20-221}_{-241},\;-20,\;\underbrace{-20+221}_{201},\;\underbrace{-20+221\cdot 2}_{422},\;\underbrace{-20+221\cdot 3}_{643},\;\ldots \end{equation*}

Nous sommes maintenant en mesure d'énoncer le théorème qui va nous permettre de résoudre le problème 13.1.5.

Théorème 13.1.15. Restes chinois.

Soit \(a_1,\ldots,a_n\in\mathbb{Z}\) et \(m_1,\ldots,m_n\in\mathbb{N}^*\) tels que

\begin{equation*} \text{PGCD}(m_i;m_j)=1\quad\text{pour tous } 1\leq i\neq j\leq n. \end{equation*}

Alors le système de congruences

\begin{equation*} \left\{ \begin{array}{cccc} x&\equiv&a_1&\mathrm{mod}\;m_1,\\ x&\equiv&a_2&\mathrm{mod}\;m_2,\\ \vdots&&\vdots&\vdots\\ x&\equiv&a_n&\mathrm{mod}\;m_n, \end{array}\right. \end{equation*}

admet une infinité de solutions en progression arithmétique, caractérisées par

\begin{equation*} x\equiv x_0\;\mathrm{mod}\;M\quad\Leftrightarrow\quad \exists k\in\mathbb{Z}, x=x_0+Mk. \end{equation*}

où

\begin{equation*} M=m_1\cdot m_2\cdots m_n \end{equation*}

et où la solution particulière \(x_0\) peut s'obtenir par la combinaison linéaire

\begin{equation*} x_0=a_1M_1u_1+a_2M_2u_2+\cdots+a_nM_nu_n \end{equation*}

en prenant pour tout \(i\) un inverse \(u_i\) de \(M_i=M/m_i\) modulo \(m_i\text{,}\) c'est-à-dire

\begin{equation*} M_i=\frac{M}{m_i}=\prod_{j\neq i}m_j\quad\text{et}\quad M_iu_i\equiv 1\;\mathrm{mod}\;m_i. \end{equation*}

Démonstration.

Pour trouver une preuve, on peut voir ça comme un résultat d'interpolation.

Exemple 13.1.16.

Résolvons le problème 13.1.5 à l'aide du théorème 13.1.15.

On a

\begin{equation*} a_1=3,\;a_2=4\text{ et }a_3=5. \end{equation*}
On note que

\begin{equation*} m_1=17,\;m_2=11\text{ et }m_3=6 \end{equation*}

sont premiers entre eux deux à deux, donc on peut appliquer le théorème 13.1.15.
Puis on calcule

\begin{equation*} M=m_1\cdot m_2\cdot m_3=17\cdot 11\cdot 6=1122, \end{equation*}

et

\begin{align*} M_1&=m_2m_3=11\cdot 6=66,\\ M_2&=m_1m_3=17\cdot 6=102,\\ M_3&=m_1m_2=17\cdot 11=187. \end{align*}
Grâce à l'algorithme d'Euclide étendu, on trouve que
- \(1=66\cdot 8+17\cdot (-31)\) donc
  
  \begin{equation*} \underbrace{66}_{M_1}\cdot\underbrace{8}_{u_1}\equiv 1\;\mathrm{mod}\;\underbrace{17}_{m_1}; \end{equation*}
- \(1=102\cdot 4+11\cdot (-37)\) donc
  
  \begin{equation*} \underbrace{102}_{M_2}\cdot\underbrace{4}_{u_2}\equiv 1\;\mathrm{mod}\;\underbrace{11}_{m_2}; \end{equation*}
- \(1=187\cdot 1+6\cdot (-31)\) donc
  
  \begin{equation*} \underbrace{187}_{M_3}\cdot\underbrace{1}_{u_3}\equiv 1\;\mathrm{mod}\;\underbrace{6}_{m_3}. \end{equation*}
On calcule maintenant la solution particulière

\begin{equation*} \begin{array}{ccccccc} x_0&=&a_1M_1u_1&+&a_2M_2u_2&+&a_3M_3u_3\\ &=&3\cdot 66\cdot 8&+&4\cdot 102\cdot 4&+&5\cdot 187\cdot 1\\ &=&4151.\\ \end{array} \end{equation*}
L'ensemble des solutions est alors caractérisé par l'équation

\begin{equation*} x\equiv x_0\;\mathrm{mod}\;M \end{equation*}

c'est-à-dire

\begin{equation*} x\equiv 4151\;\mathrm{mod}\;1122. \end{equation*}

Il s'agit donc de la progression arithmétique

\begin{equation*} \left\{4151+1122k\;|\;k\in\mathbb{Z}\right\}. \end{equation*}
Il ne reste plus qu'à trouver la plus petite solution positive en soustrayant le bon nombre de multiples de \(1122\) à \(4151\text{,}\) ce qui revient à effectuer la division euclidienne de \(4151\) par \(1122\) :

\begin{equation*} 4151=1122\cdot 3+785. \end{equation*}

Nous avons finalement résolu le problème 13.1.1: s'il empoisonne les six pirates qui restent, le cuisinier peut espérer s'emparer de \(785\) pièces d'or au minimum.

Nous allons maintenant présenter de manière plus synthétique les calculs qui permettent d'appliquer le théorème des restes chinois.

Exemple 13.1.17.

Les calculs nécessaires pour résoudre le système

\begin{equation*} \left\{ \begin{array}{cccl} x&\equiv&3&\text{mod}\; 17,\\ x&\equiv&4&\text{mod}\; 11,\\ x&\equiv&5&\text{mod}\; 6 \end{array} \right. \end{equation*}

sont les suivants :

\begin{equation*} \begin{array}{|c|c|c|c|c|c|} \hline a_i&m_i&M_i&\text{Euclide étendu}&u_i&a_iM_iu_i\\ \hline 3&17&66&1=66\cdot 8+17\cdot(-31)&8&1584\\ \hline 4&11&102&1=102\cdot 4+11\cdot(-37)&4&1632\\ \hline 5&6&187&1=187\cdot 1+6\cdot(-31)&1&935\\ \hline M=&1122&&&x_0=&4151\\ \hline \end{array} \end{equation*}

Et les solutions sont caractérisées par

\begin{equation*} x\equiv 4151\;\mathrm{mod}\;1122. \end{equation*}

Théorème des restes chinois : Résoudre un système de congruences à l'aide de l'algorithme d'Euclide étendu.

Objectif : Résoudre un système de congruences du type

\begin{equation*} \left\{ \begin{array}{cccc} x&\equiv&a_1&\mathrm{mod}\;m_1,\\ x&\equiv&a_2&\mathrm{mod}\;m_2,\\ \vdots&&\vdots&\vdots\\ x&\equiv&a_n&\mathrm{mod}\;m_n. \end{array}\right. \end{equation*}
Hypothèse : Il faut que les entiers \(m_i\) soient premiers entre eux deux à deux.
Principe : Remplir le tableau suivant

\begin{equation*} \begin{array}{|c|c|c|c|c|c|} \hline a_1&m_1&M_1=M/m_1&1=M_1u_1+m_1v_1&u_1&a_1M_1u_1\\ \hline a_2&m_2&M_2=M/m_2&1=M_2u_2+m_2v_2&u_2&a_2M_2u_2\\ \hline \vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ \hline a_n&m_n&M_n=M/m_n&1=M_nu_n+m_nv_n&u_n&a_nM_nu_n\\ \hline M=&\prod m_i&&&x_0=&\sum a_iM_iu_i\\ \hline \end{array} \end{equation*}

Les solutions constituent alors la progression arithmétique caractérisée par

\begin{equation*} x\equiv x_0\;\mathrm{mod}\;M\quad\Leftrightarrow\quad \exists k\in\mathbb{Z}, x=x_0+Mk. \end{equation*}
Voir aussi : Notes de cours de Jérôme.
Pour aller plus loin : Les entiers, ces fonctions qui s'ignorent ou comment tisser des liens entre le théorème des restes chinois et l'interpolation de Lagrange - un excellent article de Jimmy Dillies, dans la revue de vulgarisation mathématique québécoise Accromath.