Arithmétique et congruences
Fiche de révision compacte sur les entiers, les congruences et les équations en nombres entiers.
1
Divisibilité et division euclidienne
Écriture fondamentale
a = bq + r avec b \neq 0, q entier et 0 \le r < b.
n = aksignifie queadivisen.- Le reste est unique dans la division euclidienne.
Repères rapides
Divisibilité
n = ak- Reste nul
adivisen
Division euclidienne
a = bq + r- Reste borné
- Décompose un entier
2
PGCD et identité de Bézout
PGCD
- Le PGCD est le plus grand diviseur commun.
- L’algorithme d’Euclide calcule le PGCD.
Si d=\gcd(a,b), alors il existe u et v entiers tels que au+bv=d.
Mémo
Bézout transforme un PGCD en combinaison linéaire.
3
Congruences modulo n
Définition
a \equiv b [n] signifie que n divise a-b.
- Même reste dans la division par
n. - On calcule modulo
npour simplifier. - Toujours préciser le module `n`.
Règle de calcul
- 1
Réduire chaque nombre modulo
n. - 2
Remplacer par des restes plus petits.
4
Gauss et équations diophantiennes
Théorème de Gauss
On l’utilise quand deux facteurs sont premiers entre eux pour simplifier une divisibilité.
Équation diophantienne
Résoudre dans \mathbb{Z} : 15x+21y=3.
- On simplifie par
3:5x+7y=1. - Comme
\gcd(5,7)=1, Bézout donne une solution. - On cherche une combinaison linéaire égale à
1.
Il existe des solutions entières, car le PGCD de 15 et 21 divise 3.
Résolution type
- 1
Isoler une expression.
- 2
Factoriser si possible.
5
S’entraîner
Questions flash
- Dire si
12divise84. - Écrire la division euclidienne de
29par5. - Calculer
\gcd(18,30).
Rappel express
- La divisibilité sert à tester un reste nul.
- Euclide calcule le PGCD rapidement.
À retenir
Résumé
- Divisibilité et division euclidienne structurent les calculs sur les entiers.
- PGCD et Euclide donnent le bon diviseur commun.
- Bézout fournit une combinaison linéaire essentielle.
- Congruences simplifient les calculs modulo
n.