9H – NO3 – Nombres premiers, PPMC, PGDC

Posté le 04.07.2016 |


Quelques notes historiques sur les nombres premiers

C’est avec Euclide d’Alexandrie (-320? ; -260?), que les théories sur les nombres premiers se mettent en place. Dans « Les éléments » (livres VII, VIII, IX), il donne des définitions, des propriétés et démontre certaines affirmations du passé, comme l’existence d’une infinité de nombres premiers:  « Les nombres premiers sont en quantité plus grande que toute quantité proposée de nombres premiers ».

Il présente aussi la décomposition en facteurs premiers liée à la notion de PGCD.
Exemple :

  • 30 se décompose en 2 x 3 x 5 et 70 se décompose en 2 x 5 x 7. Tous les facteurs sont des nombres premiers.
  • Les diviseurs de 30 sont : 1, 2, 3, 5, 6, 10, 15 et 30
  • Les diviseurs de 70 sont : 1, 2, 5, 7, 10, 14, 35 et 70
  • Les diviseurs communs à 30 et 70 sont : 1, 2, 5 et 10. Le plus grand est 10.
  • On dit que 10 est le PGDC (Plus Grand Diviseur Commun) de 30 et 70.

Cette méthode permettant de déterminer le PGDC de deux nombres voit vite ses limites. Euclide a laissé son nom à un algorithme permettant de calculer le PGCD de deux nombres. Pour obtenir plus de détails et essayer l’algorithme d’Euclide, cliquez sur le lien en bas de page.

Un autre grec, Eratosthène de Cyrène (-276 ; -194), est l’auteur d’un célèbre crible qui permet par une méthode simple d’obtenir des nombres premiers ! Par éliminations successives des multiples des premiers nombres premiers de la liste, on obtient les suivants.

L’idée est simple.
Pour obtenir les nombres premiers inférieurs à n :

  1. Écrire tous les entiers de 2 à n,
  2. Enlever (ou barrer) les multiples de 2 sauf 2,
  3. Récupérer le plus petit nombre nom barré, c’est à dire 3, et barrer les multiples de 3 sauf 3,
  4. etc…
  5. Test d’arrêt : On s’arrête dès qu’on a atteint la racine carrée de n.
  • Voici une jolie animation du crible trouvée sur internet.
New Animation Sieve of Eratosthenes.gif
« New Animation Sieve of Eratosthenes » par M.Qrius

 

Objectifs:

  • Connaitre le vocabulaire
  • Connaître les nombres premiers inférieurs à 100
  • Connaître et savoir appliquer les critères de divisibilité (2, 3, 4, 5, 6, 9, 10, 11, 12, 15, 18, 20, 25, 50, 100)
  • Savoir « créer » un critère de divisibilité à partir des critères connus (par ex. : un nombre est divisible par 99 s’il est divisible par 9 et par 11)
  • Savoir décomposer un nombre en facteurs premiers
  • Savoir trouver le ppmc de plusieurs nombres
  • Savoir trouver le pgdc de plusieurs nombres
  • Savoir utiliser toutes les notions ci-dessus pour résoudre des problèmes

 

Théorie:

Aide-Mémoire pages 14 à 18

liste des nombres premiers jusqu’à 50000 : site

Tutoriels vidéo:

  • PGDC: vidéo 1, vidéo 2, vidéo 3
  • Déterminer le PGCD et le PPCM par décomposition: vidéo
  • vérifier si deux nombres sont premiers entre eux: vidéo
  • savoir si un nombre es divisible par 11: vidéo
  • déterminer tous les diviseurs d’un nombre par décomposition : vidéo

 

D’autres choses utiles :

  • Pour la divisibilité par un nombre composé dont on connaît la décomposition en produit de facteurs premiers n = p1k1prkr, il suffit d’appliquer la règle générale : un nombre est divisible par n si et seulement s’il est divisible par chacun des piki.
    • un nombre est divisible par 12 si et seulement s’il est divisible par 3 et par 4 (car 12 = 22 x 3 = 4 x 3)
    • un nombre est divisible par 36 si et seulement s’il est divisible par 9 et par 4 (car 36 = 22 x 32 = 4 x 9)
    • un nombre est divisible par 360 si et seulement si il est divisible par 5, 8 et 9 (car 360 = 5 x 22 x 32 = 5 x 8 x 9)
  • Critère de divisibilité par 2n : Un nombre est divisible par 2n si et seulement si ses n derniers chiffres forment un nombre divisible par 2n.
    • Un nombre est divisible par 16 = 24 si et seulement si le nombre formé par ses 4 derniers chiffres est divisible par 16.
    • Un nombre est divisible par 32 = 25 si et seulement si le nombre formé par ses 5 derniers chiffres est divisible par 32. Par exemple : 87 753 216 864 est divisible par 32 car 16 864 est divisible par 32.
  • Critère de divisibilité par 5n : Un nombre est divisible par 5n si et seulement si ses n derniers chiffres forment un nombre divisible par 5n.
    • Un nombre est divisible par 25 = 52 si et seulement si le nombre formé par ses deux derniers chiffres est divisible par 25, c’est-à-dire si son écriture « se termine » par 00, 25, 50 ou 75. Par exemple : 258 975 est divisible par 25 car il se termine par 75.
    • Un nombre est divisible par 125 = 53 si et seulement si le nombre formé par ses trois derniers chiffres est divisible par 125. Par exemple 257 543 625 est divisible par 53 = 125 car 625 est divisible par 125.
  • Critère de divisibilité par 10n : Un nombre est divisible par 10n si et seulement si ses n derniers chiffres sont égaux à 0.
    • 652 500 000 est divisible par 105 car ses 5 derniers chiffres sont des 0.
  • Le produit de deux nombres consécutifs est divisible par 2 (car parmi deux nombres consécutifs il y en a forcément un qui est pair)
  • le produit de trois nombres consécutifs est divisible par 6 (car parmi trois nombres consécutifs il y en a forcément un qui est un multiple de 3 et au moins un qui est pair).
  • Le produit de deux nombres pairs consécutifs est toujours divisible par 8.

Critères de divisibilité exotiques :

1 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
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
101 102 103 104 105 106 107 108 109 110

et aussi :

137, 271

{\displaystyle (p-1)!+1\equiv 0{\pm

Calculateurs en lignes:

 

Exercices faits en classe:

NO 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, ex. suppl. « autres critères », ex. suppl. « divers exercices ».

 

Exercices distribués en classe:

 

Exercices d’entraînement:

Exercices à faire en ligne sur multimaths.net (choisir « Parcours libre » – « nombres entiers », puis « critères de divisibilité »)

 

« Prétest »:

Voici un prétest pour vous entraîner