Les nombres premiers et la divisibilité

En mathématiques, la divisibilité est une relation entre deux nombres entiers. On dit qu'un entier $a$ est divisible par un entier $b$ (non nul) s'il existe un entier $k$ tel que $a = b \times k$.

Voici le vocabulaire essentiel :

• Si $a$ est divisible par $b$, alors $b$ est un diviseur de $a$.
• $a$ est un multiple de $b$.
• La division euclidienne (ou division entière) d'un nombre $A$ (le dividende) par un nombre $B$ (le diviseur) permet d'écrire $A = B \times Q + R$, où $Q$ est le quotient et $R$ est le reste. Le reste $R$ doit toujours être plus petit que le diviseur $B$ ($0 \le R < B$).
• Si le reste de la division euclidienne est $0$, alors $A$ est divisible par $B$.

Exemple :

• $12$ est divisible par $3$ car $12 = 3 \times 4$. Ici, $3$ est un diviseur de $12$, et $12$ est un multiple de $3$.
• La division euclidienne de $17$ par $5$ est $17 = 5 \times 3 + 2$. Le dividende est $17$, le diviseur est $5$, le quotient est $3$ et le reste est $2$. Puisque le reste n'est pas $0$, $17$ n'est pas divisible par $5$.

Les critères de divisibilité sont des règles pratiques pour savoir rapidement si un nombre est divisible par un autre sans faire la division.

• Divisibilité par 2, 5, 10 :

  • Un nombre est divisible par 2 s'il se termine par $0, 2, 4, 6, 8$ (c'est un nombre pair).
  • Un nombre est divisible par 5 s'il se termine par $0$ ou $5$.
  • Un nombre est divisible par 10 s'il se termine par $0$.
  • Exemple : $24$ est divisible par $2$. $35$ est divisible par $5$. $120$ est divisible par $2, 5$ et $10$.

• Divisibilité par 3, 9 :

  • Un nombre est divisible par 3 si la somme de ses chiffres est divisible par $3$.
  • Un nombre est divisible par 9 si la somme de ses chiffres est divisible par $9$.
  • Exemple : Pour $123$: $1+2+3=6$. Comme $6$ est divisible par $3$, $123$ est divisible par $3$. Comme $6$ n'est pas divisible par $9$, $123$ n'est pas divisible par $9$.
  • Exemple : Pour $729$: $7+2+9=18$. Comme $18$ est divisible par $3$ et par $9$, $729$ est divisible par $3$ et par $9$.

• Divisibilité par 4 :

  • Un nombre est divisible par 4 si le nombre formé par ses deux derniers chiffres est divisible par $4$.
  • Exemple : Pour $316$: les deux derniers chiffres forment $16$. Comme $16$ est divisible par $4$, $316$ est divisible par $4$.

• Divisibilité par 6 :

  • Un nombre est divisible par 6 s'il est divisible par $2$ ET par $3$.
  • Exemple : Pour $42$: il est pair (donc divisible par $2$) et $4+2=6$ (qui est divisible par $3$). Donc $42$ est divisible par $6$.

La divisibilité possède plusieurs propriétés utiles :

1. Transitivité : Si $a$ divise $b$ et $b$ divise $c$, alors $a$ divise $c$.

   • Exemple : $3$ divise $6$ (car $6 = 3 \times 2$) et $6$ divise $18$ (car $18 = 6 \times 3$). Donc, $3$ divise $18$ (car $18 = 3 \times 6$).

2. Combinaisons linéaires : Si $a$ divise $b$ et $a$ divise $c$, alors $a$ divise leur somme $(b+c)$ et leur différence $(b-c)$.

   • Exemple : $5$ divise $10$ et $5$ divise $15$. Alors $5$ divise $10+15=25$ et $5$ divise $15-10=5$.

3. Nombre fini de diviseurs : Tout nombre entier (sauf $0$) a un nombre fini de diviseurs.

   • Exemple : Les diviseurs de $12$ sont $1, 2, 3, 4, 6, 12$. Il y en a $6$.
   • Attention : un nombre a une infinité de multiples (ex: les multiples de $3$ sont $3, 6, 9, 12, \dots$).

Un nombre premier est un entier naturel qui possède exactement deux diviseurs distincts : $1$ et lui-même.

• Le nombre $1$ n'est pas un nombre premier car il n'a qu'un seul diviseur (lui-même).
• Le nombre $2$ est le seul nombre premier pair. Tous les autres nombres premiers sont impairs.

Exemples :

• $2$ est premier (diviseurs : $1, 2$).
• $3$ est premier (diviseurs : $1, 3$).
• $4$ n'est pas premier (diviseurs : $1, 2, 4$).
• $5$ est premier (diviseurs : $1, 5$).

Pour savoir si un nombre est premier, on peut utiliser la méthode par essais successifs : on essaie de le diviser par tous les nombres premiers successifs ($2, 3, 5, 7, \dots$) jusqu'à une certaine limite.

Règle d'arrêt du test : Il suffit de tester la divisibilité par les nombres premiers jusqu'à ce que le carré du diviseur testé dépasse le nombre à tester. Autrement dit, si un nombre $N$ n'est pas divisible par un nombre premier $p$ tel que $p^2 \le N$, alors $N$ est premier. On peut aussi dire qu'on arrête le test quand le diviseur $p$ devient supérieur à $\sqrt{N}$.

Exemple : Tester si $101$ est premier.

1. $\sqrt{101} \approx 10,05$. Il faut tester les nombres premiers jusqu'à $7$.
2. $101$ n'est pas divisible par $2$ (il est impair).
3. $101$ n'est pas divisible par $3$ ($1+0+1=2$, non divisible par $3$).
4. $101$ n'est pas divisible par $5$ (ne se termine ni par $0$ ni par $5$).
5. $101 \div 7 = 14$ avec un reste de $3$. Donc $101$ n'est pas divisible par $7$. Puisque $101$ n'est divisible par aucun des nombres premiers $2, 3, 5, 7$, alors $101$ est un nombre premier.

Les premiers nombres premiers sont : $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, \dots$

Le crible d'Ératosthène est une méthode ancienne pour trouver tous les nombres premiers jusqu'à une certaine limite. Le principe est simple :

1. Écrire tous les nombres d'une liste.
2. Barrer $1$.
3. Entourer $2$ (premier), puis barrer tous les multiples de $2$.
4. Entourer le premier nombre non barré suivant ($3$), puis barrer tous ses multiples.
5. Répéter l'opération jusqu'à la fin de la liste. Les nombres entourés sont les nombres premiers.

Il existe une infinité de nombres premiers. Ce fait a été prouvé par le mathématicien Euclide il y a plus de 2000 ans.

Le théorème fondamental de l'arithmétique stipule que tout nombre entier naturel supérieur à $1$ peut s'écrire comme un produit de nombres premiers d'une manière unique (à l'ordre des facteurs près). C'est la décomposition en facteurs premiers.

• Chaque nombre du produit est un facteur premier.
• L'unicité de la décomposition est essentielle : pour un nombre donné, il n'y a qu'une seule façon de l'écrire comme produit de nombres premiers.

Exemple :

• $12 = 2 \times 2 \times 3 = 2^2 \times 3$. Les facteurs premiers sont $2$ et $3$.
• $30 = 2 \times 3 \times 5$.

La méthode de l'arbre de facteurs est une façon visuelle de réaliser cette décomposition.

Pour décomposer un nombre en facteurs premiers, on le divise successivement par les plus petits nombres premiers possibles, dans l'ordre ($2, 3, 5, 7, \dots$).

1. On écrit le nombre à décomposer.
2. On essaie de le diviser par $2$. Si c'est possible, on écrit le quotient et on continue avec $2$.
3. Si ce n'est plus divisible par $2$, on essaie par $3$.
4. Et ainsi de suite avec $5, 7, 11, \dots$ jusqu'à obtenir un quotient de $1$.

La présentation en puissance consiste à regrouper les facteurs premiers identiques à l'aide d'exposants.

Exemples de décomposition :

La décomposition en facteurs premiers est un outil puissant pour :

• Trouver tous les diviseurs d'un nombre : Pour trouver tous les diviseurs d'un nombre, on forme tous les produits possibles des facteurs premiers de sa décomposition.

  • Exemple : $12 = 2^2 \times 3^1$. Les diviseurs sont de la forme $2^a \times 3^b$ où $0 \le a \le 2$ et $0 \le b \le 1$.
    • $a=0, b=0 \Rightarrow 2^0 \times 3^0 = 1$
    • $a=1, b=0 \Rightarrow 2^1 \times 3^0 = 2$
    • $a=2, b=0 \Rightarrow 2^2 \times 3^0 = 4$
    • $a=0, b=1 \Rightarrow 2^0 \times 3^1 = 3$
    • $a=1, b=1 \Rightarrow 2^1 \times 3^1 = 6$
    • $a=2, b=1 \Rightarrow 2^2 \times 3^1 = 12$ Les diviseurs de $12$ sont $1, 2, 3, 4, 6, 12$.

• Simplifier des fractions : Elle permet de trouver le plus grand diviseur commun aux numérateur et dénominateur pour rendre une fraction irréductible.

• Calculer le PGCD et le PPCM : C'est la méthode la plus efficace pour trouver le Plus Grand Commun Diviseur (PGCD) et le Plus Petit Commun Multiple (PPCM) de plusieurs nombres.

Le Plus Grand Commun Diviseur (PGCD) de deux ou plusieurs nombres entiers est le plus grand nombre entier qui divise chacun de ces nombres sans laisser de reste. On le note $\text{PGCD}(a, b)$.

Méthodes pour calculer le PGCD :

1. Par liste des diviseurs (pour petits nombres) :

   • Lister tous les diviseurs de chaque nombre.
   • Identifier les diviseurs communs.
   • Prendre le plus grand d'entre eux.
   • Exemple : $\text{PGCD}(12, 18)$
     • Diviseurs de $12$: $1, 2, 3, 4, 6, 12$.
     • Diviseurs de $18$: $1, 2, 3, 6, 9, 18$.
     • Diviseurs communs : $1, 2, 3, 6$.
     • Le plus grand est $6$. Donc $\text{PGCD}(12, 18) = 6$.

2. Par décomposition en facteurs premiers (méthode la plus efficace) :

   • Décomposer chaque nombre en facteurs premiers.
   • Prendre les facteurs premiers communs à toutes les décompositions, chacun affecté de son plus petit exposant.
   • Exemple : $\text{PGCD}(60, 126)$
     • $60 = 2^2 \times 3^1 \times 5^1$
     • $126 = 2^1 \times 3^2 \times 7^1$
     • Facteurs premiers communs : $2$ et $3$.
     • Plus petit exposant pour $2$ est $1$ (dans $2^1$).
     • Plus petit exposant pour $3$ est $1$ (dans $3^1$).
     • $\text{PGCD}(60, 126) = 2^1 \times 3^1 = 6$.

Le Plus Petit Commun Multiple (PPCM) de deux ou plusieurs nombres entiers est le plus petit nombre entier positif qui est un multiple de chacun de ces nombres. On le note $\text{PPCM}(a, b)$.

Méthodes pour calculer le PPCM :

1. Par liste des multiples (pour petits nombres) :

   • Lister les premiers multiples de chaque nombre.
   • Le premier multiple commun trouvé est le PPCM.
   • Exemple : $\text{PPCM}(4, 6)$
     • Multiples de $4$: $4, 8, 12, 16, 20, \dots$
     • Multiples de $6$: $6, 12, 18, 24, \dots$
     • Le plus petit multiple commun est $12$. Donc $\text{PPCM}(4, 6) = 12$.

2. Par décomposition en facteurs premiers (méthode la plus efficace) :

   • Décomposer chaque nombre en facteurs premiers.
   • Prendre tous les facteurs premiers présents dans les décompositions (communs ou non), chacun affecté de son plus grand exposant.
   • Exemple : $\text{PPCM}(60, 126)$
     • $60 = 2^2 \times 3^1 \times 5^1$
     • $126 = 2^1 \times 3^2 \times 7^1$
     • Facteurs premiers présents : $2, 3, 5, 7$.
     • Plus grand exposant pour $2$ est $2$ (dans $2^2$).
     • Plus grand exposant pour $3$ est $2$ (dans $3^2$).
     • Plus grand exposant pour $5$ est $1$ (dans $5^1$).
     • Plus grand exposant pour $7$ est $1$ (dans $7^1$).
     • $\text{PPCM}(60, 126) = 2^2 \times 3^2 \times 5^1 \times 7^1 = 4 \times 9 \times 5 \times 7 = 36 \times 35 = 1260$.

• Rendre une fraction irréductible (simplification) : Pour simplifier une fraction $\frac{A}{B}$ et la rendre irréductible, il suffit de diviser le numérateur et le dénominateur par leur PGCD.

  • Exemple : Simplifier $\frac{60}{126}$. On a trouvé $\text{PGCD}(60, 126) = 6$. $\frac{60}{126} = \frac{60 \div 6}{126 \div 6} = \frac{10}{21}$.

• Réduire des fractions au même dénominateur : Pour additionner ou soustraire des fractions avec des dénominateurs différents, on les réduit au même dénominateur, qui est souvent le PPCM des dénominateurs.

  • Exemple : Calculer $\frac{1}{4} + \frac{1}{6}$. On a trouvé $\text{PPCM}(4, 6) = 12$. $\frac{1}{4} + \frac{1}{6} = \frac{1 \times 3}{4 \times 3} + \frac{1 \times 2}{6 \times 2} = \frac{3}{12} + \frac{2}{12} = \frac{5}{12}$.

• Résolution de problèmes concrets : Le PGCD et le PPCM sont très utilisés pour résoudre des problèmes de partage équitable, de regroupement ou de cycles.

  • Problème PGCD : On a $60$ billes rouges et $126$ billes bleues. On veut faire des paquets identiques contenant le même nombre de billes rouges et le même nombre de billes bleues, en utilisant toutes les billes. Quel est le nombre maximal de paquets que l'on peut faire ? La réponse est $\text{PGCD}(60, 126) = 6$. On pourra faire $6$ paquets de $10$ billes rouges et $21$ billes bleues.
  • Problème PPCM : Deux bus partent de la même station à $8h00$. Le bus A passe toutes les $4$ minutes et le bus B toutes les $6$ minutes. À quelle heure repartiront-ils ensemble pour la première fois ? La réponse est $\text{PPCM}(4, 6) = 12$. Ils repartiront ensemble $12$ minutes après $8h00$, soit à $8h12$.