Résolution d'équations modulaires simples ax = b mod n

Terminale générale Spé · Option Mathématiques Expertes

À retenir

• ax b n ax - ny = b (équation diophantienne). • Une solution existe d = PGCD(a, n) b. • Si PGCD(a, n) = 1, il existe une solution unique modulo n obtenue en multipliant par l'inverse de a modulo n. • Pour n petit, on peut simplement tester les valeurs de x \0, 1, , n - 1\ dans un tableau de valeurs.

Le cours

1. Équation modulaire du premier degré On cherche les entiers x tels que ax b n, avec a, b Z et n N^* donnés. Comme tout entier est congru à l'un des restes 0, 1, , n - 1, il suffit de trouver les solutions parmi ces restes : l'ensemble des solutions est une réunion de classes x x_0 n. 2. Cas où a et n sont premiers entre eux Il existe alors un inverse u de a modulo n : au 1 n. En multipliant les deux membres par u, on obtient une solution unique modulo n : ax b n x ub n Exemple : 2 5 = 10 1 9, donc 5 est l'inverse de 2 modulo 9, et 2x 7 9 x 35 8 9. 3. Méthode générale 1. Pour un petit modulo, dresser le tableau des valeurs de ax pour x \0, 1, , n - 1\. 2. Sinon, chercher l'inverse u en testant a 1, a 2, … jusqu'à obtenir 1 modulo n, puis multiplier par u. 3. Toujours vérifier en remplaçant x par la solution trouvée. 4. Si a et n ont un diviseur commun d > 1 Il y a soit aucune solution (si d ne divise pas b), soit plusieurs classes modulo n. Exemple : 4x 6 10 a pour solutions x 4 et x 9 10 (car 16 36 6), c'est-à-dire x 4 5. Ce critère sera justifié dans le chapitre sur le PGCD et le théorème de Bézout.

Dans ce chapitre