Cours — Arithmétique : divisibilité et congruences
Nombres premiers • décomposition • PGCD • Bézout • congruences modulo \(n\) • preuves types (Maths Expertes).
Divisibilité
PGCD
Bézout
Modulo \(n\)
Preuves
0) Vocabulaire & notations
- Divisibilité : pour \(a,b\in\mathbb Z\), on écrit \(a\mid b\) si \(\exists k\in\mathbb Z\) tel que \(b=ak\).
- Multiple : \(b\) est un multiple de \(a\) \(\Leftrightarrow a\mid b\).
- PGCD : \(\gcd(a,b)\) est le plus grand entier \(d\ge 0\) qui divise \(a\) et \(b\).
- Congruence : \(a\equiv b\pmod n\) signifie \(n\mid(a-b)\) (avec \(n\ge 2\)).
Piège classique
\(a\mid b\) et \(b\mid a\) \(\Rightarrow\) pas forcément \(a=b\) : on a seulement \(|a|=|b|\) (ex : \(2\mid -2\) et \(-2\mid 2\)).
Réflexe
Pour prouver \(a\mid b\), on cherche à écrire \(b=a\times(\text{entier})\).
Pour prouver \(a\nmid b\), on travaille souvent modulo un petit entier.
Pour prouver \(a\nmid b\), on travaille souvent modulo un petit entier.
1) Propriétés de divisibilité
\[
\begin{aligned}
&a\mid b \Rightarrow a\mid (bk)\ \text{pour tout }k\in\mathbb Z.\\
&a\mid b \ \text{et}\ a\mid c \Rightarrow a\mid (b+c)\ \text{et}\ a\mid(b-c).\\
&a\mid b \Rightarrow a\mid (b+ac)\ \text{pour tout }c\in\mathbb Z.\\
&a\mid b \ \text{et}\ b\mid c \Rightarrow a\mid c.
\end{aligned}
\]
Exemple (linéarité)
Montrer que \(12\mid (84-60)\).
Comme \(12\mid 84\) et \(12\mid 60\), alors \(12\mid (84-60)=24\).
Comme \(12\mid 84\) et \(12\mid 60\), alors \(12\mid (84-60)=24\).
Méthode “combinaison linéaire”
Si \(a\mid b\) alors \(b=aq\). Pour prouver \(a\mid(\alpha b+\beta c)\), on remplace \(b\) et/ou \(c\) par une forme \(a\times(\text{entier})\).
2) Nombres premiers • décomposition en facteurs premiers
Définitions
- \(p\ge 2\) est premier si ses seuls diviseurs positifs sont \(1\) et \(p\).
- Un entier \(n\ge 2\) est composé s’il n’est pas premier.
Théorème fondamental de l’arithmétique
\[
\forall n\ge 2,\quad n=\prod_{i=1}^r p_i^{\alpha_i}
\quad\text{avec }p_i\ \text{premiers distincts et }\alpha_i\in\mathbb N.
\]
La décomposition est unique à l’ordre près.
Exemple
\(840 = 84\times 10 = (2^2\cdot 3\cdot 7)\cdot(2\cdot 5)=2^3\cdot 3\cdot 5\cdot 7.\)
Piège
“\(n\) divisible par 6” \(\Leftrightarrow\) \(2\mid n\) et \(3\mid n\).
Mais “\(n\) divisible par 12” \(\Leftrightarrow\) \(4\mid n\) et \(3\mid n\) (pas juste \(2\mid n\) et \(3\mid n\)).
Mais “\(n\) divisible par 12” \(\Leftrightarrow\) \(4\mid n\) et \(3\mid n\) (pas juste \(2\mid n\) et \(3\mid n\)).
3) PGCD • PPCM • calculs efficaces
Avec factorisation
Si \(a=\prod p^{\alpha_p}\) et \(b=\prod p^{\beta_p}\), alors :
\[
\gcd(a,b)=\prod p^{\min(\alpha_p,\beta_p)}
\qquad
\mathrm{lcm}(a,b)=\prod p^{\max(\alpha_p,\beta_p)}.
\]
Identité clé : \(\gcd(a,b)\cdot\mathrm{lcm}(a,b)=|ab|\).
Algorithme d’Euclide (à savoir faire vite)
Pour \(a\ge b\ge 0\) :
\[
a=bq+r,\quad 0\le r
On itère jusqu’à obtenir \(r=0\). Le dernier reste non nul est le PGCD.
Exemple Euclide
\[
\begin{aligned}
252 &= 198\cdot 1 + 54\\
198 &= 54\cdot 3 + 36\\
54 &= 36\cdot 1 + 18\\
36 &= 18\cdot 2 + 0
\end{aligned}
\Rightarrow \gcd(252,198)=18.
\]
Réflexe examen
Pour un PGCD “gros” sans factoriser, Euclide est souvent imbattable.
La factorisation sert surtout pour comparer, compter des diviseurs, ou prouver des propriétés.
4) Identité de Bézout • équations diophantiennes
Bézout
\[
\gcd(a,b)=d \ \Longleftrightarrow\ \exists (u,v)\in\mathbb Z^2 \text{ tel que } au+bv=d.
\]
En particulier, si \(\gcd(a,b)=1\), alors \(\exists u,v\in\mathbb Z\) : \(au+bv=1\).
Conséquence (inversibilité mod \(n\))
\(a\) admet un inverse modulo \(n\) \(\Leftrightarrow\ \gcd(a,n)=1\).
Si \(au+nv=1\), alors \(au\equiv 1\pmod n\) donc \(u\) est un inverse de \(a\) mod \(n\).
Si \(au+nv=1\), alors \(au\equiv 1\pmod n\) donc \(u\) est un inverse de \(a\) mod \(n\).
Exemple : inverse modulo
Trouver l’inverse de \(7\) modulo \(26\).
\[
\begin{aligned}
26 &= 7\cdot 3 + 5\\
7 &= 5\cdot 1 + 2\\
5 &= 2\cdot 2 + 1\\
2 &= 1\cdot 2 + 0
\end{aligned}
\]
Remontée :
\[
1=5-2\cdot 2=5-(7-5)\cdot 2=3\cdot 5-2\cdot 7
\]
et \(5=26-7\cdot 3\), donc
\[
1=3(26-7\cdot 3)-2\cdot 7=3\cdot 26-11\cdot 7.
\]
Ainsi \(-11\) est un inverse : \(7^{-1}\equiv -11\equiv 15\pmod{26}\).
Piège
“Diviser” en modulo n’est pas autorisé si l’élément n’est pas inversible.
On ne peut pas simplifier par \(a\) dans \(ax\equiv ay\pmod n\) si \(\gcd(a,n)\ne 1\).
Équation diophantienne \(ax+by=c\)
- Elle admet des solutions entières \(\Leftrightarrow d=\gcd(a,b)\mid c\).
- Si \((x_0,y_0)\) est une solution, alors toutes les solutions sont \[ x=x_0+\frac{b}{d}t,\qquad y=y_0-\frac{a}{d}t,\qquad t\in\mathbb Z. \]
5) Congruences modulo \(n\) — règles de calcul
Définition
\[
a\equiv b\pmod n \ \Longleftrightarrow\ n\mid(a-b).
\]
Règles (à utiliser sans hésiter)
Si \(a\equiv b\pmod n\) et \(c\equiv d\pmod n\), alors :
\[
\begin{aligned}
a+c &\equiv b+d \pmod n,\\
a-c &\equiv b-d \pmod n,\\
ac &\equiv bd \pmod n,\\
a^k &\equiv b^k \pmod n \quad (k\in\mathbb N).
\end{aligned}
\]
Exemple : preuve rapide
Montrer que \(37^2-1\) est divisible par \(12\).
On travaille modulo \(12\) : \(37\equiv 1\pmod{12}\) donc \(37^2\equiv 1^2\equiv 1\pmod{12}\). Ainsi \(37^2-1\equiv 0\pmod{12}\) donc \(12\mid(37^2-1)\).
On travaille modulo \(12\) : \(37\equiv 1\pmod{12}\) donc \(37^2\equiv 1^2\equiv 1\pmod{12}\). Ainsi \(37^2-1\equiv 0\pmod{12}\) donc \(12\mid(37^2-1)\).
Exemple : cycles de puissances
Calculer \(7^{202}\pmod 5\).
\(7\equiv 2\pmod 5\). Or \(2^4\equiv 1\pmod 5\).
\(202=4\cdot 50+2\) donc \(2^{202}\equiv (2^4)^{50}\cdot 2^2\equiv 1^{50}\cdot 4\equiv 4\pmod 5\).
\(7\equiv 2\pmod 5\). Or \(2^4\equiv 1\pmod 5\).
\(202=4\cdot 50+2\) donc \(2^{202}\equiv (2^4)^{50}\cdot 2^2\equiv 1^{50}\cdot 4\equiv 4\pmod 5\).
Pièges classiques (à connaître)
- \(a\equiv b\pmod n\) ne signifie pas \(a=b\), seulement “même reste”.
- \(ab\equiv 0\pmod n\) n’implique pas forcément \(a\equiv 0\) ou \(b\equiv 0\) si \(n\) n’est pas premier.
- Simplification : \(ax\equiv ay\pmod n\) \(\Rightarrow x\equiv y\pmod n\) uniquement si \(\gcd(a,n)=1\).
6) Schémas de preuve “niveau Maths Expertes”
A) Prouver une divisibilité
- Factoriser : \(a^2-b^2=(a-b)(a+b)\), etc.
- Écrire une combinaison : montrer \(n\mid(\alpha A+\beta B)\).
- Passer au modulo : “\(A\equiv 0\pmod n\)”.
Exemple : \(n^3-n=n(n-1)(n+1)\) est divisible par \(3\) (trois entiers consécutifs).
B) Prouver qu’un entier est premier / non premier
- Tester les diviseurs \(\le \sqrt{n}\) si \(n\) petit.
- Montrer qu’il admet un diviseur non trivial (factorisation, modulo…).
Astuce : si \(n\equiv 0\pmod 2\) et \(n>2\), alors \(n\) n’est pas premier.
C) Résoudre une congruence linéaire
Résoudre \(ax\equiv b\pmod n\).
- Si \(\gcd(a,n)=1\) : calculer \(a^{-1}\) mod \(n\), puis \(x\equiv a^{-1}b\pmod n\).
- Sinon : poser \(d=\gcd(a,n)\). Solutions \(\Leftrightarrow d\mid b\), puis réduire.
D) “Modulo intelligent”
Choisir un petit modulo adapté : \(2\), \(3\), \(4\), \(5\), \(8\), \(9\), \(11\), \(12\)…
Souvent : parité / modulo \(3\) / modulo \(4\) (carrés) / modulo \(9\) (somme des chiffres).
Souvent : parité / modulo \(3\) / modulo \(4\) (carrés) / modulo \(9\) (somme des chiffres).
7) Mini-fiche express (à connaître par cœur)
\[
\begin{aligned}
&a\mid b \Leftrightarrow \exists k\in\mathbb Z,\ b=ak.\\[2pt]
&a\equiv b\pmod n \Leftrightarrow n\mid(a-b).\\[2pt]
&\gcd(a,b)=\gcd(b,a\bmod b)\quad(\text{Euclide}).\\[2pt]
&\exists u,v\in\mathbb Z,\ au+bv=\gcd(a,b)\quad(\text{Bézout}).\\[2pt]
&a\ \text{inversible mod }n \Leftrightarrow \gcd(a,n)=1.
\end{aligned}
\]
À faire ensuite
Passe à la fiche ultra-synthèse puis aux exercices 19–20/20 (preuves + congruences).
Fiche →
Exercices →
Quiz HARD →