Fiche — Arithmétique : divisibilité & congruences
Tout ce qu’il faut savoir vite et juste : définitions, résultats clés,
méthodes types et pièges classiques (Maths Expertes).
1) Définitions essentielles
\[
\begin{aligned}
&a\mid b \;\Longleftrightarrow\; \exists k\in\mathbb Z,\ b=ak.\\[2pt]
&a\equiv b\pmod n \;\Longleftrightarrow\; n\mid(a-b).\\[2pt]
&\gcd(a,b)=\text{plus grand diviseur commun de }a,b.
\end{aligned}
\]
À ne pas confondre :
\(a\equiv b\pmod n\) ne signifie pas \(a=b\), mais “même reste modulo \(n\)”.
\(a\equiv b\pmod n\) ne signifie pas \(a=b\), mais “même reste modulo \(n\)”.
2) Divisibilité — résultats clés
\[
\begin{aligned}
&a\mid b \Rightarrow a\mid(bk)\quad(\forall k\in\mathbb Z)\\
&a\mid b \text{ et } a\mid c \Rightarrow a\mid(b\pm c)\\
&a\mid b \text{ et } b\mid c \Rightarrow a\mid c
\end{aligned}
\]
Méthode standard :
Pour montrer \(a\mid b\), écrire explicitement \(b=a\times(\text{entier})\), ou passer modulo \(a\).
Pour montrer \(a\mid b\), écrire explicitement \(b=a\times(\text{entier})\), ou passer modulo \(a\).
3) Nombres premiers
- \(p\ge2\) est premier ⇔ ses seuls diviseurs sont \(1\) et \(p\).
- Tout entier \(n\ge2\) admet une décomposition unique en facteurs premiers.
\[
n=\prod_{i=1}^r p_i^{\alpha_i}
\quad (p_i\ \text{premiers distincts})
\]
Piège :
“\(n\) divisible par \(6\)” ⇔ divisible par \(2\) et par \(3\). Mais “\(n\) divisible par \(12\)” ⇔ divisible par \(4\) et par \(3\).
“\(n\) divisible par \(6\)” ⇔ divisible par \(2\) et par \(3\). Mais “\(n\) divisible par \(12\)” ⇔ divisible par \(4\) et par \(3\).
4) PGCD — méthode rapide
\[
a=bq+r,\ 0\le r
Réflexe examen :
Pour un PGCD de grands nombres → algorithme d’Euclide, pas la factorisation.
Pour un PGCD de grands nombres → algorithme d’Euclide, pas la factorisation.
\[
\gcd(a,b)\cdot\mathrm{lcm}(a,b)=|ab|
\]
5) Bézout & conséquences
\[
\exists(u,v)\in\mathbb Z^2,\quad au+bv=\gcd(a,b)
\]
Conséquence majeure :
\(a\) est inversible modulo \(n\) ⇔ \(\gcd(a,n)=1\).
\(a\) est inversible modulo \(n\) ⇔ \(\gcd(a,n)=1\).
Interdit :
On ne “divise” jamais une congruence par un nombre non inversible modulo \(n\).
On ne “divise” jamais une congruence par un nombre non inversible modulo \(n\).
6) Congruences modulo \(n\)
Si \(a\equiv b\pmod n\) et \(c\equiv d\pmod n\), alors :
\[
a\pm c\equiv b\pm d,\qquad
ac\equiv bd,\qquad
a^k\equiv b^k
\]
Astuce puissante :
Remplacer les grands nombres par leur reste modulo \(n\) avant de calculer (cycles).
Remplacer les grands nombres par leur reste modulo \(n\) avant de calculer (cycles).
Pièges fréquents :
- \(ab\equiv0\pmod n\) n’implique pas \(a\equiv0\) ou \(b\equiv0\) si \(n\) non premier.
- Simplification autorisée uniquement si \(\gcd(a,n)=1\).
7) Schémas types à appliquer
Prouver une divisibilité
- Factoriser
- Combinaison linéaire
- Calcul modulo adapté
Résoudre \(ax\equiv b\pmod n\)
- \(\gcd(a,n)=1\) → inverse
- \(\gcd(a,n)\ne1\) → condition de divisibilité
À réciter absolument
\[
\begin{aligned}
&a\mid b \Leftrightarrow b=ak\\
&a\equiv b\pmod n \Leftrightarrow n\mid(a-b)\\
&\gcd(a,b)=\gcd(b,a\bmod b)\\
&au+bv=\gcd(a,b)\\
&a^{-1}\ (\text{mod }n)\ \Leftrightarrow\ \gcd(a,n)=1
\end{aligned}
\]