Division euclidienne – Nombres premiers – PGCD

Écriture en ligne :

$ 299 $ est le quotient et $ 17 $ le reste.

La division euclidienne de $ 630 $ par $ 15 $ donne un quotient de $ 42 $ et un reste nul.

On a donc $ 630 = 15\times 42 $.

On peut dire que :

• $ 630 $ est divisible par $ 15 $
• $ 630 $ est un multiple de $ 15 $
• $ 15 $ est un diviseur de $ 630 $
• $ 15 $ divise $ 630 $

(On peut aussi dire que $ 630 $ est divisible par $ 42 $, etc.)

• $ 1314 $ est divisible par $ 2 $ (chiffre des unités : 4)
• $ 1314 $ est divisible par $ 3 $ (somme des chiffres : 9)
• $ 1314 $ n'est pas divisible par $ 4 $ (deux derniers chiffres : 14)
• $ 1314 $ n'est pas divisible par $ 5 $ (chiffre des unités : 4)
• $ 1314 $ est divisible par $ 9 $ (somme des chiffres : 9)
• $ 1314 $ n'est pas divisible par $ 10 $ (chiffre des unités : 4)

• 2 ; 3 ; 5 sont des nombres premiers ;
• 0 n'est pas un nombre premier car il est divisible par tous les entiers supérieurs ou égal à 1.
• 1 n'est pas un nombre premier car il n'admet qu' un seul diviseur (lui-même).
• À l'exception du nombre 2, tous les entiers pairs ne sont pas des nombres premiers (car ils sont divisibles par 2). Cela signifie qu'à l'exception du nombre 2, tous les nombres premiers sont impairs. Par contre, la réciproque est fausse : tous les nombres impairs ne sont pas premiers ; par exemple 1 (voir ci-dessus) et 15 (divisible par 1 ; 3 ; 5 et 15) ne sont pas premiers.

• $ 10 = 2 \times 5 $
• $ 84 = 2 \times 2 \times 3 \times 7 = 2^2 \times 3 \times 7 $
• $ 23 = 23 $ (un seul facteur car 23 est premier !)

Soit à déterminer le PGCD de $ 600 $ et $ 315 $.

Les diviseurs de $ 600 $ sont :

$ 1; 2; 3; 4; 5; 6; 8; 10; 12; 15; 20; 24; 25; 30; 40; 50; 60; 75; 100; 120; 150; 200; 300; 600 $

Les diviseurs de $ 315 $ sont :

$ 1; 3; 5; 7; 9; 15; 21; 35; 45; 63; 105; 315 $

Le plus grand diviseur commun est donc $ 15 $ (le plus grand nombre figurant à la fois dans les deux listes).

$ PGCD\left(600~; 315\right)=15 $.

Il existe plusieurs méthodes permettant de trouver le PGCD de deux nombres de façon plus rapide, sans avoir besoin de faire la liste de tous les diviseurs.

En classe de Troisième, il faut connaître la méthode utilisant la décomposition en facteurs premiers (voir ci-dessous).

Par ailleurs, de nombreuses calculatrices (de niveau collège ou lycée) possède une touche permettant de calculer le PGCD de deux entiers naturels.

Calcul du PGCD à l'aide de décomposition en produit de facteurs premiers

• Exemple 1 : Calcul du PGCD de 45 et de 150 :

  Les décompositions en facteurs premiers de 45 et de 150 sont :

  $ 45 = {\color{red} 3 } \times 3 \times {\color{red} 5} = 3^2 \times 5 $

  $ 150 = 2 \times {\color{red} 3} \times {\color{red} 5} \times 5 = 2 \times 3 \times 5^2 $

  $ 3 $ et $ 5 $ sont les facteurs premiers figurant dans les deux décompositions donc le PGCD de $ 45 $ et de $ 150 $ est $ 3 \times 5 = 15. $

• Exemple 2 : Calcul du PGCD de 108 et de 144 :

  Les décompositions en produit de facteurs premiers de 108 et de 144 sont :

  $ 108 = {\color{red} 2 \times 2} \times {\color{red} 3 \times 3} \times 3 = 2^2 \times 3^3 $

  $ 144 = {\color{red} 2 \times 2} \times 2 \times 2 \times {\color{red} 3 \times 3} = 2^4 \times 3^2 $

  Le facteur $ 2 $ est présent (au moins) deux fois dans chacune des décompositions ainsi que le facteur $ 3 $ ; donc le PGCD de $ 108 $ et de $ 144 $ est $ 2 \times 2 \times 3 \times 3 = 36. $

• $ \dfrac{5}{6} $ est une fraction irréductible car $ PGCD\left(5~; 6\right)=1 $.

• $ \dfrac{121}{99} $ n'est pas une fraction irréductible car $ PGCD\left(121~; 99\right)=11 $.
  La fraction se simplifie donc par $ 11 $ :

  $ \dfrac{121}{99}=\dfrac{11\times 11}{9\times 11}=\dfrac{11}{9} $

Déterminons le PPCM de $ 8 $ et de $ 12 $.

• Multiples de $ 8 $ : $ 8, 16, 24, 32, 40, 48, \ldots $
• Multiples de $ 12 $ : $ 12, 24, 36, 48, \ldots $

Le plus petit multiple commun est $ 24 $, donc $ PPCM\left(8~; 12\right)=24 $.

Calcul du PPCM de $ 45 $ et de $ 150 $.

On décompose : $ 45 = 3^{2}\times 5 $ et $ 150 = 2\times 3\times 5^{2} $.

On prend chaque facteur premier avec son plus grand exposant :
$ PPCM\left(45~; 150\right)=2\times 3^{2}\times 5^{2}=2\times 9\times 25=450 $.