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 $} \]

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 $} \]

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 :

La notation mathématique \( \fbox{$ b | a $} \) synthétise ces notions :

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 :

\( 0 \) est considéré :

Parité et addition :

Parité et multiplication (un seul nombre pair suffit pour que le résultat soit pair) :

Nombres premiers

Un nombre premier est :

Aucune table de multiplication ne peut les atteindre (sauf la table de 1).

Décomposition :

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 :

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 \) :

  1. 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 \)
  2. 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 \)
    • démonstration : \[\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 à :

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 :

Divisible par Si Divisible Pas divisible
Règles portant sur le dernier chiffre 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 2 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 3 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é

Exemple avec la divisibilité par 9

On prend par exemple le nombre \( 738 \) :

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

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".

Précédent Comprendre les tables de multiplication Tous Suivant Développement et factorisation

Tag Kemar Joint