Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

Division euclidienne - Nombres premiers - PGCD

1 - Division euclidienne

Définition

Soient aa et bb, deux nombres entiers naturels (c'est à dire positifs) avec b0b\neq 0.

Effectuer la division euclidienne de aa par bb, c'est trouver deux entiers naturels qq et rr tels que :

a=b×q+ra = b\times q+r et r<b r < b

qq s'appelle le quotient et rr le reste.

Exemple

division euclidienne

Écriture en ligne :

6894=23×299+176894 = 23\times 299 + 17

299299 est le quotient et 1717 le reste.

Remarque

Sur la plupart des calculatrices de collège la touche qui permet d'effectuer la division euclidienne est notée : touche division euclidienne .

Par exemple, la suite de touches à entrer pour obtenir la division euclidienne de 68946894 par 2323 sur une TI-Collège est :

suite de touches division euclidienne

et voici le résultat obtenu à l'écran :

resultat division euclidienne

Définition

On dit que aa est divisible par bb si le reste de la division euclidienne de aa par bb est nul.

Cela revient à dire qu'il existe un entier naturel qq tel que a=b×qa = b\times q.

Les expressions suivantes sont synonymes :

  • aa est divisible par bb

  • aa est un multiple de bb

  • bb est un diviseur de aa

  • bb divise aa (que l'on écrit parfois bab | a)

Exemple

La division euclidienne de 630630 par 1515 donne un quotient de 4242 et un reste nul.

On a donc 630=15×42630 = 15\times 42.

On peut dire que :

  • 630630 est divisible par 1515

  • 630630 est un multiple de 1515

  • 1515 est un diviseur de 630630

  • 1515 divise 630630

(On peut aussi dire que 630630 est divisible par 4242, etc.)

Critères de divisibilité

  • Un entier naturel est divisible par 2 si son chiffre des unités est 0, 2, 4, 6 ou 8.

  • Un entier naturel est divisible par 3 si la somme de ses chiffres est divisible par 3.

  • Un entier naturel est divisible par 4 si le nombre formé par ses deux derniers chiffres est divisible par 4.

  • Un entier naturel est divisible par 5 si son chiffre des unités est 0 ou 5.

  • Un entier naturel est divisible par 9 si la somme de ses chiffres est divisible par 9.

  • Un entier naturel est divisible par 10 si son chiffre des unités est 0.

Remarques

  • Attention : Pour les critères de divisibilité par 3 et par 9, il faut effectuer la somme des chiffres (et non regarder le chiffre des unités)

  • Il n'existe pas de critère de divisibilité par 7 qui soit très simple. Le plus rapide est en général d'effectuer la division !

Exemple

  • 13141314 est divisible par 22 (chiffre des unités : 4)

  • 13141314 est divisible par 33 (somme des chiffres : 9)

  • 13141314 n'est pas divisible par 44 (deux derniers chiffres : 14)

  • 13141314 n'est pas divisible par 55 (chiffre des unités : 4)

  • 13141314 est divisible par 99 (somme des chiffres : 9)

  • 13141314 n'est pas divisible par 1010 (chiffre des unités : 4)

2 - Nombres premiers

Définition

On dit qu'un nombre entier naturel est premier s'il possède exactement deux diviseurs : 1 et lui-même.

Exemples

  • 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.

Remarque

Il est utile de connaître par cœur la liste des nombres premiers inférieurs à 20 (ou plus ...):

2 ; 3 ; 5 ; 7 ; 11 ; 13 ; 17 ; 19

Théorème

Décomposition en produit de facteurs premiers

Tout nombre entier supérieur ou égal à 2 peut s'écrire sous la forme d'un produit de nombres premiers. Cette décomposition est unique (à l'ordre des facteurs près).

Remarque

Ce résultat très important est également appelé « Théorème fondamental de l'arithmétique »

Exemple

  • 10=2×510 = 2 \times 5

  • 84=2×2×3×7=22×3×784 = 2 \times 2 \times 3 \times 7 = 2^2 \times 3 \times 7

  • 23=2323 = 23 (un seul facteur car 23 est premier !)

Méthode

Pour décomposer un nombre N N en produit de facteurs premiers, on peut essayer de le diviser successivement par chaque nombre premier inférieur ou égal à n \sqrt{ n } . Le méthode détaillée est décrite sur la fiche : Décomposition en produit de facteurs premiers.

3 - PGCD

Définition

Le PGCD de deux entiers naturels non nuls aa et bb est le plus grand diviseur commun à aa et à bb, c'est à dire le plus grand entier naturel qui divise à la fois aa et bb.

Exemple

Soit à déterminer le PGCD de 600600 et 315315.

Les diviseurs de 600600 sont :

1;2;3;4;5;6;8;10;12;15;20;24;25;30;40;50;60;75;100;120;150;200;300;6001; 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 315315 sont :

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

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

PGCD(600 ;315)=15PGCD\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). D'autres méthodes sont proposées en compléments : Calcul du PGCD par soustractions successives et algorithme d'Euclide.

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.

Exemples

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=3×3×5=32×545 = \color{red}{3 }\color{black} \times 3 \times \color{red}{5} \color{black}= 3^2 \times 5

    150=2×3×5×5=2×3×52 150 = 2 \times \color{red}{3}\color{black} \times \color{red}{5}\color{black} \times 5 = 2 \times 3 \times 5^2

    33 et 55 sont les facteurs premiers figurant dans les deux décompositions donc le PGCD de 4545 et de 150150 est 3×5=15. 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=2×2×3×3×3=22×33108 = \color{red}{2 \times 2}\color{black} \times \color{red}{ 3 \times 3}\color{black} \times 3 = 2^2 \times 3^3

    144=2×2×2×2×3×3=24×32 144 = \color{red}{2 \times 2}\color{black} \times 2 \times 2 \times \color{red}{3 \times 3}\color{black} = 2^4 \times 3^2

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

Définition

Une fraction est irréductible si son numérateur et son dénominateur n'ont aucun diviseur commun mis à part 11, c'est à dire si le PGCD du numérateur et du dénominateur est égal à 1.

Exemples

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

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

    12199=11×119×11=119\frac{121}{99}=\frac{11\times 11}{9\times 11}=\frac{11}{9}