Utiliser les notions de multiple diviseur et de nombre premier

En mathématiques, les notions de multiple et de diviseur sont fondamentales pour comprendre les propriétés des nombres entiers.

Définition de multiple

Un nombre entier $b$ est un multiple d'un nombre entier $a$ (non nul) s'il existe un autre nombre entier $k$ tel que $b = a \times k$. Autrement dit, $b$ est dans la table de multiplication de $a$. Un nombre a une infinité de multiples.

Exemples :

• $12$ est un multiple de $3$ car $12 = 3 \times 4$. Ici, $a=3$, $b=12$, $k=4$.
• $35$ est un multiple de $7$ car $35 = 7 \times 5$.
• Les multiples de $5$ sont $0, 5, 10, 15, 20, \dots$ (on obtient chaque multiple en multipliant $5$ par un entier : $5 \times 0$, $5 \times 1$, $5 \times 2$, etc.).
• Tout nombre entier est un multiple de $1$ (car $n = 1 \times n$).
• Tout nombre entier non nul est un multiple de lui-même (car $n = n \times 1$).

Définition de diviseur

Un nombre entier $a$ (non nul) est un diviseur d'un nombre entier $b$ si la division euclidienne de $b$ par $a$ a un reste nul. Cela signifie que $b$ peut être divisé par $a$ sans laisser de reste, et le résultat est un nombre entier. Autrement dit, si $b = a \times k$, alors $a$ est un diviseur de $b$. Un nombre a un nombre fini de diviseurs.

Exemples :

• $3$ est un diviseur de $12$ car $12 \div 3 = 4$ (le reste est $0$).
• $7$ est un diviseur de $35$ car $35 \div 7 = 5$.
• Les diviseurs de $12$ sont $1, 2, 3, 4, 6, 12$.
• $1$ est un diviseur de tout nombre entier.
• Tout nombre entier non nul est un diviseur de lui-même.

Relation entre multiple et diviseur

Ces deux notions sont réciproques. Si $b$ est un multiple de $a$, alors $a$ est un diviseur de $b$. Inversement, si $a$ est un diviseur de $b$, alors $b$ est un multiple de $a$.

Exemple : Puisque $42 = 6 \times 7$:

• $42$ est un multiple de $6$.
• $42$ est un multiple de $7$.
• $6$ est un diviseur de $42$.
• $7$ est un diviseur de $42$.

Les critères de divisibilité sont des règles qui permettent de déterminer rapidement si un nombre entier est divisible par un autre sans effectuer la division complète.

Critères de divisibilité par 2, 3, 5

• Divisibilité par 2 : Un nombre est divisible par $2$ s'il est pair, c'est-à-dire si son dernier chiffre est $0, 2, 4, 6$ ou $8$.

• Divisibilité par 3 : Un nombre est divisible par $3$ si la somme de ses chiffres est un multiple de $3$.

• Divisibilité par 5 : Un nombre est divisible par $5$ si son dernier chiffre est $0$ ou $5$.

Critères de divisibilité par 4, 9, 10

• Divisibilité par 4 : Un nombre est divisible par $4$ si le nombre formé par ses deux derniers chiffres est un multiple de $4$.

• Divisibilité par 9 : Un nombre est divisible par $9$ si la somme de ses chiffres est un multiple de $9$.

• Divisibilité par 10 : Un nombre est divisible par $10$ si son dernier chiffre est $0$.

Application des critères

Ces critères peuvent être combinés pour tester la divisibilité par des nombres composés.

$138$ :

• Est-il divisible par $2$ ? Oui, car il se termine par $8$.
• Est-il divisible par $3$ ? Oui, car $1+3+8 = 12$, et $12$ est un multiple de $3$. Donc, $138$ est divisible par $6$.

Trouver tous les diviseurs d'un nombre est une compétence utile.

Méthode systématique de recherche

Pour trouver tous les diviseurs d'un nombre entier $N$:

1. Commencez par $1$. C'est toujours un diviseur.
2. Testez les nombres entiers successifs ($2, 3, 4, \dots$) pour voir s'ils divisent $N$ (sans reste).
3. Si un nombre $d$ divise $N$, alors le quotient $N/d$ est aussi un diviseur. Cela permet de trouver les diviseurs par paires.
4. Arrêtez le processus lorsque le diviseur testé $d$ dépasse $\sqrt{N}$. En effet, si $d > \sqrt{N}$, alors $N/d < \sqrt{N}$, et ce diviseur $N/d$ aurait déjà été trouvé.

• $1$ est un diviseur, $36/1 = 36$. (Paire : $1, 36$)
• $2$ est un diviseur, $36/2 = 18$. (Paire : $2, 18$)
• $3$ est un diviseur, $36/3 = 12$. (Paire : $3, 12$)
• $4$ est un diviseur, $36/4 = 9$. (Paire : $4, 9$)
• $5$ n'est pas un diviseur.
• $6$ est un diviseur, $36/6 = 6$. (Paire : $6$, qui est répété) La racine carrée de $36$ est $6$. On s'arrête là. Les diviseurs de $36$ sont : $1, 2, 3, 4, 6, 9, 12, 18, 36$.

Nombre fini de diviseurs

Comme mentionné précédemment, tout nombre entier non nul a un nombre fini de diviseurs. Cette propriété le distingue des multiples, qui sont en nombre infini.

Diviseurs triviaux

Pour tout nombre entier $N > 1$:

• $1$ est toujours un diviseur de $N$.
• $N$ est toujours un diviseur de $N$. Ces deux diviseurs sont appelés les diviseurs triviaux.

Les nombres premiers sont les "briques élémentaires" de l'arithmétique.

Définition d'un nombre premier

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

Exemples :

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

Le nombre 1 n'est pas premier

Par définition, un nombre premier doit avoir exactement deux diviseurs distincts. Le nombre $1$ n'a qu'un seul diviseur positif, qui est $1$ lui-même. Donc, $1$ n'est pas un nombre premier.

Le nombre 2 est le seul nombre pair premier

• $2$ est un nombre premier car ses diviseurs sont $1$ et $2$.
• Tous les autres nombres pairs ($4, 6, 8, \dots$) sont divisibles par $2$ (en plus de $1$ et d'eux-mêmes). Ils ont donc au moins trois diviseurs ($1, 2$, et le nombre lui-même). Par conséquent, $2$ est le seul nombre pair qui est premier.

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

Principe du crible

L'idée est d'éliminer de manière systématique les multiples des nombres premiers successifs. Ce qui reste sont les nombres premiers.

Construction du crible

Pour trouver les nombres premiers jusqu'à $N$:

1. Écrivez tous les nombres entiers de $2$ à $N$.
2. Entourez $2$, le premier nombre premier. Puis, barrez tous les multiples de $2$ (sauf $2$ lui-même).
3. Le prochain nombre non barré est $3$. Entourez $3$. Puis, barrez tous les multiples de $3$ (sauf $3$ lui-même).
4. Le prochain nombre non barré est $5$. Entourez $5$. Puis, barrez tous les multiples de $5$ (sauf $5$ lui-même).
5. Continuez ce processus avec le prochain nombre non barré. Vous pouvez vous arrêter lorsque le carré du nombre premier courant est supérieur à $N$.

Identification des nombres premiers

Les nombres qui restent non barrés à la fin du processus sont les nombres premiers.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

1. Entourer $2$. Barrer tous les multiples de $2$ : $4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30$.
2. Le prochain non barré est $3$. Entourer $3$. Barrer tous les multiples de $3$ : $6, 9, 12, 15, 18, 21, 24, 27, 30$. (Certains sont déjà barrés).
3. Le prochain non barré est $5$. Entourer $5$. Barrer tous les multiples de $5$ : $10, 15, 20, 25, 30$.
4. Le prochain non barré est $7$. Entourer $7$. Barrer tous les multiples de $7$ : $14, 21, 28$. On peut s'arrêter là car $7^2 = 49$, qui est plus grand que $30$. Les nombres premiers jusqu'à $30$ sont ceux qui sont entourés ou non barrés : $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$.

Pour déterminer si un grand nombre est premier, on utilise une méthode plus directe.

Méthode par division successive

Pour tester si un nombre entier $N$ est premier, on essaie de le diviser par tous les nombres premiers successifs ($2, 3, 5, 7, \dots$). Si $N$ est divisible par l'un de ces nombres premiers, alors $N$ n'est pas premier. Si $N$ n'est divisible par aucun de ces nombres premiers jusqu'à une certaine limite, alors $N$ est premier.

Arrêt du test à la racine carrée

La limite pour le test est $\sqrt{N}$. Si un nombre $N$ n'a pas de diviseur premier inférieur ou égal à sa racine carrée ($\sqrt{N}$), alors $N$ est premier. Pourquoi ? Si $N$ n'est pas premier, il a au moins un diviseur $d$ autre que $1$ et $N$. Si $d > \sqrt{N}$, alors $N/d$ serait un autre diviseur et $N/d < \sqrt{N}$. Donc, $N$ aurait un diviseur plus petit que $\sqrt{N}$. Il suffit donc de tester les diviseurs premiers jusqu'à $\sqrt{N}$.

Exemples de test

• Tester si $101$ est premier.

  1. Calculer $\sqrt{101} \approx 10,05$.
  2. Les nombres premiers à tester sont ceux inférieurs ou égaux à $10,05$ : $2, 3, 5, 7$.
  3. $101$ n'est pas divisible par $2$ (impair).
  4. $101$ n'est pas divisible par $3$ ($1+0+1 = 2$, pas multiple de $3$).
  5. $101$ n'est pas divisible par $5$ (ne se termine ni par $0$ ni par $5$).
  6. $101$ n'est pas divisible par $7$ ($101 = 7 \times 14 + 3$). Puisqu'aucun nombre premier inférieur ou égal à $\sqrt{101}$ ne divise $101$, alors $101$ est un nombre premier.

• Tester si $91$ est premier.

  1. Calculer $\sqrt{91} \approx 9,54$.
  2. Les nombres premiers à tester sont $2, 3, 5, 7$.
  3. $91$ n'est pas divisible par $2$.
  4. $91$ n'est pas divisible par $3$ ($9+1=10$).
  5. $91$ n'est pas divisible par $5$.
  6. $91$ est divisible par $7$ ($91 = 7 \times 13$). Donc, $91$ n'est pas un nombre premier (il est composé).

Ce théorème est l'un des piliers de la théorie des nombres.

Énoncé du théorème

Tout nombre entier naturel $N$ supérieur à $1$ peut s'écrire de manière unique comme un produit de nombres premiers. Cette écriture est appelée la décomposition en facteurs premiers ou décomposition canonique.

Exemple :

• $12 = 2 \times 2 \times 3 = 2^2 \times 3$
• $30 = 2 \times 3 \times 5$
• $100 = 2 \times 2 \times 5 \times 5 = 2^2 \times 5^2$

Unicité de la décomposition

L'ordre des facteurs n'a pas d'importance, mais les facteurs eux-mêmes et leurs exposants sont uniques pour chaque nombre. Par exemple, $2 \times 3 \times 5$ est la même décomposition que $3 \times 2 \times 5$.

Importance de la décomposition

La décomposition en facteurs premiers est un outil puissant pour résoudre de nombreux problèmes en arithmétique, notamment pour trouver des diviseurs, le PGCD et le PPCM. Chaque nombre a sa propre "empreinte digitale" unique sous forme de produit de nombres premiers.

Pour décomposer un nombre en facteurs premiers, on utilise une méthode de divisions successives.

Divisions successives par des nombres premiers

1. Commencez par le plus petit nombre premier, $2$.
2. Divisez le nombre par $2$ autant de fois que possible.
3. Passez au nombre premier suivant, $3$. Divisez le résultat par $3$ autant de fois que possible.
4. Continuez avec les nombres premiers successifs ($5, 7, 11, \dots$) jusqu'à ce que le quotient final soit $1$.

Présentation de la décomposition

On présente souvent la décomposition sous forme d'un produit avec des puissances.

Exemples de décomposition

• Décomposer $60$ :

  60 | 2
  30 | 2
  15 | 3
   5 | 5
   1 |
  

  Donc, $60 = 2 \times 2 \times 3 \times 5 = 2^2 \times 3^1 \times 5^1$.

• Décomposer $126$ :

  126 | 2
   63 | 3
   21 | 3
    7 | 7
    1 |
  

  Donc, $126 = 2 \times 3 \times 3 \times 7 = 2^1 \times 3^2 \times 7^1$.

La décomposition en facteurs premiers est très utile.

Simplification de fractions

Pour simplifier une fraction, on décompose le numérateur et le dénominateur en facteurs premiers, puis on simplifie les facteurs communs.

$60 = 2^2 \times 3 \times 5$ $126 = 2 \times 3^2 \times 7$

$\frac{60}{126} = \frac{2 \times 2 \times 3 \times 5}{2 \times 3 \times 3 \times 7} = \frac{\cancel{2} \times 2 \times \cancel{3} \times 5}{\cancel{2} \times \cancel{3} \times 3 \times 7} = \frac{2 \times 5}{3 \times 7} = \frac{10}{21}$. La fraction $\frac{10}{21}$ est irréductible car $10$ et $21$ n'ont plus de facteurs premiers en commun.

Recherche de diviseurs à partir de la décomposition

Tous les diviseurs d'un nombre peuvent être formés en prenant des combinaisons des facteurs premiers de sa décomposition, avec des exposants inférieurs ou égaux à ceux de la décomposition originale.

Les diviseurs auront la forme $2^a \times 3^b \times 5^c$ où $0 \le a \le 2$, $0 \le b \le 1$, $0 \le c \le 1$.

• $a$ peut être $0, 1, 2$ (3 choix)
• $b$ peut être $0, 1$ (2 choix)
• $c$ peut être $0, 1$ (2 choix) Combinons-les : $2^0 \times 3^0 \times 5^0 = 1$ $2^1 \times 3^0 \times 5^0 = 2$ $2^2 \times 3^0 \times 5^0 = 4$ $2^0 \times 3^1 \times 5^0 = 3$ $2^1 \times 3^1 \times 5^0 = 6$ $2^2 \times 3^1 \times 5^0 = 12$ $2^0 \times 3^0 \times 5^1 = 5$ $2^1 \times 3^0 \times 5^1 = 10$ $2^2 \times 3^0 \times 5^1 = 20$ $2^0 \times 3^1 \times 5^1 = 15$ $2^1 \times 3^1 \times 5^1 = 30$ $2^2 \times 3^1 \times 5^1 = 60$ Les diviseurs de $60$ sont : $1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$.

Calcul du nombre de diviseurs

Si la décomposition en facteurs premiers d'un nombre $N$ est $p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k}$, alors le nombre total de diviseurs de $N$ est $(a_1+1) \times (a_2+1) \times \dots \times (a_k+1)$.

Nombre de diviseurs = $(2+1) \times (1+1) \times (1+1) = 3 \times 2 \times 2 = 12$. Ce qui correspond bien à la liste trouvée ci-dessus.

Le Plus Grand Commun Diviseur (PGCD) de deux nombres est le plus grand nombre qui les divise tous les deux.

Définition du PGCD

Le PGCD de deux nombres entiers $a$ et $b$ (non nuls) est le plus grand entier positif qui est un diviseur de $a$ et un diviseur de $b$. On le note $\text{PGCD}(a, b)$.

Diviseurs communs

Pour trouver le PGCD, on cherche d'abord les diviseurs de chaque nombre, puis les diviseurs qui sont communs aux deux listes, et enfin le plus grand de ces diviseurs communs.

Méthode par énumération des diviseurs

1. Lister tous les diviseurs du premier nombre.
2. Lister tous les diviseurs du second nombre.
3. Identifier les diviseurs qui apparaissent dans les deux listes (les diviseurs communs).
4. Le plus grand de ces diviseurs communs est le PGCD.

• Diviseurs de $12$ : $1, 2, 3, 4, 6, 12$.
• Diviseurs de $18$ : $1, 2, 3, 6, 9, 18$.
• Diviseurs communs de $12$ et $18$ : $1, 2, 3, 6$.
• Le plus grand de ces diviseurs communs est $6$. Donc, $\text{PGCD}(12, 18) = 6$.

Pour les grands nombres, la méthode par liste de diviseurs est fastidieuse. L'algorithme d'Euclide est bien plus efficace.

Principe des divisions euclidiennes

L'algorithme d'Euclide est basé sur la propriété suivante : $\text{PGCD}(a, b) = \text{PGCD}(b, r)$, où $r$ est le reste de la division euclidienne de $a$ par $b$. (Avec $a > b$). On répète cette opération jusqu'à ce que le reste soit $0$.

Mise en œuvre de l'algorithme

1. Divisez le plus grand nombre par le plus petit.
2. Remplacez le plus grand nombre par le plus petit, et le plus petit nombre par le reste de la division précédente.
3. Répétez jusqu'à ce que le reste soit $0$.

Dernier reste non nul

Le dernier reste non nul est le PGCD.

• $1071 = 1029 \times 1 + 42$
• $1029 = 42 \times 24 + 21$
• $42 = 21 \times 2 + 0$ Le dernier reste non nul est $21$. Donc, $\text{PGCD}(1071, 1029) = 21$.

La décomposition en facteurs premiers offre une autre méthode pour calculer le PGCD.

Facteurs premiers communs

Pour calculer le PGCD de deux nombres $a$ et $b$ à partir de leurs décompositions en facteurs premiers :

1. Décomposez $a$ et $b$ en facteurs premiers.
2. Identifiez tous les facteurs premiers communs aux deux décompositions.

Exposants minimaux

Pour chaque facteur premier commun, prenez la puissance avec le plus petit exposant. Le PGCD est le produit de ces facteurs premiers communs avec leurs exposants minimaux.

• Décomposition de $60 = 2^2 \times 3^1 \times 5^1$.
• Décomposition de $126 = 2^1 \times 3^2 \times 7^1$.
• Facteurs premiers communs : $2$ et $3$.
• Pour le facteur $2$ : l'exposant minimal est $1$ (entre $2^2$ et $2^1$). On prend $2^1$.
• Pour le facteur $3$ : l'exposant minimal est $1$ (entre $3^1$ et $3^2$). On prend $3^1$.
• Le facteur $5$ n'est pas commun.
• Le facteur $7$ n'est pas commun. Donc, $\text{PGCD}(60, 126) = 2^1 \times 3^1 = 2 \times 3 = 6$.

Une notion importante liée au PGCD.

Définition de nombres premiers entre eux

Deux nombres entiers $a$ et $b$ sont dits premiers entre eux si leur seul diviseur commun positif est $1$. Autrement dit, ==$\text{PGCD}(a, b) = 1$==. Attention : cela ne signifie pas que $a$ et $b$ sont eux-mêmes des nombres premiers.

Exemples :

• $\text{PGCD}(7, 10) = 1$. Donc $7$ et $10$ sont premiers entre eux. ($7$ est premier, $10$ ne l'est pas).
• $\text{PGCD}(15, 8) = 1$. Donc $15$ et $8$ sont premiers entre eux. (Ni $15$ ni $8$ ne sont premiers).
• $\text{PGCD}(6, 9) = 3$. Donc $6$ et $9$ ne sont pas premiers entre eux.

PGCD égal à 1

La condition $\text{PGCD}(a, b) = 1$ est la définition même de "premiers entre eux". Si deux nombres sont premiers entre eux, on ne peut pas simplifier davantage la fraction qu'ils forment. Ex: $\frac{7}{10}$ est irréductible.

Exemples et propriétés

• Si $p$ est un nombre premier, et $a$ est un entier non multiple de $p$, alors $\text{PGCD}(p, a) = 1$.
• Si $a$ et $b$ sont premiers entre eux, et $a$ divise $bc$, alors $a$ divise $c$ (Théorème de Gauss).

Le Plus Petit Commun Multiple (PPCM) est l'inverse du PGCD en termes de logique.

Définition du PPCM

Le PPCM de deux nombres entiers $a$ et $b$ (non nuls) est le plus petit entier positif qui est un multiple de $a$ et un multiple de $b$. On le note $\text{PPCM}(a, b)$.

Multiples communs

Pour trouver le PPCM, on liste les multiples de chaque nombre, on identifie les multiples qui sont communs aux deux listes, et on prend le plus petit de ces multiples communs (différent de 0).

Méthode par énumération des multiples

1. Lister les premiers multiples du premier nombre.
2. Lister les premiers multiples du second nombre.
3. Identifier le plus petit multiple commun non nul.

• Multiples de $12$ : $0, 12, 24, 36, 48, 60, \dots$
• Multiples de $18$ : $0, 18, 36, 54, 72, \dots$
• Le plus petit multiple commun non nul est $36$. Donc, $\text{PPCM}(12, 18) = 36$.

La décomposition en facteurs premiers est la méthode la plus efficace pour calculer le PPCM de grands nombres.

Facteurs premiers communs et non communs

Pour calculer le PPCM de deux nombres $a$ et $b$ à partir de leurs décompositions en facteurs premiers :

1. Décomposez $a$ et $b$ en facteurs premiers.
2. Identifiez tous les facteurs premiers présents dans l'une ou l'autre des décompositions (communs et non communs).

Exposants maximaux

Pour chaque facteur premier identifié, prenez la puissance avec le plus grand exposant. Le PPCM est le produit de ces facteurs premiers avec leurs exposants maximaux.

• Décomposition de $60 = 2^2 \times 3^1 \times 5^1$.
• Décomposition de $126 = 2^1 \times 3^2 \times 7^1$.
• Facteurs premiers présents : $2, 3, 5, 7$.
• Pour le facteur $2$ : l'exposant maximal est $2$ (entre $2^2$ et $2^1$). On prend $2^2$.
• Pour le facteur $3$ : l'exposant maximal est $2$ (entre $3^1$ et $3^2$). On prend $3^2$.
• Pour le facteur $5$ : l'exposant maximal est $1$ (entre $5^1$ et $5^0$). On prend $5^1$.
• Pour le facteur $7$ : l'exposant maximal est $1$ (entre $7^0$ et $7^1$). On prend $7^1$. Donc, $\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$.

Il existe une relation fondamentale qui lie le PGCD et le PPCM de deux nombres.

Formule PGCD(a,b) * PPCM(a,b) = a * b

Pour deux nombres entiers positifs $a$ et $b$, la relation suivante est toujours vraie : $\text{PGCD}(a, b) \times \text{PPCM}(a, b) = a \times b$ Cette formule est très utile car si l'on connaît le PGCD (par exemple, grâce à l'algorithme d'Euclide), on peut facilement trouver le PPCM, et inversement.

Application de la formule

En utilisant la formule : $6 \times \text{PPCM}(12, 18) = 12 \times 18$ $6 \times \text{PPCM}(12, 18) = 216$ $\text{PPCM}(12, 18) = \frac{216}{6} = 36$. Ceci correspond bien au résultat trouvé par la méthode d'énumération.

Vérification avec des exemples

$6 \times 1260 = 7560$. $60 \times 126 = 7560$. La formule est vérifiée. Cette relation est un outil puissant pour vérifier les calculs ou pour trouver l'une des valeurs si l'autre est connue.