Arithmétique : divisibilité, nombres premiers, PGCD

La divisibilité

Un nombre entier $a$ est divisible par un nombre entier $b$ (non nul) si le résultat de la division euclidienne de $a$ par $b$ est un nombre entier et que le reste est nul. On dit alors que $b$ est un diviseur de $a$, et que $a$ est un multiple de $b$.

Méthode
Pour savoir si un nombre $a$ est divisible par un nombre $b$, on peut effectuer la division euclidienne de $a$ par $b$. Si le reste est $0$, alors $a$ est divisible par $b$.
Il existe aussi des critères de divisibilité pour certains nombres :
1. Un nombre est divisible par $2$ s'il est pair (son chiffre des unités est $0, 2, 4, 6$ ou $8$).
2. Un nombre est divisible par $3$ si la somme de ses chiffres est divisible par $3$.
3. Un nombre est divisible par $4$ si le nombre formé par ses deux derniers chiffres est divisible par $4$.
4. Un nombre est divisible par $5$ si son chiffre des unités est $0$ ou $5$.
5. Un nombre est divisible par $9$ si la somme de ses chiffres est divisible par $9$.
6. Un nombre est divisible par $10$ si son chiffre des unités est $0$.

Exemple
Le nombre $120$ est-il divisible par $2$, $3$, $4$, $5$, $9$ et $10$ ?

Corrigé pas à pas
Vérifions la divisibilité de $120$ par chaque nombre :
• Par $2$ : $120$ se termine par $0$, il est donc pair. Oui, $120$ est divisible par $2$ ($120 = 2 \times 60$).
• Par $3$ : La somme des chiffres de $120$ est $1+2+0 = 3$. $3$ est divisible par $3$. Oui, $120$ est divisible par $3$ ($120 = 3 \times 40$).
• Par $4$ : Le nombre formé par les deux derniers chiffres est $20$. $20$ est divisible par $4$ ($20 = 4 \times 5$). Oui, $120$ est divisible par $4$ ($120 = 4 \times 30$).
• Par $5$ : $120$ se termine par $0$. Oui, $120$ est divisible par $5$ ($120 = 5 \times 24$).
• Par $9$ : La somme des chiffres de $120$ est $3$. $3$ n'est pas divisible par $9$. Non, $120$ n'est pas divisible par $9$.
• Par $10$ : $120$ se termine par $0$. Oui, $120$ est divisible par $10$ ($120 = 10 \times 12$).

Erreurs fréquentes
Confondre un diviseur et un multiple. Par exemple, $6$ est un diviseur de $18$, mais $18$ est un multiple de $6$.
Oublier de vérifier que le reste de la division euclidienne est nul pour affirmer la divisibilité.

Les nombres premiers

Un nombre premier est un nombre entier naturel qui possède exactement deux diviseurs distincts : $1$ et lui-même.
• Attention : $1$ n'est pas un nombre premier car il n'a qu'un seul diviseur ($1$).
• Les premiers nombres premiers sont $2, 3, 5, 7, 11, 13, 17, 19, 23, \dots$
• Le seul nombre premier pair est $2$.
Tout nombre entier non premier (et supérieur à $1$) peut être écrit comme un produit de nombres premiers. C'est la décomposition en facteurs premiers*.

Méthode
Pour décomposer un nombre entier en facteurs premiers, on le divise successivement par les plus petits nombres premiers possibles ($2, 3, 5, 7, \dots$) jusqu'à obtenir $1$.
1. Commencer par diviser le nombre par $2$ autant de fois que possible.
2. Si le nombre n'est plus divisible par $2$, essayer de le diviser par $3$ autant de fois que possible.
3. Continuer avec le nombre premier suivant ($5$), puis $7$, et ainsi de suite.

Exemple
Décomposez le nombre $60$ en facteurs premiers.

Corrigé pas à pas
Pour décomposer $60$ en facteurs premiers, nous allons le diviser successivement par les plus petits nombres premiers :
• $60 \div 2 = 30$
• $30 \div 2 = 15$
• $15$ n'est pas divisible par $2$. On essaie le nombre premier suivant, $3$.
• $15 \div 3 = 5$
• $5$ n'est pas divisible par $3$. On essaie le nombre premier suivant, $5$.
• $5 \div 5 = 1$
Nous avons atteint $1$. Les facteurs premiers sont $2, 2, 3, 5$.
Donc, la décomposition en facteurs premiers de $60$ est $2 \times 2 \times 3 \times 5$, que l'on peut écrire $2^2 \times 3 \times 5$.

Erreurs fréquentes
Considérer $1$ comme un nombre premier.
Utiliser des diviseurs qui ne sont pas premiers dans la décomposition (par exemple, diviser par $4$ au lieu de $2 \times 2$).
Oublier de diviser par le même facteur premier plusieurs fois si c'est possible.

Le Plus Grand Commun Diviseur (PGCD)

Le Plus Grand Commun Diviseur (PGCD) de deux nombres entiers non nuls est le plus grand nombre entier qui divise ces deux nombres simultanément.
• On note le PGCD de $a$ et $b$ par $PGCD(a;b)$.
Deux nombres dont le PGCD est $1$ sont dits premiers entre eux*.

Méthode
Il existe plusieurs méthodes pour trouver le PGCD de deux nombres $a$ et $b$.
1. Méthode par la liste des diviseurs :
• Lister tous les diviseurs de $a$.
• Lister tous les diviseurs de $b$.
• Identifier les diviseurs communs aux deux listes.
• Le plus grand de ces diviseurs communs est le PGCD.
2. Méthode par la décomposition en facteurs premiers :
• Décomposer $a$ en facteurs premiers.
• Décomposer $b$ en facteurs premiers.
• Le PGCD est le produit des facteurs premiers communs, chacun pris avec le plus petit de leurs exposants.
3. Algorithme d'Euclide : C'est la méthode la plus efficace pour les grands nombres.
• Effectuer la division euclidienne du plus grand nombre par le plus petit : $a = b \times q + r$ (où $r$ est le reste).
• Si le reste $r$ est $0$, alors $b$ est le PGCD.
• Si le reste $r$ n'est pas $0$, on remplace $a$ par $b$ et $b$ par $r$, puis on recommence une division euclidienne.
• Le PGCD est le dernier reste non nul.

Exemple
Calculez le PGCD de $60$ et $84$.

Corrigé pas à pas
Nous allons calculer le PGCD de $60$ et $84$ en utilisant les trois méthodes :
• Méthode 1 : Liste des diviseurs
• Diviseurs de $60$ : $1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$.
• Diviseurs de $84$ : $1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84$.
• Les diviseurs communs sont : $1, 2, 3, 4, 6, 12$.
• Le plus grand de ces diviseurs communs est $12$. Donc $PGCD(60;84) = 12$.
• Méthode 2 : Décomposition en facteurs premiers
• Décomposition de $60$ : $60 = 2^2 \times 3 \times 5$.
• Décomposition de $84$ : $84 = 2^2 \times 3 \times 7$.
• Les facteurs premiers communs sont $2$ et $3$.
• Pour le facteur $2$, le plus petit exposant est $2$ (on prend $2^2$).
• Pour le facteur $3$, le plus petit exposant est $1$ (on prend $3^1$).
• $PGCD(60;84) = 2^2 \times 3 = 4 \times 3 = 12$.
• Méthode 3 : Algorithme d'Euclide
• $84 = 60 \times 1 + 24$ (le reste est $24$)
• $60 = 24 \times 2 + 12$ (le reste est $12$)
• $24 = 12 \times 2 + 0$ (le reste est $0$)
Le dernier reste non nul est $12$. Donc $PGCD(60;84) = 12$.

Erreurs fréquentes
Oublier des diviseurs lors de la méthode par liste.
Prendre le plus grand exposant au lieu du plus petit pour les facteurs communs lors de la décomposition en facteurs premiers (cela mènerait au PPCM, qui est une autre notion).
Ne pas comprendre le principe de l'algorithme d'Euclide et s'arrêter trop tôt ou trop tard dans les divisions.

Décomposer un nombre entier en facteurs premiers

1. 1. Écrire le nombre à décomposer.
2. 2. Diviser le nombre par le plus petit nombre premier possible ($2$).
3. 3. Si le quotient est encore divisible par $2$, continuer à diviser par $2$.
4. 4. Quand le quotient n'est plus divisible par $2$, passer au nombre premier suivant ($3$) et répéter l'opération.
5. 5. Continuer avec les nombres premiers suivants ($5, 7, 11, \dots$) jusqu'à obtenir un quotient de $1$.
6. 6. Écrire le nombre initial comme un produit de tous les diviseurs premiers utilisés, en utilisant des puissances si un facteur apparaît plusieurs fois.

Exemple
Décomposez $180$ en facteurs premiers.

Corrigé pas à pas
Nous allons décomposer $180$ en facteurs premiers :
• $180 \div 2 = 90$
• $90 \div 2 = 45$
• $45$ n'est pas divisible par $2$. On essaie $3$.
• $45 \div 3 = 15$
• $15 \div 3 = 5$
• $5$ n'est pas divisible par $3$. On essaie $5$.
• $5 \div 5 = 1$
Donc, la décomposition en facteurs premiers de $180$ est $2 \times 2 \times 3 \times 3 \times 5 = 2^2 \times 3^2 \times 5$.

Calculer le PGCD de deux nombres avec l'algorithme d'Euclide

1. 1. Identifier le plus grand et le plus petit des deux nombres.
2. 2. Effectuer la division euclidienne du plus grand nombre par le plus petit. Noter le reste.
3. 3. Si le reste est $0$, le PGCD est le diviseur de cette étape.
4. 4. Si le reste n'est pas $0$, remplacer le plus grand nombre par le diviseur de l'étape précédente, et le plus petit nombre par le reste de l'étape précédente.
5. 5. Répéter les étapes $2$ à $4$ jusqu'à obtenir un reste de $0$.
6. 6. Le PGCD est le dernier reste non nul obtenu avant le reste $0$.

Exemple
Calculez le PGCD de $252$ et $180$.

Corrigé pas à pas
Appliquons l'algorithme d'Euclide pour trouver le PGCD de $252$ et $180$ :
• $252 = 180 \times 1 + 72$ (le reste est $72$)
• $180 = 72 \times 2 + 36$ (le reste est $36$)
• $72 = 36 \times 2 + 0$ (le reste est $0$)
Le dernier reste non nul est $36$. Donc $PGCD(252;180) = 36$.

Définitions clés

• Un nombre $a$ est divisible par $b$ si la division euclidienne de $a$ par $b$ a un reste de $0$. $b$ est un diviseur de $a$, $a$ est un multiple de $b$.
• Un nombre premier est un entier naturel qui a exactement deux diviseurs distincts : $1$ et lui-même. (Ex: $2, 3, 5, 7, \dots$)
• Le Plus Grand Commun Diviseur (PGCD) de deux nombres est le plus grand nombre qui les divise tous les deux.
• Deux nombres sont premiers entre eux si leur PGCD est $1$.

Critères de divisibilité

• Par $2$ : le nombre est pair (chiffre des unités $0, 2, 4, 6, 8$).
• Par $3$ : la somme des chiffres est divisible par $3$.
• Par $4$ : le nombre formé par les deux derniers chiffres est divisible par $4$.
• Par $5$ : le chiffre des unités est $0$ ou $5$.
• Par $9$ : la somme des chiffres est divisible par $9$.
• Par $10$ : le chiffre des unités est $0$.

Calcul du PGCD

• Par décomposition en facteurs premiers :
• 1. Décomposer les deux nombres en facteurs premiers.
• 2. Prendre le produit des facteurs premiers communs, chacun avec le plus petit de leurs exposants.
• Par l'algorithme d'Euclide :
• 1. Effectuer les divisions euclidiennes successives : $a = bq_1 + r_1$, puis $b = r_1 q_2 + r_2$, etc.
• 2. Le PGCD est le dernier reste non nul.