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 $} \) avec \( r \) compris entre \( 0 \) et \( b - 1 \) (\( r \) toujours inférieur au diviseur)

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 \( 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, mais il est multiple de tous les nombres car quel que soit \( n \), \( \frac{0}{n} = 0 \).

La notation mathématique \( 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 :

Parité et addition :

Parité et multiplication :

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

Tout entier non premier peut être exprimé par un produit de nombre premiers plus petits.

Un nombre premier ne peut être décomposé par définition, on peut dire qu'il est sa propre 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. 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 :

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

PGCD PPCM
Plus grand diviseur commun Plus petit multiple commun
  1. Décomposer chaque terme en produits de nombres premiers
  2. Garder uniquement les facteurs premiers communs aux deux décompositions
  3. Les affecter des exposants les plus petits
  4. Multiplier ces facteurs pour obtenir un produit
  1. Décomposer chaque terme en produits de nombres premiers
  2. Conserver tous les facteurs premiers qui apparaissent (communs ou pas)
  3. Les affecter des exposants les plus grands
  4. Multiplier ces facteurs pour obtenir un produit

Exemples d'utilisation

Soit un rectangle de longueur 90 cm et de largeur 42 cm que je veux 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 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é :

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