Bac+3 à Bac+814 formules

Congruences et arithmétique : formules et méthode

Calculer modulo m, c’est ne garder que le reste de la division par m. L’horloge en est l’exemple familier : 15 h est la même heure que 3 h, modulo 12.

Voici les formules pour résoudre une équation de congruence, trouver un inverse modulaire et utiliser les théorèmes de Fermat et d’Euler.

Les formules

0 formule sur 14 est contrôlée automatiquement : le site les teste sur des valeurs tirées au hasard à chaque mise à jour. Les autres (définitions, conditions, relations entre grandeurs) ne se testent pas ainsi.

Congruences

Définition
a ≡ b (mod m) équivaut à m divise a − b
a et b ont le même reste dans la division par m
Somme et produit
a ≡ b et c ≡ d (mod m) donnent a + c ≡ b + d et a × c ≡ b × d (mod m)
Puissance
a ≡ b (mod m) donne a^k ≡ b^k (mod m)
Inverse modulaire
a u ≡ 1 (mod m) admet une solution u si et seulement si PGCD(a, m) = 1
Équation
a x ≡ b (mod m) donne x ≡ u × b (mod m)
u est l’inverse de a modulo m

PGCD et Bézout

Algorithme d’Euclide
PGCD(a, b) = PGCD(b, reste de a ÷ b)
on s’arrête quand le reste est nul
Identité de Bézout
PGCD(a, b) = 1 équivaut à il existe u et v avec a u + b v = 1
Théorème chinois
si m et n sont premiers entre eux, x ≡ a (mod m) et x ≡ b (mod n) ont une unique solution modulo m n

Fermat, Euler et l’indicatrice

Petit théorème de Fermat
p premier et p ne divise pas a donnent a^{p − 1} ≡ 1 (mod p)
Variante
a^p ≡ a (mod p), pour tout entier a
Théorème d’Euler
PGCD(a, n) = 1 donne a^φ(n) ≡ 1 (mod n)
Indicatrice d’un premier
φ(p) = p − 1 et φ(p^k) = p^k − p^{k − 1}
Multiplicativité
φ(m n) = φ(m) × φ(n), si m et n sont premiers entre eux
Formule générale
φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …
p₁, p₂, … sont les facteurs premiers de n

La méthode pas à pas

Pour a x ≡ b (mod m) : cherchez l’inverse u de a modulo m (un entier tel que a × u laisse un reste de 1), puis x ≡ u × b.
Pour un inverse, essayez les multiples de a jusqu’à tomber sur un reste de 1, ou utilisez l’algorithme d’Euclide étendu.
Pour une grande puissance modulo un nombre premier p, réduisez l’exposant modulo p − 1 grâce à Fermat.
Pour φ(n), décomposez n en facteurs premiers puis appliquez la formule générale.

Exemples résolus

3x ≡ 5 (mod 7) : inverse de 3
3 × 5 = 15 = 2 × 7 + 1
3 × 5 = 15 laisse le reste 1 modulo 7 : 5 est l’inverse de 3.
3x ≡ 5 (mod 7) : on multiplie par l’inverse
5 × 5 = 25 = 3 × 7 + 4
x ≡ 25 ≡ 4 (mod 7). Vérification : 3 × 4 = 12 = 7 + 5, qui est bien congru à 5.
Fermat : 2⁶ modulo 7
2 × 2 × 2 × 2 × 2 × 2 = 64 = 9 × 7 + 1
64 laisse le reste 1 dans la division par 7, comme l’annonce a^{p − 1} ≡ 1.
Indicatrice de 13
13 − 1 = 12
13 est premier : φ(13) = 12.
Indicatrice de 12 = 2² × 3
12 × 1 ÷ 2 × 2 ÷ 3 = 6 × 2 ÷ 3 = 12 ÷ 3 = 4
φ(12) = 4 : parmi 1 à 12, les nombres premiers avec 12 sont 1, 5, 7 et 11.
PGCD de 252 et 198
252 = 198 + 54 ; 198 = 3 × 54 + 36 ; 54 = 36 + 18 ; 36 = 2 × 18
Le dernier reste non nul est 18 : PGCD(252, 198) = 18.

Les pièges à éviter

On ne peut pas simplifier librement : 6 ≡ 2 (mod 4) ne donne pas 3 ≡ 1 (mod 4). Diviser n’est possible qu’en multipliant par un inverse.
Un inverse modulaire n’existe que si PGCD(a, m) = 1 : 2 n’a pas d’inverse modulo 6.
Fermat demande p premier ; pour un module composé, c’est le théorème d’Euler qui s’applique.
φ(m n) = φ(m) φ(n) exige que m et n soient premiers entre eux : φ(4) est 2, et non φ(2) × φ(2) = 1.

S’entraîner

Chaque type d’équation ci-dessous se résout de tête avec la méthode de cette page : la réponse est toujours un nombre entier. Lancez une partie de dix questions, le jeu vous montre la méthode après chaque erreur.

Toutes ces équations, dix questions Congruence modulo un nombre premier Indicatrice d’Euler

Astuces de calcul mental liées : La preuve par 9 : reste dans la division par 9, Les critères de divisibilité, Contrôler un produit avec le dernier chiffre.

Ce cours fait partie du programme de : Bac+3, Bac+8.

Tous les cours

Les quatre opérations Fractions et nombres décimaux Périmètres, aires et volumes Proportionnalité, vitesse et unités Pourcentages et évolutions Équations du premier degré Puissances, racines et valeur absolue Second degré Exponentielle et logarithme Dérivées et intégrales Déterminant Nombres complexes Suites et sommes Dénombrement et probabilités Équations différentielles Factorielle et fonction Gamma

Relecture et vérification

Ce cours est rédigé par l’éditeur du site. Les exemples chiffrés sont recalculés à chaque mise à jour, et 0 formule sur 14 est testée sur des valeurs aléatoires. Il n’a pas encore été relu par un enseignant de mathématiques : si vous repérez une erreur ou une formule manquante, signalez-la, elle sera corrigée.

Sources

Mathématiques expertes : programme de l’enseignement optionnel de la classe terminale généraleMinistère de l’Éducation nationale (juin 2019), 2019 (Programme officiel, France)Citée ici pour : congruences dans ℤ, théorèmes de Bézout et de Gauss, petit théorème de Fermat, algorithme d’Euclide (terminale, option mathématiques expertes).
Ce que couvre cette source
Texte de 16 pages (juin 2019) : nombres complexes (forme algébrique, module, argument, formes trigonométrique et exponentielle, formules de Moivre et du binôme), arithmétique (congruences, théorèmes de Bézout et de Gauss, petit théorème de Fermat) et graphes et matrices (opérations, inverse, puissances, systèmes linéaires, chaînes de Markov). Il ne parle pas du déterminant d’une matrice. Je n’ai pas vérifié s’il a été modifié depuis 2019.

Ce que la page écrit au-delà de ces documents est de l’éditeur : des techniques classiques de calcul mental, des exemples recalculés par les tests du site et des choix de présentation.

Mis à jour le 5 novembre 2026