La divisibilité et les nombres premiers

La divisibilité est une notion fondamentale en arithmétique. Elle décrit la relation entre deux nombres entiers lorsqu'un nombre peut être divisé par un autre sans laisser de reste.

Vocabulaire clé :

• Diviseur : Un nombre entier $d$ est un diviseur d'un autre nombre entier $n$ si la division de $n$ par $d$ donne un reste de zéro. On dit alors que $n$ est divisible par $d$.
• Multiple : Un nombre entier $n$ est un multiple d'un nombre entier $d$ si $n$ peut s'écrire sous la forme $n = k \times d$, où $k$ est un entier. Si $d$ est un diviseur de $n$, alors $n$ est un multiple de $d$.
• Dividende, diviseur, quotient, reste : Dans une division euclidienne de $a$ par $b$, on écrit $a = b \times q + r$, où $a$ est le dividende, $b$ est le diviseur, $q$ est le quotient et $r$ est le reste. Le reste $r$ doit toujours vérifier $0 \le r < b$.

Relation entre division euclidienne et divisibilité : Un nombre $a$ est divisible par un nombre $b$ (non nul) si et seulement si le reste de la division euclidienne de $a$ par $b$ est égal à 0. Exemple : La division de 12 par 3 est $12 = 3 \times 4 + 0$. Le reste est 0, donc 12 est divisible par 3. 3 est un diviseur de 12. 12 est un multiple de 3.

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

• Divisibilité par 2, 5, 10 :
  • Un nombre est divisible par 2 si son dernier chiffre est 0, 2, 4, 6 ou 8 (il est pair).
  • Un nombre est divisible par 5 si son dernier chiffre est 0 ou 5.
  • Un nombre est divisible par 10 si son dernier chiffre est 0.
• 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, la somme des chiffres est $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.
• Divisibilité par 4 : Un nombre est divisible par 4 si le nombre formé par ses deux derniers chiffres est divisible par 4. Exemple : 316 est divisible par 4 car 16 est divisible par 4 ($16 = 4 \times 4$).
• Divisibilité par 6 : Un nombre est divisible par 6 s'il est divisible à la fois par 2 ET par 3. Exemple : 48 est divisible par 2 (il est pair) et la somme de ses chiffres ($4+8=12$) est divisible par 3. Donc 48 est divisible par 6.

La divisibilité possède plusieurs propriétés utiles pour la résolution de problèmes. Soient $a$, $b$, $c$ des entiers.

• Si $a$ divise $b$ et $b$ divise $c$, alors $a$ divise $c$. C'est la propriété de transitivité. Exemple : Si 3 divise 6 ($6 = 2 \times 3$) et 6 divise 18 ($18 = 3 \times 6$), alors 3 divise 18 ($18 = 6 \times 3$).
• Si $a$ divise $b$ et $a$ divise $c$, alors $a$ divise $(b+c)$. Exemple : Si 5 divise 10 et 5 divise 15, alors 5 divise $(10+15)$, c'est-à-dire 25. En effet $10=5 \times 2$ et $15=5 \times 3$, donc $10+15 = 5 \times 2 + 5 \times 3 = 5 \times (2+3) = 5 \times 5 = 25$.
• Si $a$ divise $b$ et $a$ divise $c$, alors $a$ divise $(b-c)$. Exemple : Si 5 divise 15 et 5 divise 10, alors 5 divise $(15-10)$, c'est-à-dire 5.
• Si $a$ divise $b$, alors $a$ divise $kb$ (où $k$ est un entier). Si un nombre $a$ divise un nombre $b$, alors $a$ divise n'importe quel multiple de $b$. Exemple : Si 7 divise 14, alors 7 divise $14 \times 3 = 42$.

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

• Deux diviseurs exacts, 1 et lui-même : Cette condition est essentielle.
• Le cas particulier de 1 : Le nombre 1 n'est PAS un nombre premier car il n'a qu'un seul diviseur (lui-même).
• Exemples de nombres premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, ... Le nombre 2 est le seul nombre premier pair.

Pour vérifier si un nombre $N$ est premier, on utilise la méthode des essais successifs de division.

• Méthode par essais successifs de division : On essaie de diviser $N$ par tous les nombres premiers successifs ($2, 3, 5, 7, ...$) jusqu'à une certaine limite.
• Arrêt des essais à la racine carrée : Il suffit de tester les diviseurs premiers jusqu'à la racine carrée du nombre $N$. Si $N$ n'a pas de diviseur premier inférieur ou égal à $\sqrt{N}$, alors $N$ est premier. Pourquoi ? Si $N$ avait un diviseur $d > \sqrt{N}$, alors il aurait aussi un diviseur $N/d < \sqrt{N}$. Donc, si on n'a trouvé aucun diviseur jusqu'à $\sqrt{N}$, c'est qu'il n'y en a pas. Exemple : Pour savoir si 101 est premier, on calcule $\sqrt{101} \approx 10,05$. On teste les nombres premiers inférieurs à 10,05 : 2, 3, 5, 7.
  • 101 n'est pas divisible par 2 (impair).
  • $1+0+1=2$, 101 n'est pas divisible par 3.
  • Le dernier chiffre n'est pas 0 ou 5, 101 n'est pas divisible par 5.
  • $101 = 7 \times 14 + 3$, 101 n'est pas divisible par 7. Donc, 101 est un nombre premier.
• Utilisation des critères de divisibilité : Avant de commencer les divisions, on peut rapidement éliminer les diviseurs 2, 3, 5 grâce aux critères.
• Liste des premiers nombres premiers : Il est utile de connaître par cœur les premiers nombres premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

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

• Principe du crible :
  1. Écrire tous les nombres entiers de 2 jusqu'à la limite souhaitée.
  2. Le premier nombre non barré (2) est premier. Barrer tous ses multiples (4, 6, 8, ...).
  3. Passer au nombre non barré suivant (3). Il est premier. Barrer tous ses multiples (6, 9, 12, ...).
  4. Continuer ce processus jusqu'à ce que tous les nombres soient barrés ou identifiés comme premiers.
• Application pour trouver les nombres premiers : Cette méthode est très visuelle pour comprendre comment les nombres premiers sont "filtrés" des nombres composés. Exemple : Pour trouver les nombres premiers jusqu'à 20 : 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
  1. 2 est premier. Barrer les multiples de 2 : 4, 6, 8, 10, 12, 14, 16, 18, 20.
  2. 3 est premier. Barrer les multiples de 3 : 6 (déjà barré), 9, 12 (déjà barré), 15, 18 (déjà barré).
  3. 5 est premier. Barrer les multiples de 5 : 10 (déjà barré), 15 (déjà barré), 20 (déjà barré).
  4. 7 est premier. Barrer les multiples de 7 : 14 (déjà barré). Les nombres restants sont premiers : 2, 3, 5, 7, 11, 13, 17, 19.
• Efficacité de la méthode : Très efficace pour les petites limites.
• Limites du crible : Devient très lourd pour trouver de très grands nombres premiers.

La décomposition en facteurs premiers est une notion essentielle en arithmétique.

• Tout nombre entier peut être décomposé : Tout nombre entier supérieur à 1 peut s'écrire comme un produit de nombres premiers.
• Produit de facteurs premiers : Par exemple, $12 = 2 \times 2 \times 3 = 2^2 \times 3$. Ici, 2 et 3 sont les facteurs premiers de 12.
• Unicité de la décomposition : Le Théorème fondamental de l'arithmétique stipule que cette décomposition est unique à l'ordre des facteurs près. Chaque nombre a une seule "empreinte digitale" de nombres premiers.
• Exemples simples :
  • $6 = 2 \times 3$
  • $10 = 2 \times 5$
  • $30 = 2 \times 3 \times 5$
  • $100 = 2 \times 2 \times 5 \times 5 = 2^2 \times 5^2$

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

• Division par les plus petits nombres premiers : On commence par essayer de diviser le nombre par le plus petit nombre premier (2), puis par le suivant (3), puis (5), et ainsi de suite, jusqu'à obtenir un quotient de 1.

• Présentation en colonne : C'est une méthode visuelle très pratique.

  Nombre | Facteur premier
  -------|----------------
  120    | 2
  60     | 2
  30     | 2
  15     | 3
  5      | 5
  1      |
  

  Ainsi, $120 = 2 \times 2 \times 2 \times 3 \times 5 = 2^3 \times 3 \times 5$.

• Exemples de décomposition :

  • Décomposer 72 :

    72 | 2
    36 | 2
    18 | 2
    9  | 3
    3  | 3
    1  |
    

    Donc $72 = 2^3 \times 3^2$.

• Vérification du résultat : Pour vérifier, il suffit de multiplier les facteurs premiers entre eux pour retrouver le nombre initial.

La décomposition en facteurs premiers est un outil puissant avec de nombreuses applications.

• Simplification de fractions : Pour simplifier une fraction $\frac{a}{b}$, on décompose $a$ et $b$ en facteurs premiers, puis on élimine les facteurs communs au numérateur et au dénominateur. Exemple : Simplifier $\frac{120}{72}$. $120 = 2^3 \times 3 \times 5$ $72 = 2^3 \times 3^2$ $\frac{120}{72} = \frac{2^3 \times 3 \times 5}{2^3 \times 3^2} = \frac{5}{3}$
• Calcul du PGCD (Plus Grand Commun Diviseur) : Le PGCD de deux nombres est le produit des facteurs premiers communs, affectés de leur plus petite puissance.
• Calcul du PPCM (Plus Petit Commun Multiple) : Le PPCM de deux nombres est le produit de tous les facteurs premiers (communs ou non), affectés de leur plus grande puissance.
• Recherche de diviseurs d'un nombre : Si $N = p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k}$, alors tout diviseur de $N$ s'écrit $d = p_1^{b_1} \times p_2^{b_2} \times ... \times p_k^{b_k}$ avec $0 \le b_i \le a_i$. Le nombre total de diviseurs est $(a_1+1)(a_2+1)...(a_k+1)$. Exemple : Pour $12 = 2^2 \times 3^1$. Le nombre de diviseurs est $(2+1)(1+1) = 3 \times 2 = 6$. Les diviseurs de 12 sont : $2^0 \times 3^0 = 1$, $2^1 \times 3^0 = 2$, $2^2 \times 3^0 = 4$, $2^0 \times 3^1 = 3$, $2^1 \times 3^1 = 6$, $2^2 \times 3^1 = 12$.

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

• Définition du PGCD : Le PGCD de $a$ et $b$, noté PGCD($a$, $b$), est le plus grand diviseur commun à $a$ et $b$.
• Méthode par liste des diviseurs :
  1. Lister tous les diviseurs de chaque nombre.
  2. Identifier les diviseurs communs.
  3. Choisir le plus grand parmi les diviseurs communs. Exemple : 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 PGCD(12, 18) = 6. Cette méthode est longue pour de grands nombres.
• Méthode par décomposition en facteurs premiers :
  1. Décomposer chaque nombre en facteurs premiers.
  2. Prendre les facteurs premiers communs, chacun avec sa plus petite puissance.
  3. Multiplier ces facteurs. Exemple : PGCD(120, 72) $120 = 2^3 \times 3^1 \times 5^1$ $72 = 2^3 \times 3^2$ Facteurs communs : $2^3$ et $3^1$. PGCD(120, 72) = $2^3 \times 3^1 = 8 \times 3 = 24$.
• Algorithme d'Euclide (introduction) : C'est une méthode plus rapide, basée sur les divisions euclidiennes successives. Le PGCD est le dernier reste non nul. Exemple : PGCD(120, 72) $120 = 1 \times 72 + 48$ $72 = 1 \times 48 + 24$ $48 = 2 \times 24 + 0$ Le dernier reste non nul est 24. Donc PGCD(120, 72) = 24.

Le Plus Petit Commun Multiple (PPCM) de deux ou plusieurs nombres entiers est le plus petit nombre entier positif qui est un multiple de tous ces nombres.

• Définition du PPCM : Le PPCM de $a$ et $b$, noté PPCM($a$, $b$), est le plus petit multiple commun positif de $a$ et $b$.
• Méthode par liste des multiples :
  1. Lister les premiers multiples de chaque nombre.
  2. Identifier le plus petit multiple commun. Exemple : PPCM(12, 18) Multiples de 12 : {12, 24, 36, 48, 60, ...} Multiples de 18 : {18, 36, 54, 72, ...} Le plus petit multiple commun est 36. Donc PPCM(12, 18) = 36. Cette méthode est longue pour de grands nombres.
• Méthode par décomposition en facteurs premiers :
  1. Décomposer chaque nombre en facteurs premiers.
  2. Prendre tous les facteurs premiers (communs ou non), chacun avec sa plus grande puissance.
  3. Multiplier ces facteurs. Exemple : PPCM(120, 72) $120 = 2^3 \times 3^1 \times 5^1$ $72 = 2^3 \times 3^2$ Facteurs avec la plus grande puissance : $2^3$, $3^2$, $5^1$. PPCM(120, 72) = $2^3 \times 3^2 \times 5^1 = 8 \times 9 \times 5 = 360$.
• Relation PGCD x PPCM = a x b : Pour deux nombres $a$ et $b$, on a la propriété fondamentale : PGCD($a$, $b$) $\times$ PPCM($a$, $b$) = $a \times b$. Cette relation permet de calculer l'un si l'autre est connu. Exemple : PGCD(120, 72) = 24. PPCM(120, 72) = $\frac{120 \times 72}{24} = \frac{8640}{24} = 360$.

Deux nombres entiers sont dits premiers entre eux si leur seul diviseur commun positif est 1.

• Définition (PGCD = 1) : Deux nombres $a$ et $b$ sont premiers entre eux si et seulement si leur PGCD est égal à 1. ==PGCD($a$, $b$) = 1==.
• Exemples de nombres premiers entre eux :
  • PGCD(7, 10) = 1. (7 est premier, 10 ne l'est pas, mais ils sont premiers entre eux.)
  • PGCD(15, 22) = 1.
  • Attention : des nombres premiers entre eux ne sont pas forcément eux-mêmes des nombres premiers.
• Propriétés :
  • Si $a$ et $b$ sont premiers entre eux, alors PPCM($a$, $b$) = $a \times b$.
  • Si un nombre premier $p$ ne divise pas $a$, alors $p$ et $a$ sont premiers entre eux.
• Application à la simplification de fractions : Une fraction $\frac{a}{b}$ est irréductible (simplifiée au maximum) si et seulement si $a$ et $b$ sont premiers entre eux. Pour rendre une fraction irréductible, il faut diviser le numérateur et le dénominateur par leur PGCD. Exemple : La fraction $\frac{5}{3}$ est irréductible car PGCD(5, 3) = 1.

Le PGCD est utilisé pour résoudre des problèmes où l'on cherche à partager, grouper ou découper des éléments en parts égales, les plus grandes possibles.

• Partage équitable : Distribuer un nombre maximum de lots identiques. Exemple : On dispose de 42 billes rouges et 70 billes bleues. On veut faire le plus grand nombre de paquets identiques, contenant chacun le même nombre de billes rouges et le même nombre de billes bleues. On cherche PGCD(42, 70). $42 = 2 \times 3 \times 7$ $70 = 2 \times 5 \times 7$ PGCD(42, 70) = $2 \times 7 = 14$. On pourra faire 14 paquets. Chaque paquet contiendra $42/14 = 3$ billes rouges et $70/14 = 5$ billes bleues.
• Groupes identiques : Former des groupes ayant la même composition.
• Carrelage, découpe : Découper en carrés de côté maximal, sans perte. Exemple : Une pièce rectangulaire de 4,20 m par 5,40 m doit être carrelée avec des dalles carrées de même dimension, les plus grandes possibles, sans coupe. On convertit en cm : 420 cm et 540 cm. On cherche PGCD(420, 540). $420 = 2^2 \times 3 \times 5 \times 7$ $540 = 2^2 \times 3^3 \times 5$ PGCD(420, 540) = $2^2 \times 3 \times 5 = 4 \times 3 \times 5 = 60$. Les dalles auront un côté de 60 cm.
• Optimisation : Trouver la plus grande mesure commune.

Le PPCM est utilisé pour résoudre des problèmes où l'on cherche à trouver le moment où des événements périodiques se reproduisent simultanément, ou la plus petite quantité commune.

• Rendez-vous périodiques, Synchronisation : Trouver quand plusieurs événements qui se répètent à des intervalles différents se produiront en même temps. Exemple : Un bus A passe toutes les 12 minutes, un bus B passe toutes les 18 minutes. Ils partent ensemble à 8h00. Quand repartiront-ils ensemble ? On cherche PPCM(12, 18). $12 = 2^2 \times 3$ $18 = 2 \times 3^2$ PPCM(12, 18) = $2^2 \times 3^2 = 4 \times 9 = 36$. Les bus repartiront ensemble 36 minutes après 8h00, soit à 8h36.
• Multiples communs : Calculer la plus petite quantité commune nécessaire.
• Calcul de fréquences : Déterminer la fréquence de coïncidence de cycles.

• Choix de la bonne méthode :
  • PGCD : Problèmes de partage, découpe, recherche du "plus grand commun".
  • PPCM : Problèmes de cycles, rendez-vous, recherche du "plus petit commun" (temps ou quantité).
• Interprétation des résultats : S'assurer que le résultat a du sens dans le contexte du problème.
• Erreurs courantes :
  • Confondre PGCD et PPCM.
  • Oublier de vérifier si un nombre est premier lors de la décomposition.
  • Erreurs de calcul avec les puissances dans les décompositions.
• Exercices de synthèse : Pratiquer régulièrement pour maîtriser ces concepts et leurs applications. La clé est de bien identifier si le problème demande un PGCD ou un PPCM.