Divisibilité, division euclidienne et congruences
Divisibilité dans ?, division euclidienne, congruences modulo n et leurs règles de calcul ; applications : restes de puissances, critères de divisibilité, calendrier, chiffrement affine.
1. Divisibilité dans ?
Définition · Diviseur, multiple
Soient $a$ et $b$ deux entiers relatifs. On dit que $a$ divise $b$, noté $a \mid b$, s'il existe un entier $k$ tel que $b = ka$. On dit aussi que $b$ est un multiple de $a$.
Propriété · Combinaisons linéaires
Si $d \mid a$ et $d \mid b$, alors $d$ divise toute combinaison $au + bv$ (avec $u$, $v$ entiers). Par exemple, $d$ divise $a + b$, $a - b$ et $3a - 2b$.
2. Division euclidienne
Propriété · Théorème
Pour tout entier $a$ et tout entier $b \geq 1$, il existe un unique couple $(q\,;\,r)$ d'entiers tel que $a = bq + r$ et $0 \leq r < b$. $q$ est le quotient, $r$ le reste.
Exemple · Avec un négatif
$-17 = 5 \times (-4) + 3$ : le quotient est $-4$ et le reste $3$ (et non $-2$, car un reste est positif).
3. Congruences
Définition · Congruence modulo n
Soit $n \geq 2$. On dit que $a$ est congru à $b$ modulo $n$, noté $a \equiv b \ [n]$, si $n \mid a - b$, c'est-à-dire si $a$ et $b$ ont le même reste dans la division par $n$.
Propriété · Règles de calcul
Si $a \equiv b\ [n]$ et $c \equiv d\ [n]$, alors $a + c \equiv b + d\ [n]$, $ac \equiv bd\ [n]$ et $a^k \equiv b^k\ [n]$ pour tout entier naturel $k$.
Méthode · Reste d'une grande puissance
On cherche une petite puissance congrue à $1$. Exemple : $2^3 = 8 \equiv 1\ [7]$, donc $2^{99} = \left(2^3\right)^{33} \equiv 1\ [7]$ et $2^{100} \equiv 2\ [7]$ : le reste de $2^{100}$ dans la division par $7$ est $2$.
Attention · Pas de division
On ne « simplifie » pas une congruence : $2 \times 3 \equiv 2 \times 0\ [6]$ mais $3 \not\equiv 0\ [6]$. Pour résoudre $ax \equiv b\ [n]$, on multiplie par un inverse de $a$ modulo $n$, quand il existe.
S'entraîner
Exercices corrigés
🎓 20 exercices corrigés et un quiz vous attendent dans ce chapitre.
Créez votre compte gratuit pour voir les corrections, faire les quiz et suivre votre progression.
Diviseurs
★☆☆Lister les diviseurs positifs de $36$.
Divisions euclidiennes
★☆☆Effectuer la division euclidienne de $247$ puis de $250$ par $13$.
Dividende négatif
★★☆Effectuer la division euclidienne de $-17$ par $5$.
Combinaison linéaire
★☆☆Montrer que si $d$ divise $a$ et $b$, alors $d$ divise $3a - 2b$.
Diviseur dépendant de n
★★★Déterminer les entiers naturels $n$ tels que $n + 3$ divise $2n + 11$.
Reste de 2¹?? par 7
★★☆Déterminer le reste de la division de $2^{100}$ par $7$.
Reste de 3²?²? par 5
★★☆Déterminer le reste de $3^{2026}$ dans la division par $5$.
Critère de divisibilité par 9
★★☆Montrer que $10 \equiv 1\ [9]$, en déduire le critère de divisibilité par $9$ et l'appliquer à $123\,456$.
Produit de deux consécutifs
★☆☆Montrer que $n(n + 1)$ est pair pour tout entier $n$.
n³ ? n
★★☆Montrer que $n^3 - n$ est divisible par $6$ pour tout entier $n$.
Somme de deux carrés
★★★Montrer qu'un carré est congru à $0$ ou $1$ modulo $4$. En déduire qu'une somme de deux carrés n'est jamais congrue à $3$ modulo $4$.
Équation 3x ? 2 [7]
★★☆Résoudre $3x \equiv 2\ [7]$.
Calendrier
★☆☆Aujourd'hui est un lundi. Quel jour serons-nous dans $100$ jours ?
Dernier chiffre
★★☆Quel est le dernier chiffre de $7^{2026}$ ?
5? ? 1
★☆☆Montrer que $5^n - 1$ est divisible par $4$ pour tout entier naturel $n$.
2³? ? 1
★★☆Montrer que $2^{3n} - 1$ est divisible par $7$.
x² ? 1 [8]
★★★Montrer que le carré de tout entier impair est congru à $1$ modulo $8$.
Division en Python
★☆☆Que renvoie divmod(247, 13) en Python ? Et -17 // 5, -17 % 5 ?
Chiffrement affine
★★☆On code les lettres A ? 0, B ? 1, …, Z ? 25 et on chiffre $x$ en $y \equiv 3x + 5\ [26]$. Chiffrer C, puis trouver la formule de déchiffrement.
Nombre de diviseurs
★★☆Combien $2^3 \times 3^2$ possède-t-il de diviseurs positifs ? Les lister.
Vérifier
Avez-vous bien compris ?
Répondez au quiz : la correction s'affiche immédiatement.