Les Nombres Premiers

PGCD, PPCM

Ces théories ne s'appliquent qu'aux nombres entiers positifs. Par conséquents, sur cette page nous n'utiliserons que des nombres entiers positifs.

1. Les nombres premiers
   1. Premiers nombres premiers

      Définition : un nombre premier est divisible uniquement par 1 et par lui-même.

      Les premiers nombres premiers sont donc 2, 3, 5, 7... 4 n'est pas premier car divisible aussi par 2, 6 par 2 et 3, 8 par 2...

      Nous pouvons donc imaginer un tableau ( Crible d'Ératostène 284-192 av. J.-C.) où nous allons mettre tous les nombres (par exemple les 100 premiers dans un tableau 10x10) et rayer au fur et à mesure qu'on trouve un nombre premier tous ces multiples qui ne seront pas des nombres premiers. 1 n'est bien sur pas à prendre en compte car dire qu'un nombre est multiple de 1 ne prouve pas qu'il soit premier ou non : 3 et 4 sont l'un et l'autre multiples de 1. Nous allons donc commencer à 2 et rayer tous les nombres pairs supérieurs à 2. Ensuite le premier non rayé est 3, c'est le nombre premier suivant. Nous allons donc rayer tous les multiples de 3 supérieurs à 3 non déjà rayés. Le nombre premier suivant sera 5, c'est à dire le nombre suivant non rayés et nous allons recommencer la procédure : rayer tous les multiples de 5 supérieur à 5 non déjà rayés. Le suivant sera 7, puis 11, puis 13, puis ... et chaque fois on rayera tous les multiples du nombre premier étudié supérieurs à lui même et le nombre premier suivant sera le premier non rayé...

      Pour avoir un autre exemple de tableau, choisissez la dimension de ces côtés , puis demandez le calcul en cliquant sur le bouton suivant :

      Un essai de rapidité : .

   2. Décomposition en nombre premier

      Un nombre peut se décomposer en produit de nombre(s) premier(s) comme 198=2x3x3x11. Cette décomposition est unique (à l'ordre près : 198=3x2x11x3 est aussi exact). Une méthode simple pour faire manuellement cette décomposition consiste à mettre notre nombre à gauche d'un trait et d'essayer de le diviser par le plus petit nombre premier possible par lequel il est divisible, de mettre ce nombre premier à droite du trait et le résultat de la division sous notre nombre à étudier et de recommencer avec nouveau nombre tant qu'il n'est pas égal à un. Regardez l'exemple suivant.

      198		2	Nous pouvons diviser 198 par 2
      99		3	Nous ne pouvons plus le diviser par 2, mais par trois
      33		3	Nous pouvons encore le diviser par 3
      11		11	Plus divisible par 3, ni par 5, ni par 7, mais par 11
      1			Le reste est 1, nous avons donc fini : 198=2x3x3x11

      Pour avoir un autre exemple de calcul, choisissez le nombre que vous voulez ci-contre , puis demandez le calcul en cliquant sur le bouton suivant :
   3. Programme/Algorithme

      Ceci ouvre bien sur la voie à des exercices de programmations !

      1. Mon nombre est-il premier ?

         Trouver et programmer un algorithme qui cherchera si votre nombre est premier ou non.

      2. Décomposition d'un nombre en produit de nombre premier.

         Faîtes la décomposition en nombre premier d'un nombre quelconque. Transformez ce programme en fonction que vous pourrez utiliser plus tard.

      3. Un petit coup de main

         Nombres impairs : si notre nombre n'est pas multiple de 2, alors on peut ne parcourir que les nombres impairs. Ce sera plus rapide (2 fois plus) qu'un parcours de tous les nombres et moins compliqué qu'un parcours de nombres premiers uniquement. En effet, cette dernière méthode demande de connaître/mémoriser tous les nombres premiers, ce qui est impossible car il y en a un nombre infini.

         Plus petit que la racine carrée : si le nombre qu'on cherche à décomposer n'a pas de diviseur plus petit que la racine carrée de lui-même alors, il est premier. En effet, si ce nombre A admet un diviseur B plus grand que sa racine carrée, alors il en admet un autre C=A/B plus petit que cette racine carrée tel que B.C=A . C ne peut pas être plus grand que la racine carré de A sinon B.C>A .

2. PPCM, PGCD
   1. Définitions

      PPCM : Plus Petit Commun Multiple, c'est le nombre le plus petit qui soit divisible par un ensemble de nombres donné.
      Par exemple, Le PPCM de 6 et 22 est 66. Le PPCM de 21, 6 et 14 est 42.

      PGCD : Plus Grand Commun Diviseur, c'est le plus grand nombre qui divise un ensemble de nombres donné.
      Par exemple, le PGCD de 6 et 22 est 2. Le PGCD de 21, 14 et 42 est 7.

      Nombres premiers entre eux : on dit que deux nombres sont premiers entre eux si leur PGCD est 1. C'est à dire qu'ils n'ont aucun diviseur commun en dehors de 1 (qui lui divise tous les entiers).
      Par exemple, 22 et 35 sont premiers entre eux, mais 22 et 99 ne le sont pas.

   2. Calcul à partir de la décomposition en nombre premier

      Les calculs du PPCM ainsi que celui du PGCD peuvent se faire à partir de la décomposition en nombre premier. Pour le PPCM on prend tous les nombres premiers présents dans la décomposition des nombres donnés avec leur plus grand exposant. Pour le PGCD, on prend les nombres premiers présents dans toutes les décompositions avec leurs plus petits exposants (attention aux subtilités de langage, ceux sont presque les mêmes mots, mais dans un ordre différent).

      Prenons le cas particulier du calcul de PPCM et de PGCD pour deux nombres. Si on regarde la décomposition en nombres premiers des deux nombres, le PPCM est l'union des 2 décompositions et le PGCD est l'intersection des deux compositions (remarque valable aussi dans le cas général). Ceci implique que la multiplication du PPCM et du PGCD de deux nombres est le produit de ces deux nombres : on ne prend qu'une fois ce qui est à un seul des deux (uniquement dans le PPCM) et on prend 2 fois ce qui est dans les deux (qui est dans le PPCM et le PGCD). Donc si on trouve le PGCD (ou le PPCM) de deux entiers, on peut trouver le PPCM (ou le PGCD) en multipliant entre eux les deux entiers et en divisant le tout par le PGCD (ou le PPCM] : PPCM(A,B)=AxB/PGCD(A,B).

   3. Algorithme de calcul

      Il existe un algorithme simple permettant de trouver le PGCD de deux nombres. Je vais vous aider à le trouver.

      Soit A et B deux entiers strictement positifs tel que A>B et C leur PGCD qu'on cherche.
      Par définition C divise A et B, on peut donc écrire A=aC et B=bC (a=A/C et b=B/C). De part leur définition a et b sont premiers entre eux : leur PGCD est obligatoire 1, sinon, C n'est pas le PGCD de A et B.
      Soit R le reste de la division de A par B : R=A-B.Q (1) avec R<B et Q entier (c'est la définition du reste de la division), soit r le reste de la division de a par b : r=a-b.q (2) avec r<b.
      Comme a et b sont premiers entre eux, r l'est aussi car tout diviseur commun de r et b doit alors diviser a=b.q+r. Ce diviseur est alors unique et c'est donc 1. Ceci est valable tant que r n'est pas nul ! Ce dernier cas signifierait que b=1 et q=a, sinon b serait un diviseur commun de b et a plus grand que 1 ce qui contredit a et b premier entre eux.
      Ces deux égalités (1) et (2) sont les seules vérifiant R<B, r<b, avec r, R, q et Q entiers positifs (le reste de la division est unique, on n'a qu'une possibilité pour r, R, q et Q).
      Supposons r non nul. Si on multiplie (2) par C ceci donne rC=aC-bC.q=A-B.q. Ceci donne donc rC=R et q=Q grâce à l'unicité. Donc R est divisible par C, tout comme B. r et b étant premier entre eux, R et B ne peuvent donc pas admettre de diviseur plus grand que C. Donc le PGCD de R et B est toujours C. On peut recommencer cette manoeuvre avec cette fois B à la place de A et R à la place de B. On trouverait ainsi un reste (nouveau R) plus petit que l'ancien. On vient ainsi de fabriquer une suite décroissante (les R successifs) qui sont multiples de C. Cette deviendra constante lorsque...
      Cette fois, on suppose que R=0, c'était donc que b=1, d'où C=B : on a trouvé C ! Notre suite de nombre R va donc décroittre petit à petit jusqu'à R=C puis restera constante à R=0.

      Il reste donc à mettre cette idée sous forme d'algorithme, puis de programme. On calculera ainsi le PGCD de A et B. On en déduira donc leur PPCM par la formule : PPCM(A,B)=A.B/PGCD(A,B).

      À vos crayons, puis à vos ordinateurs...

      Pour tout bien vérifier, rajoutez à ce programme la décomposition en nombre premiers faîtes précédemment afin de donner la décomposition en nombres premiers A, B, le PPCM et le PGCD.

      Pour l'exemple, calcul du PGCD et du PPCM de et , puis .
   4. Exemples d'utilisation de PPCM et PGCD.
      1. Opérations sur les fractions

         Simplification de fractions : une fraction d'entier est simplifiée quand le numérateur et le dénominateur sont premiers entre eux. Soit A et B deux entiers strictement positifs et C leur PGCD. On pose a=A/C et b=B/C.

         A	=	aC	=	a
         B		Cb		b

         Si C!=1, A/B n'est pas simplifié alors que a/b l'est.

         
         

         Addition (soustraction) de fractions. Nous partons de deux fractions simplifiées A et B ainsi que C et D sont premiers entre eux. Soit E le PPCM de B et D : E=bB=dD.

         A	+	C	=	Ab	+	Cd	=	Ab+Cd
         B		D		bB		dD		E

         Ceci donne le plus petit dénominateur possible pour le calcul, mais rien n'indique que la nouvelle fraction est irréductible. Pour le comprendre essayer avec 1/2+1/6...

      2. Trouver une période

         Soit la fonction suivante : f(x)=sin(35x)+sin(21x). Quelle est la période de cette fonction ?

         La période du premier sinus est 2.Pi/35, celle du second est 2.Pi/21 et celle du tout 2.Pi/7 car 7 est le PGCD de 21 et 35.