Home

MPSI/PCSI

Révisions Maths lycée

Arithmétique Maths expertes

Théorèmes de Bézout et Gauss

Cet exercice consiste à résoudre un système de congruences en utilisant les équations de Dioff-Ancienne. Le système à résoudre est le suivant : x congru à 1 modulo 11, et x congru à 3 modulo 4. Pour montrer que ce système revient à résoudre l'équation 11u + 4v = 2, où u et v sont des entiers relatifs, on écrit les équations de congruence en notation algebrique. On obtient x = 1 + 11u et x = 3 + 4v. En simplifiant, on obtient l'équation 11u - 4v = 2, ce qui est l'équation diophantienne recherchée. On vérifie si cette équation a des solutions en utilisant le PGCD de 11 et 4, qui est égal à 1. Comme 1 divise 2, l'équation a des solutions. On trouve une solution particulière en observant que 11 et 4 ont des multiples qui se comportent bien ensemble, comme 12. On obtient les coefficients de Bézout en prenant -1 pour u et -3 pour v. En multipliant ces coefficients par 2, on obtient une solution particulière de l'équation, soit u = -2 et v = -6. On généralise ensuite les solutions en ajoutant un coefficient k à la solution particulière. Finalement, on simplifie en remplaçant les coefficients négatifs par des coefficients positifs, et on obtient que u = 2 + 4k et v = 5 + 11k sont les solutions de l'équation diophantienne. Pour trouver les solutions du système initial, on remplace u et v dans les équations de congruence. On obtient x = 23 + 44k, ce qui signifie que les solutions du système sont congrues à 23 modulo 44.

Salut ! Dans cet exercice, on veut résoudre ce système-là, qui est un système de congruence. On va passer par les équations de Dioff-Ancienne pour résoudre ce système. On nous dit de montrer que ce système revient à résoudre l'équation 11u plus 4v est égal à 2, où u et v sont des entiers relatifs. Ce système, c'est x congruent à 1 modulo 11, et x congruent à 3 modulo 4. On sait que si x est solution de ce système, il existe u et v, tel que x c'est 1 plus 11u, ça veut dire ça, et congruer à 1 modulo 11, ça veut dire qu'il existe u dans z tel que x est égal à 1 plus 11u, et pareil, congruer à 3 modulo 4, ça veut dire qu'il existe v tel que x est égal à 3 plus 4v. Voilà, c'est ça que ça veut dire. Donc, finalement, on a une égalité de deux nombres, alors il y a du u, il y a du v, on met l'égalité et on voit ce que ça donne comme simplification, parce que c'est ça qu'on veut, on veut une égalité avec du u et du v. Donc, finalement, 1 plus 11u est égal à 3 plus 4v, on met u et v du même côté, on met le 1 à droite, ce qui nous fait 11u moins 4v est égal à 2, ce qui est exactement ce qu'on nous demandait d'avoir comme équation diophantienne. Ensuite, on résout de l'équation E, donc c'est ce qu'on va faire. C'est une équation diophantienne, donc il faut vérifier pour savoir s'il y a des solutions. Est-ce que le PGCD des deux coefficients devant nos inconnus divise le nombre qui est à droite, la constante qui est à droite ? Donc là, PGCD de 11 et 4, ça fait 1, et 1, du coup, ça marche tout le temps parce que 1 divise bien 2 ici. Donc, l'équation admet des solutions. Alors, là, soit on trouve directement une solution particulière, soit on trouve les coefficients de Bézout, les coefficients de Bézout, soit ils sautent aux yeux, soit on fait l'algorithme de Clid et ensuite, on remonte l'algorithme de Clid pour trouver les coefficients de Bézout. Ici, éventuellement, on ne trouve pas de solution particulière, mais les coefficients de Bézout vont sauter aux yeux parce que là, on voit qu'on a 11 et on a 4. Donc, on sait que dans les multiples de 4, il y a 12, 12 qui va très bien se comporter parce qu'on est à 1 de 11. Donc, en prenant les bons coefficients, on va très facilement retrouver les coefficients de Bézout. Donc, en prenant moins 1 pour U et moins 3 pour V, on a les coefficients de Bézout, du coup, pour 11 et 4. Donc, ce qui nous fait, voilà, ça fait 11, pardon, moins 11 plus 12, ça nous fait 1. On multiplie tout ça par 2 parce que nous, ce qui nous intéresse, c'est 2. Donc, ça fait 11 fois moins 2, moins 4 fois moins 6, du coup, ça fait 2. Maintenant qu'on a une solution particulière, donc là, on a moins 2, moins 6, c'est une solution particulière de E. On va généraliser les solutions en faisant tout simplement, donc là, on a l'ensemble des solutions. Donc, on a pour U, c'est la solution particulière, moins ce coefficient-là fois 4, fois K, pardon. Donc, ça fait U moins moins 4 fois K. Donc, ça fait U plus 4K. Et pareil pour, non, pas pareil pour V, c'est la solution particulière, mais cette fois-ci, plus le coefficient devant U, fois K. D'accord ? À chaque fois, il y en a un des deux qui est en signe contraire du signe qu'on peut trouver ici. Et donc, alors, après simplification, parce que là, on peut laisser comme ça, moins 2, moins 6, on peut laisser comme ça, mais on aime bien avoir des nombres un peu plus petits, généralement, ou au moins positifs. Là, si j'ajoute un K, parce que c'est vrai pour n'importe quel cas, mais en particulier, si j'ajoute un K, je retrouve que U est égal à 2, et V est égal à 5. C'est un peu plus joli d'écrire ça, donc on prend 2 et 5 comme premiers coefficients. Et donc, on trouve l'ensemble des solutions comme étant U qui vaut 2 plus 4K, et V qui vaut 5 plus 11K, pour K qui décrit Z. Donc voilà, et ensuite, en déduire les solutions de S. Donc S, c'était le système qu'on nous donnait au début. Donc là, solution du système, ça veut dire qu'on cherche une solution modulo 44. Si on se rappelle du chapitre sur les congruences, quand on a un système de congruence, la solution qu'on va donner, elle est modulo, le produit des deux, parce qu'ils sont premiers entre eux, donc modulo 44. Donc ça veut dire qu'on aimerait bien avoir un X qui est égal à, vu qu'on ne travaille pas avec des congruences, on ne va pas avoir du modulo 44, mais on aimerait bien avoir un X qui est égal à quelque chose plus 44 fois K. D'accord ? Donc c'est l'équivalent du modulo 44. Donc on a U et V qui nous intéressaient, on va voir un peu comment ça se passe. On sait que X, on avait dit que c'était 1 plus 11U. Bon, ben U, on remplace par ce qu'on a trouvé, 2 plus 4K. Ça fait 1 plus 22 plus 44K. Ça, c'est très bien, parce que le 44K, il apparaît là. Et donc, on a que X est égal à 23 plus 44K. Alors, on l'aurait aussi retrouvé, le 44K, avec, si on avait pris V au lieu de prendre U, parce que là, on voit qu'on a 4 fois V. V, il y a 11K, donc ça nous aurait fait 44K aussi. Ça aurait fait la même chose, sauf qu'il fallait en choisir un. Bon, j'ai pris U parce que c'était le premier. Et donc finalement, on trouve que, donc voilà, on a dit 23 plus 44K, mais du coup, ça veut dire, si on revient aux congruences, système de départ, X est congrué à 23 modulo 44. Et donc, voilà pour l'ensemble des solutions. Et voilà pour cet exercice.

Système congruences et Bezout

RELATED

Recommended videos

test

Nombres premiers entre eux

Équation diophantienne