Chapitre 20 — diviseurs, division euclidienne et l'art du raisonnement par disjonction selon le reste. Tout ce qu'il faut savoir refaire, condensé.
Naviguez avec les flèches ← → du clavier, ou via le Sommaire.
Les fonctions Python % et //, et les pièges classiques à ne pas oublier le jour du contrôle.
Soient $a\in\mathbb{Z}$ et $b\in\mathbb{Z}^*$. On dit que $b$ divise $a$ lorsque :
Trois façons de dire la même chose : « $b$ divise $a$ », « $b$ est un diviseur de $a$ », « $a$ est un multiple de $b$ ».
L'ensemble des diviseurs de $a$ se note $\ \mathrm{Div}(a)=\{\,b\in\mathbb{Z}^*\mid b\mid a\,\}.$
$\mathrm{Div}(0)=\mathbb{Z}$ : tout entier non nul divise $0$, car $0=b\times0$.
$0\mid 0$ est vrai, mais $0$ ne divise aucun entier non nul. À ne pas confondre avec la forme indéterminée $\dfrac{0}{0}$.
$\mathrm{Div}(1)=\{-1,\,1\}$.
Pour tout $a$ : $\ \{-1,\,1,\,-a,\,a\}\subset\mathrm{Div}(a).$
$\mathrm{Div}(a)=\mathrm{Div}(|a|)$ : pour chercher les diviseurs, on travaille avec les diviseurs positifs.
Sur $\mathbb{N}$, $\mid$ est réflexive, antisymétrique et transitive : c'est une relation d'ordre… mais partiel. Deux entiers ne sont pas toujours comparables (ex. $7$ et $10$).
Pour $a,b$ non nuls : $\ b\mid a \implies |b|\leqslant|a|.$ La réciproque est fausse ($-7\leqslant 12$ mais $-7\nmid 12$).
Si $c\mid a$ et $c\mid b$, alors pour tous entiers $\alpha,\beta$ :
En particulier : $c\mid a+b$ et $c\mid a-b$.
$5\mid 4+6$ mais $5\nmid 4$ et $5\nmid 6$. Un diviseur d'une somme ne divise pas forcément chaque terme.
Pour les diviseurs communs à $a=6n+5$ et $b=7n+6$ : on cherche une combinaison linéaire qui vaut $\pm1$.
Si $d\mid a$ et $d\mid b$, alors $d\mid 6b-7a$, donc $d\mid 1$, d'où $d\in\{-1,1\}$.
$\mathrm{Div}(a)\cap\mathrm{Div}(b)=\{-1,1\}$ : on dit que $a$ et $b$ sont premiers entre eux.
Pour tous $a\in\mathbb{Z}$ et $b\in\mathbb{Z}^*$, il existe un unique couple $(q,r)\in\mathbb{Z}^2$ tel que :
$q$ est le quotient, $r$ le reste. Si $b\in\mathbb{N}^*$ : $\ 0\leqslant r\lt b$.
Le reste est toujours positif et strictement plus petit que $|b|$ : c'est exactement cette condition $0\leqslant r\lt|b|$ qui rend le couple unique.
Résultat : $q=-4$, $r=7$, et bien $0\leqslant 7\lt 11$. ✓
Dans la division par $b\,(\gt0)$, le reste vit dans $\{0,1,\dots,b-1\}$. Les entiers se rangent donc en $b$ familles disjointes : c'est une partition de $\mathbb{Z}$.
Pour démontrer une propriété de divisibilité : on raisonne par disjonction selon le reste, en traitant chaque cas un par un.
Montrer : si $3\nmid n$, alors $n^2$ a pour reste $1$ dans la division par $3$. Comme $3\nmid n$, on a $n=3q+1$ ou $n=3q+2$.
Dans les deux cas $n^2=3k+1$. $\blacksquare$
Pour prouver « divisible par $6$ » : montrez qu'il est divisible par $2$ et par $3$, puis combinez — $u=3u-2u=3(2b)-2(3a)=6(b-a)$.
a % b renvoie le reste de la division de $a$ par $b$a // b renvoie le quotientn % k == 0 traduit exactement $k\mid n$def diviseurs(n): L = [] for k in range(1, n+1): if n % k == 0: L.append(k) return L >>> diviseurs(2025) [1, 3, 5, 9, 15, 25, 27, 45, 75, 81, 225, 405, 675, 2025]
% reste · // quotient