Home

MPSI/PCSI

Maths

Algèbre

PGCD et algorithme d’Euclide

Dans cet exercice, on cherche à trouver les solutions de l'équation AX congruent à B modulo N, avec des conditions sur A, B et N. On veut démontrer que cette équation a une solution si et seulement si le PGCD de A et N divise B.

Dans la première partie, on montre que si X est une solution de l'équation, alors le PGCD divise B. On utilise le fait que si AX est congruent à B modulo N, cela signifie que le PGCD de A et N divise B.

Dans la deuxième partie, on montre que si le PGCD divise B, alors l'équation a une solution. On utilise le théorème de Bézout pour montrer qu'il existe un nombre UV tel que AU + NV est égal à D. En multipliant cette équation par B, on obtient BAU + BNV = BD. En factorisant B par le PGCD, on obtient l'équation B'AU + B'NV = B. On en déduit que B'U est une solution de l'équation.

Dans la deuxième question, on suppose que le PGCD divise B et on pose N égale à DN'. On veut montrer que l'ensemble des solutions de l'équation est donné par X0 + QN', où Q est un entier. On utilise le fait que si X est une solution, alors A(X-X0) est congruent à 0 modulo N. En factorisant A par le PGCD, on obtient l'équation A'(X-X0) = KN'. Comme A' et N' sont premiers entre eux, on en déduit que N' divise X-X0. On peut alors montrer que tous les nombres de la forme X0 + QN' sont des solutions de l'équation.

Dans la troisième question, on cherche à montrer que deux solutions de l'équation sont congrues entre elles modulo N si et seulement si le PGCD divise la différence de leurs coefficients multiplicateurs. On en déduit que les solutions de l'équation sont de la forme X0 + QN', où Q est un entier et X0 est une solution particulière. On conclut que l'équation admet exactement ces solutions.

Salut, bienvenue dans cet exercice. Alors, dans cet exercice, on cherche à trouver les solutions de AX et congruent à B modulo N, où on a des conditions sur A, B et N. On nous note que D, c'est le PGCD de A et de N. Ensuite, première question, on nous demande de justifier que cette équation admet une solution, si et seulement si D divise B. D'accord ? Le B qui est ici. Si et seulement si, en gros, le PGCD de A et de N divise B. On va voir, c'est un si et seulement si, donc on va le faire dans un sens puis dans l'autre. On va commencer par le premier sens, ça veut dire qu'on va montrer que si elle admet une solution, si X est solution, en gros, D divise B. Donc, si X est solution de AX congruent à B modulo N, ça veut dire qu'il existe K, tel que AX est égale à B plus KN. On revient un peu, B abat des congruences. Donc, ça veut dire que le PGCD, donc D divise A et D divise N, donc, en particulier, D divise B. D'accord ? Parce qu'on passe KN de l'autre côté, il divise A, il divise N, donc on peut factoriser par le PGCD, donc, naturellement, il divise B. Ce sens était assez rapide à montrer. Maintenant, c'est un peu plus dur, mais ça reste assez facile. On va montrer dans l'autre sens, ça veut dire que si D divise B, on va montrer que, du coup, l'équation admet une solution. Donc, si D divise B, il existe UV tel que AU plus NV est égal à D. C'est le théorème de Bézout qui nous dit ça. Donc, en particulier, en multipliant par B, on a que BAU plus BNV est égal à BD. Alors, à quoi ça sert de faire ça ? En fait, on va pouvoir ensuite faire apparaître modulo N, notre fameux nombre qui sera conjugué à B. Donc, on sait que D divise B, donc, en particulier, on peut écrire B comme DB'. On remplace ça. On a, du coup, DB'AU, DB'NV et B'xD², d'accord ? Parce que ça fait DB'xD, c'est B'xD². Maintenant, on peut simplifier partout par D. Donc, on simplifie par D, il reste B, d'accord ? Il reste B'D, donc c'est juste B. Ici, on l'enlève, ici, on l'enlève, et on a B'AU plus B'NV est égal à B. Alors, maintenant, qu'est-ce qu'on fait, ça ? En fait, on voit que B'U, c'est solution de AX conjugué à B modulo N. Parce qu'en fait, si on prend le modulo N ici, celui-là, il s'en va, et donc B'AU est conjugué à B modulo N. Et donc, voilà, on a trouvé, à tâtonnement, une solution, comme ça, de AX conjugué à B modulo N, dans le cas où D divise B. Ensuite, question 2, on nous dit, dans cette question, on suppose que D divise B, pour qu'il y ait des solutions, sinon, ce n'est pas drôle. X0, on nous dit que c'est une solution, et on pose N égale D N'. Ensuite, démontrer que l'ensemble des solutions de l'équation, c'est X0 plus Q N', où Q appartient à Z. Donc là, en gros, on divise N par le PGCD de N et de A, ici. Et les solutions, l'ensemble des solutions, c'est une solution particulière plus Q fois N'. Alors, on va voir d'où ça sort, un peu, cette histoire. Donc, on sait que X0 est une solution. Ce qu'on dit, c'est que si X est une solution, alors on a que A fois X moins X0 est conjugué à 0 modulo N. Parce qu'on aurait AX conjugué à B, et AX0 conjugué à B. Donc, quand on fait la différence entre les deux, on a AX moins AX0 conjugué à B moins B, 0. On factorise par A. C'est un peu rapide, mais il ne faut pas non plus être déstabilisé. Donc, ça veut dire que A fois X moins X0 est égal à K fois N. OK ? Conjugué à 0, K fois N, on retrouve ici. Et on note A qui est égal à DA', pour pouvoir, à un moment, simplifier par D. Et ça nous fait, du coup, que DA' fois X moins X0 est égal à K fois DN'. Là, on simplifie par D, c'était le but. Donc, on se retrouve avec A' fois X moins X0 est égal à K fois N'. Alors, qu'est-ce qu'on voulait à la base, si on se rappelle un peu ? On voulait dire que l'ensemble des solutions, on aimerait bien avoir que X est égal à X0 plus Q fois N'. On a N' qui apparaît, on a du X0, etc. Bon, il faut voir un peu ce qui se passe. Étant donné qu'A' et N' sont premiers entre eux, parce qu'on a divisé A et N par leur PGCD, donc A' et N' sont premiers entre eux, on a que N' divise X moins X0. Parce que N' divise ça, il est premier avec A', donc le théorème de Gauss nous assure que N' divise X moins X0. Donc, ça veut dire qu'il existe un Q tel que X est égal à X0 plus Q fois N'. Donc là, on a montré que si X est solution, alors il s'écrit comme ça, que je ne cache pas, mais il reste à montrer qu'au moins tous ceux-là sont solutions. D'accord ? Parce que X est solution, il s'écrit comme ça, mais peut-être que ces trucs-là ne sont pas solutions. Il faut montrer maintenant que tous les nombres qui s'écrivent comme ça sont solutions. Donc, réciproquement, si on a X qui est égal à X0 plus Q fois N', où Q c'est un entier, on va voir est-ce que AX est bien congru à B modulo N. Donc, AX est congru à A fois X0 plus A fois Q N' modulo N. A, on l'écrit encore comme A'D, et du coup, voilà. AX0, on sait que X0 est solution, donc AX0 est congru à B modulo N. Une fois qu'on a remplacé A par A'D, on reconnaît qu'il y a D et N' qui vont se regrouper ensemble pour faire N, donc ce truc-là sera congru à 0 modulo N, et on a bien que AX est congru à B modulo N. Donc, X est bien solution de AX congru à B modulo N, dans le cas où il s'écrit comme ça. Donc, voilà pour la question A. Maintenant, question B. Alors, comment on va faire ça ? Donc là, ce qu'on peut regarder, c'est, on va essayer de voir si on a deux solutions qui sont congrues entre elles modulo N. On va voir ce qui se passe, parce que là, on veut qu'il y ait uniquement des congruences possibles modulo N. Si on voit que deux nombres sont congrus entre eux, on va voir ce qu'ils doivent vérifier. Donc, X1, X2, on prend deux solutions. Il existe alors Q1, Q2, d'après la question précédente, telle que X1, c'est X0 plus Q1, N'. Pareil pour X2. Ensuite, si maintenant, comme on disait, s'ils sont congrus ensemble modulo N, qu'est-ce qui se passe ? Donc, ça veut dire qu'on a ça congru à ça, on simplifie par X0, on passe celui-ci de l'autre côté dans les congruences, ça nous fait Q1 moins Q2 fois N', congru à zéro modulo N. Donc, en gros, N divise ce produit-là, Q1 moins Q2 fois N'. Donc, N, étant donné que c'est N'D, on simplifie par N', ça nous fait D divise Q1 moins Q2. Tout simplement, D divise Q1 moins Q2. Alors, qu'est-ce qu'on en fait de ce résultat ? Ça nous dit qu'en fait, si deux nombres sont congrus entre eux, alors le PGCD divise la différence de Q1 et Q2. En gros, ça veut dire que les entiers X0, X0N', X02N', X0D-1N' sont tous différents modulo N, parce qu'à chaque fois, les différences, ça n'atteint pas D, parce qu'on s'arrête à N-1. Donc, la différence n'atteint pas D. Donc, ils ne seront pas congrus ensemble. Vraiment, c'est ça qu'il faut comprendre, c'est que, là, on a raisonné en équivalence. Donc, pour qu'ils soient congrus ensemble, il faut que D divise la différence des multiples qu'on a utilisés avec N' dans l'écriture de la solution. Mais, si on prend tous ces nombres-là, en fait, ça nous dit qu'ils sont tous différents modulo N, parce que D ne divisera pas la différence, parce que D est plus grand, tout simplement. Et aussi, on a que tous les entiers qui s'écrivent comme X0 plus QN', sont congrus, pardon, modulo N à un de ces entiers-là qui sont ici. Donc, en fait, l'équation admet exactement des solutions, toutes celles-ci, on a D, modulo N. Voilà pour cet exercice.

Equation modulaire

RELATED

Recommended videos

PGCD Fibonacci

algorithme d’Euclide

Equations de Bezou