Congruence linéaire

Le problème suivant, traité par les mathématiciens indiens Bhāskara I[5] au VII^e siècle puis Brahmagupta vers 628[6] (dans son Brahmasphutasiddhanta), réapparaît au début du XI^e siècle sous la plume du mathématicien égyptien Alhazen[5], qui donne deux méthodes[7]. Fibonacci l'inclut en 1202 dans son Liber abaci[5]^,[7].

Au marché, un cheval écrase le panier d'œufs d'une fermière. Le cavalier propose de rembourser les dégâts et demande combien d'œufs contenait le panier. La femme se souvient seulement qu'il en restait toujours un quand elle les sortait deux par deux, et de même par groupes de trois, quatre, cinq ou six, mais qu'il n'en restait aucun quand elle les sortait sept par sept. Combien avait-elle d'œufs au minimum ?

Il s'agit donc de trouver le plus petit entier positif x tel que

Ce système est en fait équivalent à : x – 1 divisible par ppcm(2, 3, 4, 5, 6) = 60 et x ≡ 0 mod 7, soit x ≡ 301 mod 420.

Un « problème des œufs » analogue, également repris par Fibonacci[7], est aussi attribué à Brahmagupta[8] :

autrement dit :

et un sous-problème à Bhaskara[7] ou à Brahmagupta[9] :

Le sous-problème équivaut à x ≡ –1 mod 60, et le problème entier à : x ≡ –1 mod 60 et x ≡ 0 mod 7, soit x ≡ 119 mod 420.

En 717, le moine bouddhiste Yi Xing résout le problème suivant[7] :

Quatre équipes, composées respectivement de 2, 3, 6 et 12 travailleurs, ont chacune le même nombre x de jours-hommes de travail à accomplir. Chaque équipe travaille (un certain nombre non nul de jours). Combien d'unités de travail ont été accomplies en tout (au minimum), sachant qu'il reste aux équipes, respectivement, 1, 2, 5 et 5 unités non faites ? Yi Xing donne une méthode pour résoudre le système correspondant,

Yi Xing avait découvert un principe qui généralise à la fois le cas de deux congruences et le théorème des restes chinois :

Ces conditions de compatibilité sont nécessaires d'après le cas de deux congruences. On montre qu'elles sont suffisantes, soit par récurrence sur k en utilisant ce cas particulier, soit en se ramenant à la situation où les m_i sont premiers entre eux deux à deux puis en appliquant le théorème des restes chinois.

Ces deux preuves sont constructives et se traduisent par les deux algorithmes suivants.

Pour résoudre un système de k congruences vérifiant les conditions de compatibilité de l'énoncé, on utilise d'abord la méthode pour deux congruences. On remplace ainsi les deux premières équations x ≡ r₁ mod m₁ et x ≡ r₂ mod m₂ par une seule, de la forme x ≡ r mod m avec m = ppcm(m₁, m₂), c'est-à-dire qu'on calcule un entier r congru à r₁ mod m₁ et à r₂ mod m₂.

Le nouveau système n'a plus que k – 1 équations, et vérifie encore les hypothèses car pour tout j > 2, r_j – r est divisible par pgcd(m_j, m₁) et par pgcd(m_j, m₂) donc par leur ppcm qui (par distributivité du pgcd par rapport au ppcm) est égal à pgcd(m_j, m). On peut donc répéter l'opération, et remplacer de même les deux premières congruences du nouveau système (les équations x ≡ r mod m et x ≡ r₃ mod m₃) par une seule, et ainsi de suite.

On s'arrête lorsqu'il ne reste plus qu'une équation. Elle donne l'ensemble des solutions, sous la forme x ≡ R mod M avec (par associativité du ppcm) M = ppcm(m₁, … , m_k)[10].

En pratique, il n'est pas nécessaire d'avoir vérifié au préalable les k(k – 1)/2 conditions de compatibilité : si elles ne sont pas toutes satisfaites, on le constatera par arrêt prématuré, dans l'alternance de résolutions et de substitutions, sur la résolution d'une équation sans solution. On peut même se dispenser de traiter d'abord indépendamment chacune des équations initiales A_ix ≡ B_i mod M_i en la mettant sous forme résolue x ≡ r_i mod m_i : on met seulement la première sous cette forme, on substitue dans la deuxième que l'on résout, on en déduit une forme résolue pour le système formé des deux premières équations, on substitue dans la suivante, etc.

Exemple.

Considérons le systèmex ≡ 1 mod 12, 2x ≡ 20 mod 45 et 3x ≡ 35 mod 50.

On peut le ramener d'abord au système équivalent x ≡ 1 mod 12, x ≡ 10 mod 45 et x ≡ –5 mod 50, ce qui permet d'affirmer qu'il existe des solutions (car 10 – 1 est divisible par 3, –5 – 1 par 2 et –5 – 10 par 5) et qu'elles forment une classe modulo ppcm(12, 45, 50) = 900, puis résoudre ce système équivalent par substitutions successives.

Plus directement : d'après l'exemple du § « Cas de deux congruences », les solutions du sous-système constitué des deux premières équations sont les x de la forme –35 + 180k (avec k entier). On reporte dans la troisième : 3(–35 + 180k) ≡ 35 mod 50 équivaut à 40k ≡ 40 mod 50, soit 4k ≡ 4 mod 5, c'est-à-dire k ≡ 1 mod 5. Les solutions du système des trois congruences sont donc :x = –35 + 180(1 + 5l) = 145 + 900l (avec l entier).

En 1247, le mathématicien chinois Qin Jiushao expose la méthode[5] trouvée par son prédécesseur Yi Xing[7]^,[8]. Elle consiste à choisir des entiers n₁, … , n_k, premiers entre eux deux à deux, de même ppcm que m₁, … , m_k, et tels que chaque n_i soit un diviseur du m_i correspondant. Cela revient[11] à placer chaque facteur primaire p^v de ppcm(m₁, … , m_k) dans n_i pour l'indice i (ou l'un des indices) tel(s) que m_i est divisible par p^v. Alors, toute solution du système x ≡ r₁ mod m₁ et … et x ≡ r_k mod m_k est solution du système x ≡ r₁ mod n₁ et … et x ≡ r_k mod n_k (puisque n_i divise m_i) et réciproquement, toute solution du second (fournie par le théorème chinois) est solution du premier (grâce aux conditions de compatibilité de l'énoncé)[11].

Solution du problème des unités de travail.

Pour m₁ = 2, m₂ = 3, m₃ = 6 et m₄ = 12, les valeurs r₁ = 1, r₂ = 2, r₃ = 5 et r₄ = 5 sont compatibles car r₂ – r₁ est divisible par 1, r₃ – r₁ et r₄ – r₁ par 2, r₃ – r₂ et r₄ – r₂ par 3 et r₄ – r₃ par 6. On peut choisir simplement n₁ = n₂ = n₃ = 1 et n₄ = 12. Le système est donc équivalent à sa dernière équation : x ≡ 5 mod 12. Compte tenu de la contrainte supplémentaire (x strictement supérieur aux r_i et minimal), la solution est x = 17, ce qui donne un total de 4 × 17 – (1 + 2 + 5 + 5) = 55 jours-hommes accomplis.