Une congruence ne dit pas que deux entiers sont égaux, mais qu'ils ont le même reste dans une division. Cette relation transforme des puissances immenses en calculs sur un petit nombre de classes.
La rigueur porte sur le module, le sens des implications et les divisions autorisées. Simplifier une congruence comme une équation réelle peut faire perdre ou ajouter des solutions.
Division euclidienne et divisibilité
Division euclidienne
Pour et , il existe un unique couple tel que et .
On dit que n divise a lorsqu'il existe un entier q tel que a = nq. Cette définition doit être utilisée avec les entiers négatifs comme avec les positifs.
Définir une congruence
Congruence et arithmétique modulaire
On écrit lorsque n divise . Cela équivaut à dire que a et b ont le même reste modulo n.
Le module n doit être un entier strictement positif. Réduire un entier modulo n consiste à le remplacer par un représentant congru, souvent son reste entre 0 et n - 1.
Calculer modulo n
Compatibilité avec les opérations
Les congruences se conservent par addition, soustraction, multiplication et puissance entière positive.
On peut réduire les facteurs avant de les multiplier, ce qui limite les tailles. En revanche, la division n'est pas automatique. Pour simplifier par un facteur, il faut contrôler son inverse modulo n ou adapter le module.
Étudier les puissances et les cycles
Les restes des puissances finissent souvent par se répéter. On calcule quelques termes, on identifie une période, puis on réduit l'exposant modulo cette période. La périodicité doit être justifiée par une relation multiplicative, pas seulement devinée sur un tableau court.
Exemple de dernier chiffre
Modulo 10, les puissances de 7 ont pour restes successifs 7, 9, 3 et 1. Multiplier encore par 7 fait recommencer le cycle, dont la période vaut 4. Comme , on obtient . Le dernier chiffre est donc 9. La justification du cycle vient du retour au reste 1, qui rend la suite des produits identique à partir de l'étape suivante.
Démontrer un critère de divisibilité
Les critères décimaux viennent des restes des puissances de 10. Modulo 9, toutes sont congrues à 1 : un entier est congru à la somme de ses chiffres. Modulo 11, (10equiv-1), donc les signes alternent.
Cette démarche explique le critère au lieu de le réciter. Elle s'adapte à une base ou à un module différent dès que l'on sait réduire les puissances de la base.
Croiser deux congruences
Pour résoudre un petit système de congruences, on peut écrire les représentants de la première sous la forme (x=a+nk), puis substituer dans la seconde. Lorsque les modules sont premiers entre eux, une classe unique apparaît modulo leur produit.
Ainsi (xequiv2pmod3) et (xequiv3pmod5) conduisent à (2+3kequiv3pmod5), puis (kequiv2pmod5). On obtient (xequiv8pmod{15}), résultat vérifié dans les deux congruences initiales.
Résoudre une congruence linéaire
Condition de résolution
La congruence admet une solution si et seulement si divise b. Si a et n sont premiers entre eux, a possède un inverse modulo n.
Quand l'inverse existe, on multiplie les deux membres par cet inverse. Sinon, on commence par le PGCD et l'on décrit toutes les classes solutions modulo n.
Applications et contrôles
Erreur fréquente : de , on ne peut pas toujours conclure .
Contrôle utile : substituer un représentant de chaque classe trouvée dans la congruence initiale.
Le PGCD, Bézout et Gauss expliquent les inverses et les simplifications. Le petit théorème de Fermat accélère les puissances.
Le calcul modulaire attendu est fixé par le programme officiel de mathématiques expertes en Terminale.