En arithmétique modulaire, une congruence linéaire à une seule inconnuePour les aspects historiques et techniques concernant le cas de plusieurs inconnues, voir par exemple , vol. 2, et . 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 (Ax ≡ B mod M, … , Ax ≡ B mod M) de telles équations, même lorsque le théorème des restes chinois ne s'applique pas directement.
Cas d'une seule congruence
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 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 Modulo 45, il y a donc trois solutions : –3, –3 + 15 et –3 – 15.
Pour résoudre un système de congruences Ax ≡ B mod M, on peut ainsi se ramener au cas où tous les A valent 1., cas étudié ci-dessous.
Cas de deux congruences
(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.
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 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èmeOn 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 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 donc x = 1 + 12(–3 + 15k), soit
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 puis Brahmagupta vers 628. (dans son Brahmasphutasiddhanta), réapparaît au début du sous la plume du mathématicien égyptien Alhazen, qui donne deux méthodes. Fibonacci l'inclut en 1202 dans son Liber abaci, , ..
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 :
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 :
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 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 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 – r est divisible par pgcd(m, m) et par pgcd(m, m) donc par leur ppcm qui (par distributivité du pgcd par rapport au ppcm) est égal à pgcd(m, 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 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)..
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 Ax ≡ B mod M en la mettant sous forme résolue 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
Exemple. Considérons le système 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 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 (avec k entier). On reporte dans la troisième : é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 :
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, premiers entre eux deux à deux, de même ppcm que m, … , m, et tels que chaque n soit un diviseur du m correspondant. Cela revient à placer chaque facteur primaire p de ppcm(m, … , m) dans n pour l'indice i (ou l'un des indices) tel(s) que m est divisible par p. Alors, toute solution du système et … et x ≡ r mod m est solution du système x ≡ r mod n et … et x ≡ r mod n (puisque n divise m) 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 et minimal), la solution est x = 17, ce qui donne un total de accomplis.
Notes et références
Catégorie:Arithmétique modulaire