Congruence linéaire

En arithmétique modulaire, une congruence linéaire à une seule inconnue x est une équation diophantienne de la forme Ax ≡ B mod M, où les données sont trois entiers A, B et M.

L'équation a des solutions entières x si et seulement si le pgcd de A et M divise B, et ces solutions forment alors une classe de congruence modulo M/pgcd(A, M).

On sait aussi résoudre un système quelconque (A₁x ≡ B₁ mod M₁, … , A_kx ≡ B_k mod M_k) de telles équations, même lorsque le théorème des restes chinois ne s'applique pas directement.

Cas d'une seule congruence

Soient

• A ≠ 0, B et M trois entiers,
• d le pgcd de A et M,
• a et m les entiers premiers entre eux A/d et M/d,
• b le rationnel B/d.

La congruence linéaire

Ax ≡ B mod M

a des solutions si et seulement si b est entier. Elle équivaut alors à

x ≡ c × b mod m,

où c est un inverse de a modulo m.

Lorsque l'ensemble des solutions est non vide, il forme donc une classe mod m, soit d classes mod M.

Tous ces résultats se déduisent de l'étude de l'équation diophantienne Ax + My = B.

Exemples.

• L'équation 24x ≡ 8 mod 45 n'a pas de solution car pgcd(24, 45) = 3 ne divise pas 8.
• L'équation 24x ≡ 18 mod 45 équivaut (en simplifiant par 3) à 8x ≡ 6 mod 15.
  Comme 15 est petit, on trouve immédiatement que l'inverse mod 15 du coefficient 8 est 2, « par balayage » pour k de 0 à 14, en s'arrêtant dès que 8k ≡ 1 mod 15 (pour un module plus grand, on utiliserait l'algorithme d'Euclide étendu). L'équation 8x ≡ 6 mod 15 est donc équivalente (en multipliant par 2) à x ≡ 12 mod 15.
  Une façon plus directe de résoudre 8x ≡ 6 mod 15 est de procéder de même « par balayage » pour k de –7 à 7, en s'arrêtant dès que 8k ≡ 6 mod 15 : on retrouve ainsi que 8x ≡ 6 mod 15 équivaut à 8x ≡ 8×(–3) mod 15, c'est-à-dire x ≡ –3 mod 15.
  Modulo 45, il y a donc trois solutions : –3, –3 + 15 et –3 – 15.

Pour résoudre un système de congruences A_ix ≡ B_i mod M_i, on peut ainsi se ramener au cas où tous les A_i valent 1, cas étudié ci-dessous.

Cas de deux congruences

Soient m, n, r et s quatre entiers. Le système

x ≡ r mod m et x ≡ s mod n

a des solutions si et seulement si s – r est un multiple de pgcd(m, n), et les solutions forment alors une classe modulo ppcm(m, n).

(Ce système se réécrit x = r + jm = s + kn donc sa résolution équivaut à celle de l'équation diophantienne linéaire jm – kn = s – r.)

Plus généralement, pour tout entier a ≠ 0, le système x ≡ r mod m et ax ≡ s mod n a des solutions si et seulement si s – ar est un multiple de pgcd(am, n), et les solutions forment alors une classe modulo ppcm(am, n)/a.

Démonstration

• Cas m = 0. Le système x = r et ax ≡ s mod n a une (unique) solution si et seulement si s – ar est un multiple de n.
• Cas m ≠ 0. Posons d = pgcd(am, n). Les solutions éventuelles du système sont les x de la forme r + mj avec j entier tel que a(r + mj) ≡ s mod n, c'est-à-dire amj ≡ s – ar mod n. D'après la section précédente, il existe de tels entiers j si et seulement si s – ar est multiple de d, et ces solutions j forment alors une classe modulo n/d, les x = r + mj correspondants formant donc une classe modulo mn/d = ppcm(am, n)/a.

Exemple.

Considérons le systèmex ≡ 1 mod 12 et 2x ≡ 20 mod 45.On peut prévoir qu'il existe des solutions — en vérifiant que pgcd(2 × 12, 45) = 3 divise 20 – (2 × 1) = 18 — et qu'elles forment une classe modulo ppcm(2 × 12, 45)/2 = 180. On le retrouve en résolvant : les solutions sont les x de la forme 1 + 12j pour j entier tel que 2(1 + 12j) ≡ 20 mod 45, c'est-à-dire 24j ≡ 18 mod 45. D'après l'exemple de la section précédente, les solutions sont j = –3 + 15k donc x = 1 + 12(–3 + 15k), soitx = –35 + 180k (avec k entier).

Système de k congruences

Quelques exemples célèbres

Le problème des œufs

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

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

x ≡ 1 mod 2, 3, 4, 5, 6 et x ≡ 0 mod 7.

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, est aussi attribué à Brahmagupta :

x ≡ 1 mod 2, x ≡ 2 mod 3, x ≡ 3 mod 4, x ≡ 4 mod 5, x ≡ 5 mod 6 et x ≡ 0 mod 7

autrement dit :

x ≡ –1 mod 2, 3, 4, 5, 6 et x ≡ 0 mod 7

et un sous-problème à Bhaskara ou à Brahmagupta :

x ≡ –1 mod 3, 4, 5 et 6.

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.

Le problème des unités de travail

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

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,

x ≡ 1 mod 2, x ≡ 2 mod 3, x ≡ 5 mod 6 et x ≡ 5 mod 12.

Théorème des restes chinois généralisé

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 :

Théorème des restes chinois généralisé — Un système de k congruences

x ≡ r₁ mod m₁ et … et x ≡ r_k mod m_k

a des solutions si et seulement si, pour tous indices i et j, pgcd(m_i, m_j) divise r_i – r_j, et les solutions forment alors une classe modulo ppcm(m₁, … , m_k).

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.

Méthode des substitutions successives

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).

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).

Méthode chinoise

En 1247, le mathématicien chinois Qin Jiushao expose la méthode trouvée par son prédécesseur Yi Xing. 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 à 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é).

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.