All subjects
- All subjects
Congurences simultanées
Dans cet exercice, nous devons résoudre des équations linéaires congruentes modulo m.
Dans la première partie, on nous demande de prouver qu'une équation de la forme nx congrue à a modulo m a une unique solution modulo m lorsque n et m sont premiers entre eux.
On utilise le théorème de Bézout qui nous dit que si m et n sont premiers entre eux, alors il existe une combinaison linéaire d'entiers u et v telle que mu plus nv est égal à 1.
On multiplie l'équation nx congrue à a modulo m par v de chaque côté pour se débarrasser de nv et obtenir x congrue à av modulo m.
Dans la deuxième partie, on considère deux équations modulo n et m respectivement, avec m et n premiers entre eux. On veut montrer qu'il existe une unique solution modulo nm.
On utilise à nouveau le théorème de Bézout pour trouver une combinaison linéaire d'entiers u et v telle que um plus nv est égal à 1.
En multipliant la deuxième équation par nv, on obtient une expression pour k, qui est égal à v fois b moins a modulo m. On remplace k dans la première équation pour obtenir une expression pour x.
La solution est donc de la forme x congrue à av modulo mn.
Ensuite, dans la troisième partie, on résout un problème pratique où deux signaux s'allument à des intervalles de temps différents.
On modélise ce problème par trois congruences modulo 15, 28 et 2 respectivement. On utilise le théorème de Bézout pour trouver une unique solution, qui est x congrue à 92 plus 420L modulo 420, où L est un entier arbitraire.
Finalement, dans la dernière partie, on résout un problème où on doit répartir un butin entre plusieurs personnes.
On modélise ce problème par trois congruences modulo 17, 11 et 6 respectivement. On utilise le théorème de Bézout pour trouver une solution particulière, qui est x congrue à 37 modulo 187.
En résolvant cette équation modulo 6, on trouve que l'ensemble des solutions est x congrue à 785 plus 1122L modulo 1122, où L est un entier arbitraire.
