Divisibilité
Division euclidienne
La division euclidienne d'un nombre entier naturel appelé dividende par un autre entier naturel appelé diviseur revient à trouver deux autres entiers naturels appelés respectivement quotient et reste tels que :
\[ \fbox{$ a = b \times q + r $} \]
- \( a \) = dividende, du latin dividendus qui signifie "celui qui doit être partagé"
- \( b \) = diviseur, du latin divisor qui signifie "celui qui partage"
- \( q \) = quotient de la division de \( a \) par \( b \), du latin quotiens qui signifie "combien de fois"
- \( r \) = reste
- \( r \) est toujours inférieur au diviseur (compris entre \( 0 \) et \( b - 1 \)) car il représente ce qui reste après la division complète
Pour poser une division, voir ces techniques (dont celle de la potence).
Divisibles et multiples
Si le quotient d'une division euclidienne est un nombre entier et que le reste est nul, alors :
\[ \fbox{$ a = b \times q $} \]
- \( a \) est un multiple de \( b \) (\( a \) contient plusieurs fois exactement \( b \))
- \( a \) est divisible par \( b \) (la division de \( a \) par \( b \) est un nombre entier)
- \( b \) divise \( a \)
- \( b \) est un diviseur de \( a \)
On peut visualiser le concept de la divisibilité comme la possibilité de partager en lots de même taille :
0 est souvent omis de la liste des multiples :
- mais il est multiple de tous les nombres
- car quel que soit \( n \), \( 0 = 0 \times n \)
La notation mathématique \( \fbox{$ b | a $} \) synthétise ces notions :
- \( b \) divise \( a \)
- \( b \) est un diviseur de \( a \)
- \( a \) est un multiple de \( b \)
- \( a \) est divisible par \( b \)
Donc, si \( a \) est divisible par \( b \), alors \( a \) est un multiple de \( b \) (c'est la même chose) :
Parité
Tout entier est soit pair soit impair :
- un entier pair est un entier multiple de 2
- un entier impair ne peut être divisé exactement et sans reste
Parité et addition :
- Pair + Pair = Pair
- Impair + Impair = Pair
- Pair + Impair = Impair
Parité et multiplication (un seul nombre pair suffit pour que le résultat soit pair) :
- Pair × Pair = Pair
- Impair × Impair = Impair
- Pair × Impair = Pair
Nombres premiers
Un nombre premier est :
- un entier naturel (\( n \in \mathbb{N} \)) plus grand que 1
- qui admet exactement deux diviseurs distincts entiers et positifs : 1 et lui-même
Aucune table de multiplication ne peut les atteindre (sauf la table de 1).
Décomposition :
- tout entier non premier peut être décomposé en un produit de nombre premiers plus petits
- tout nombre premier ne peut être décomposé (il est sa propre décomposition par définition)
Les nombres premiers de 1 à 100 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Pour s'en rappeler il existe un moyen simple :
- on observe qu'après 2 et 3 et jusqu'à 100, tous les multiples de 6 ont au moins un nombre voisin qui est premier
- il suffit alors d'écarter les multiples de 5 et de 7
| Multiples de 5 ou de 7 | 35 | 65 | 77 | 95 | ||||||||||||
| Nombres premiers | 5 | 11 | 17 | 23 | 29 | 41 | 47 | 53 | 59 | 71 | 83 | 89 | ||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Multiples de 6 | 6 | 12 | 18 | 24 | 30 | 36 | 42 | 48 | 54 | 60 | 66 | 72 | 78 | 84 | 90 | 96 |
| Nombres premiers | 7 | 13 | 19 | 31 | 37 | 43 | 61 | 67 | 73 | 79 | 97 | |||||
| Multiples de 5 ou de 7 | 25 | 49 | 55 | 85 | 91 | |||||||||||
Pour trouver les nombres premiers, voir aussi :
PGCD et PPCM
PGCD Plus Grand Commun Diviseur
Le PGCD de deux entiers naturels est le plus grand entier naturel qui divise à la fois \( a \) et \( b \).
Noté \( (a,b) \) ou \( \text{pgcd}(a,b) \).
PPCM Plus Petit Commun Multiple
Le PPCM de deux entiers naturels est le plus petit entier naturel multiple à la fois de \( a \) et de \( b \).
Noté \( [a,b] \) ou \( \text{ppcm}(a,b) \).
Trouver le PGCD avec l'algorithme d'Euclide
L'algorithme d'Euclide utilise le reste \( r \) de la division euclidienne de \( a \) par \( b \) :
\[ \fbox{$ \text{pgcd}(a,b) = \text{pgcd}(b,r) $} \]
En effet, si la division de \( a \) par \( b \) :
- donne un reste \( r \) nul, alors \( a = b \times q \) et :
- \( b \) est un diviseur de \( a \)
- or aucun diviseur de \( b \) ne peut être plus grand que \( b \) lui-même : \( b \) est son propre plus grand diviseur
- donc \( b \) est le plus grand diviseur commun de \( a \) et \( b \)
- laisse un reste \( r \), alors \( a = b \times q + r \) et :
- les diviseurs communs de \( a \) et \( b \) sont aussi ceux de \( b \) et \( r \), voir la démonstration ci-dessous :
- \[\begin{align} \text{Soit :} \\ a &= bq + r \\ \text{et $d$ un diviseur commun de $a$ et $b$,} \\ \text{alors on peut écrire $a$ et $b$ comme ça :} \\ a &= dy \\ b &= dz \\ \text{Puis les remplacer dans l'égalité initiale :} \\ dy &= dzq + r \\ r &= dy - dzq \\ r &= d(y - zq) \\ \text{Donc $d$ divise aussi $r$.} \\ \end{align}\]
- donc on peut remplacer \( a \) et \( b \) par \( b \) et \( r \) qui ont le même plus grand diviseur commun
L'algorithme d'Euclide consiste à répéter cette opération tant qu'il y a un reste non nul.
Ainsi, calculer le plus grand diviseur des nombres 90 et 21 avec l'algorithme d'Euclide consiste à :
- remplacer le couple (90, 21)
- par le couple (21, 6)
- puis par le couple (6, 3)
- et, 6 étant un multiple de 3, par le nombre 3 qui est le résultat
Trouver le PGCD et le PPCM par décomposition
La décomposition en nombres premiers donne une méthode systématique pour trouver les PGCD et PPCM.
| PGCD Plus grand diviseur commun |
PPCM Plus petit multiple commun |
|
|---|---|---|
| 1 | Décomposer chaque terme en produits de nombres premiers | |
| 2 | Garder les facteurs premiers communs aux deux décompositions | Garder les facteurs premiers (communs ou pas) des deux décompositions |
| 3 | Les affecter des exposants les plus petits | Les affecter des exposants les plus grands |
| 4 | Multiplier ces facteurs pour obtenir un produit | |
Illustration avec un diagramme de Venn :
Exemples d'utilisation
Soit un rectangle de longueur 90 cm et de largeur 42 cm que l'on veut daller avec des carrés les plus grands possibles. Quelle sera la longueur du côté de ce carré ? On peut utiliser le \( \text{pgcd}(90,42) \) pour trouver le nombre commun à la longueur et à la largeur le plus grand possible :
\[ \left. \begin{array}{l} 90 = 2^1 \times 3^2 \times 5^1 \\ 42 = 2^1 \times 3^1 \times 7^1 \end{array} \right\} \quad \text{pgcd}(90,42) = 2^1 \times 3^1 = 6 \]
Soit une tour constituée de briques de 90 cm et une autre constituée de briques de 42 cm. À quelle plus petite hauteur se rejoignent exactement les tours ? On peut utiliser le \( \text{ppcm}(90,42) \) pour trouver le nombre commun à la longueur et à la largeur le plus petit possible :
\[ \left. \begin{array}{l} 90 = 2^1 \times 3^2 \times 5^1 \\ 42 = 2^1 \times 3^1 \times 7^1 \end{array} \right\} \quad \text{ppcm}(90,42) = 2^1 \times 3^2 \times 5^1 \times 7^1 = 630 \]
Propriétés
Propriétés reliant le PGCD et le PPCM :
\[\begin{align} \text{pgcd}(15,20) &= 2^{\min{(0,2)}} \times 3^{\min{(1,0)}} \times 5^{\min{(1,1)}} \\ &= 2^0 \times 3^0 \times 5^1 \\ &= 5 \\ \text{ppcm}(15,20) &= 2^{\max{(0,2)}} \times 3^{\max{(1,0)}} \times 5^{\max{(1,1)}} \\ &= 2^2 \times 3^1 \times 5^1 \\ &= 60 \\ \end{align}\]
Si \( a,b \in \mathbb{N} \), on a toujours :
\[ \fbox{$ \text{pgcd}(a,b) \times \text{ppcm}(a,b) = a \times b $} \]
…car les exposants s'annulent :
\[ \fbox{$ \min{(e,f)} + \max{(e,f)} = e + f $} \]
De là, on peut déduire le PPCM en connaissant le PGCD :
\[ \text{ppcm}(a,b) = \frac{a \times b}{\text{pgcd}(a,b)} \]
Critères de divisibilité
Les critères de divisibilité sont un prérequis pour :
- décomposer un nombre en produits de nombres premiers
- simplifier une fraction
| Divisible par | Si | Divisible | Pas divisible |
|---|---|---|---|
| Règles portant sur le chiffre des unités seulement | |||
| 2 | le chiffre des unités est pair | 3978 | 4975 |
| 5 | le chiffre des unités est 0 ou 5 | 14975 | 10978 |
| 10 | le chiffre des unités est 0 | 15990 | 10536 |
| Règles portant sur les deux derniers chiffres | |||
| 4 | les deux derniers chiffres forment un multiple de 4 | 8512 | 7518 |
| 25 | les deux derniers chiffres sont 00, 25 50 ou 75 | 65475 | 123 |
| Règles portant sur les trois derniers chiffres | |||
| 8 | les trois derniers chiffres forment un multiple de 8 | 1728 | 3999 |
| Règles portant sur tous les chiffres | |||
| 3 | la racine numérique (somme des chiffres) est divisible par 3 | 315 | 139 |
| 9 | la racine numérique (somme des chiffres) est divisible par 9 | 711 | 93 |
| 11 | la somme des chiffres de rang impair moins la somme des chiffres de rang pair donne un multiple de 11 (11, 22, 33…) | 71918 | 333 |
| Autres règles | |||
| 6 | le nombre est divisible à la fois par 2 et par 3 | 48 | 20 |
| 7 | le nombre sans le dernier chiffre moins le double du dernier chiffre est un multiple de 7 (ici 27 - 6 = 21) | 273 | 582 |
| 12 | le nombre est divisible à la fois par 3 et par 4 | 2160 | 4579 |
Preuves des critères de divisibilité
- Blaise Pascal, Des caractères de divisibilité des nombres déduits de la somme de leurs chiffres, ou les rubans de Pascal
- Preuves des critères de divisibilité
- Critère universel de divisibilité (PDF)
Exemple avec la divisibilité par 9
On prend par exemple le nombre \( 738 \) :
- On travaille en base 10, ça veut dire qu'on peut décomposer \( 738 \) :
- \( 738 = (7 \times 100) + (3 \times 10) + (8 \times 1) \)
- On remplace \( 100 \) par \( 99 + 1 \) et \( 10 \) par \( 9 + 1 \) pour avoir des termes divisibles par \( 9 \), puis on rassemble les "\( \times 1 \)" avec la distributivité et la commutativité :
- \(\begin{align} 738 &= (7 \times (99 + 1)) + (3 \times (9 + 1)) + (8 \times 1) \\ &= (7 \times 99) + (7 \times 1) + (3 \times 9) + (3 \times 1) + (8 \times 1) \\ &= (7 \times 99) + (3 \times 9) + (7 \times 1) + (3 \times 1) + (8 \times 1) \\ &= (7 \times 99) + (3 \times 9) + ((7 + 3 + 8) \times 1) \\ &= \underbrace{(7 \times 99)}_{\text{divisible par }9} + \underbrace{(3 \times 9)}_{\text{divisible par }9} + \underbrace{(7 + 3 + 8)}_{\text{divisible par }9} \\ \end{align}\)
- \( 738 \) est donc divisible par \( 9 \) car égal à une somme dont chaque partie est divisible par \( 9 \)
On remarque que le troisième terme est la somme des chiffres du nombre \( 738 \) ! Plus généralement :
\[ \fbox{$ d_2d_1d_0 = \underbrace{(d_2 \times 99)}_{\text{divisible par }9} + \underbrace{(d_1 \times 9)}_{\text{divisible par }9} + \underbrace{(d_2 + d_1 + d_0)}_{\text{somme des chiffres}} $} \]
Il suffit donc que la somme des chiffres d'un nombre soit divisible par 9 pour que tout le nombre soit divisible par 9.
Exemple avec la divisibilité par 5
- Soit un nombre à quatre chiffres noté \( n \) avec \( a \), \( b \), \( c \) et \( d \) des entiers compris entre 0 et 9 :
- \( n = abcd \)
- On travaille en base 10, ça veut dire qu'on peut décomposer \( n \) :
- \( n = a \times 1000 + b \times 100 + c \times 10 + d \)
- En posant \( q \)…
- \( q = a \times 200 + b \times 20 + c \times 2 \)
- …on peut simplifier l'égalité \( n \) :
- \( n = 5 * q + d \)
- Imaginons que \( n \) soit un multiple de 5 :
- \( n = 5 * k \)
- Alors :
- \( 5 * k = 5 * q + d \)
- \( 5 * k - 5 * q = d \)
- \( d = 5(k - q) \)
- \( d \) est un multiple de 5 !
- \( d \) étant le chiffre des unités, il ne peut être que 0 ou 5, sinon il ne serait pas un multiple de 5.
- Donc \( n \) est multiple de 5 si \( d=0 \) ou \( d=5 \).
Congruences
L'image d'un fil hélicoïdal, utilisé dans "Critères usuels et moins usuels de divisibilité", permet d'illustrer les congruences :
Etant donnés un entier naturel \( n \) et deux entiers relatifs \( a \) et \( b \), on dit que \( a \) est congru à \( b \) modulo \( n \) lorsque \( a - b \) est multiple de \( n \).
On note \( a \equiv b \pmod{m} \).
Congruence, du latin congruere, signifie se rencontrer en étant en mouvement. Et modulo, du latin modulus, signifie mesure. Ainsi, dire que 5 et 9 sont congrus modulo 4 signifie que 5 rencontre 9 lorsqu'on prend 4 comme mesure.
Voir "L'opérateur modulo".
Joint