Systèmes de congruences

Cette fois, c'est deux fichiers pour le prix d'un : congruences.c et congruences-g.c traitent respectivement un cas particulier et le cas général des systèmes de congruences linéaires du type ax = b mod n et cx = d mod m.

Pour commencer, congruences.c traite le cas où « tout de passe bien », c'est-à-dire quand on est assuré d'avoir une solution et une seule. Il résout par exemple le système de l'exercice 1 de la deuxième interro. Les techniques mises en jeu sont l'inversion modulo n et la version simple (théorème 4.3 p. 64/65 du cours) du théorème chinois. Vous remarquerez qu'il avoue son impuissance dans certains cas.

Le cas général

Le premier problème potentiel est une équation ax = b où a n'est pas inversible. Celui-ci est traité par lineaire_g(). C'est une mise en oeuvre de la proposition 2.10 p. 48 du cours, dans le cas particulier G = Z/nZ (penser à traduire la notation multiplicative en additif). Voir plus spécifiquement l'exemple 2.10 juste en dessous.

Le deuxième danger est de tomber hors du champ d'application du théorème chinois simple, c'est-à-dire quand m et n ne sont pas premiers entre eux. On utilise alors la version plus précise, implémentée par chinois_g(), que constitue le théorème 4.4 p. 66. Bien comprendre dans cet énoncé que la description de l'image du morphisme permet de savoir si une solution existe, que de plus la démonstration indique comment la trouver par une relation de Bézout, et qu'enfin le calcul du noyau détermine le nombre de solutions et comment elles se déduisent d'une solution particulière.

La résolution du système se fait alors en deux étapes : on commence par résoudre chacune des équations avec lineaire_g(). Si une d'entre elles n'a pas de solution, c'est fini. Sinon, on résout avec par le théorème chinois étendu le nouveau système obtenu avec les nouveaux modules, et les solutions des équations précédentes comme nouveaux membres de droite.

Enfin, signalons qu'on peut parfaitement traiter des systèmes avec plus d'équations. Il suffit pour cela de réduire progressivement le nombre d'équations en résolvant les deux premières, puis en les remplaçant par la nouvelle équation x = a' mod n', dont les coefficients sont donnés par la résolution, qui leur est équivalente.

Remarques

Ces deux programmes utilisent une nouvelle implémentation de l'algorithme d'Euclide étendu, qui, contrairement à la fonction euclide_complet() peu réaliste d'euclide.c, ne renvoie que l'objet réellement intéressant : la relation de Bézout. C'est donc bezout() qui fait le vrai travail, le reste du code n'étant somme tout que le traduction de quelques théorème. Cet algorithme étant central en arithmétique modulaire, il est donc très intéressant de l'optimiser le plus possible, comme on l'a déjà évoqué.

Une remarque plus mathématique pour finir : la définition du type sol_t n'est pas si anodine. Elle traduit la structure possible des images réciproques dans Z d'éléments de Z/nZ par un morphisme d'anneau. C'est soir l'ensemble vide, soit une classe de Z modulo un de ses idéaux. C'est un fait général sur les morphismes de différentes structures, et il importe de bien comprendre à quel point les notions d'image et de noyau sont en fait concrêtes.