Congruence linéaire

En arithmétique modulaire, une congruence linéaire à une seule inconnue[1] 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 (A1x ≡ B1 mod M1, … , Akx ≡ Bk mod Mk) de telles équations, même lorsque le théorème des restes chinois ne s'applique pas directement.

## Cas d'une seule congruence

[modifier | modifier le code]

> 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[2].

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 Aix ≡ Bi mod Mi, on peut ainsi se ramener au cas où tous les Ai valent 1[3], cas étudié ci-dessous.

## Cas de deux congruences

[modifier | modifier le code]

> 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)[4], 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

[modifier | modifier le code]

### Quelques exemples célèbres

[modifier | modifier le code]

#### Le problème des œufs

[modifier | modifier le code]

Le problème suivant, traité par les mathématiciens indiens Bhāskara I[5] au VIIe siècle puis Brahmagupta vers 628[6] (dans son Brahmasphutasiddhanta), réapparaît au début du XIe 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

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

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[7] ou à Brahmagupta[9] :

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

[modifier | modifier le code]

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,

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é

[modifier | modifier le code]

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é[8] -- Un système de k congruences

x ≡ r1 mod m1 et … et x ≡ rk mod mk

a des solutions si et seulement si, pour tous indices i et j, pgcd(mi, mj) divise ri – rj, et les solutions forment alors une classe modulo ppcm(m1, … , mk).

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 mi 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

[modifier | modifier le code]

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 ≡ r1 mod m1 et x ≡ r2 mod m2 par une seule, de la forme x ≡ r mod m avec m = ppcm(m1, m2), c'est-à-dire qu'on calcule un entier r congru à r1 mod m1 et à r2 mod m2.

Le nouveau système n'a plus que k – 1 équations, et vérifie encore les hypothèses car pour tout j > 2, rj – r est divisible par pgcd(mj, m1) et par pgcd(mj, m2) donc par leur ppcm qui (par distributivité du pgcd par rapport au ppcm) est égal à pgcd(mj, 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 ≡ r3 mod m3) 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(m1, … , mk)[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 Aix ≡ Bi mod Mi en la mettant sous forme résolue x ≡ ri mod mi : 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

[modifier | modifier le code]

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 n1, … , nk, premiers entre eux deux à deux, de même ppcm que m1, … , mk, et tels que chaque ni soit un diviseur du mi correspondant. Cela revient[11] à placer chaque facteur primaire pv de ppcm(m1, … , mk) dans ni pour l'indice i (ou l'un des indices) tel(s) que mi est divisible par pv. Alors, toute solution du système x ≡ r1 mod m1 et … et x ≡ rk mod mk est solution du système x ≡ r1 mod n1 et … et x ≡ rk mod nk (puisque ni divise mi) 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 m1 = 2, m2 = 3, m3 = 6 et m4 = 12, les valeurs r1 = 1, r2 = 2, r3 = 5 et r4 = 5 sont compatibles car r2 – r1 est divisible par 1, r3 – r1 et r4 – r1 par 2, r3 – r2 et r4 – r2 par 3 et r4 – r3 par 6. On peut choisir simplement n1 = n2 = n3 = 1 et n4 = 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 ri et minimal), la solution est x = 17, ce qui donne un total de 4 × 17 – (1 + 2 + 5 + 5) = 55 jours-hommes accomplis.

## Notes et références

[modifier | modifier le code]

1. ↑ Pour les aspects historiques et techniques concernant le cas de plusieurs inconnues, voir par exemple (en) Leonard Eugene Dickson, History of the Theory of Numbers (en) [détail des éditions], vol. 2, p. 88-93 et (en) Alton T. Butson et Bonnie M. Stewart, « Systems of linear congruences », Canad. J. Math., vol. 7, 1955, p. 358-368 (lire en ligne).
2. ↑ (en) William J. LeVeque, Topics in Number Theory, Courier Dover Publications, 2002 (lire en ligne), p. 32 et 21.
3. ↑ LeVeque 2002, p. 34.
4. ↑ (en) Thomas Koshy, Elementary Number Theory with Applications, Academic Press, 2007, 2e éd. (lire en ligne), p. 303.
5. ↑ a b c et d (en) James Joseph Tattersall, Elementary Number Theory in Nine Chapters, CUP, 1999 (lire en ligne), p. 175.
6. ↑ Koshy 2007, p. 307.
7. ↑ a b c d e et f Dickson, p. 58-62, aperçu sur Google Livres.
8. ↑ a b et c (en) Richard A. Mollin, An Introduction to Cryptography, CRC Press, 2000 (lire en ligne), p. 68-70.
9. ↑ (en) Emil Grosswald, Topics from the Theory of Numbers, Springer Science+Business Media, 2010, 2e éd. (lire en ligne), p. 49.
10. ↑ (en) Jiří Heřman, Radan Kučera et Jaromír Šimša, Equations and Inequalities : Elementary Problems and Theorems in Algebra and Number Theory, Springer Science+Business Media, 2000 (lire en ligne), p. 206-208.
11. ↑ a et b (en) Gareth A. Jones et Josephine M. Jones, Elementary Number Theory, Springer Science+Business Media, 2004 (1re éd. 1998) (lire en ligne), p. 60-61.

* Arithmétique et théorie des nombres

*[VIIe]: 7ᵉ siècle
*[XIe]: 11ᵉ siècle
*[etc.]: et cetera
*[(en)]: Langue : anglais
*[p.]: pages
*[vol.]: volume
*[2e]: deuxième
*[éd.]: édition
*[1re]: première