PGCD-Nombres premiers entre eux - Maxicours

PGCD-Nombres premiers entre eux

Objectif :
PGCD de deux entiers naturels - Nombres premiers entre eux
1. PGCD de deux entiers naturels

Définition : Si a et b sont deux entiers, on appelle PGCD (Plus Grand Commun Diviseur) de a et b le plus grand des diviseurs communs de a et de b.

On le note PGCD(a ; b).


Exemple : L'ensemble des diviseurs de 45 est D45 = { 1 ; 3 ; 5 ; 9 ; 15 ; 45 }.
L'ensemble des diviseurs de 63 est D63 = { 1 ; 3 ; 7 ; 9 ; 21 ; 63 }.
L'ensemble de leurs diviseurs communs est D45D63 = { 1 ; 3 ; 9 }.
Leur plus grand diviseur commun est 9. PGCD( 45 ; 63 ) = 9.

Recherche du PGCD avec l'algorithme d'Euclide

Pour trouver le PGCD de deux naturels, une méthode est d'utiliser l'algorithme d'Euclide : on effectue la division euclidienne du plus grand des deux nombres par le plus petit, puis successivement la division du diviseur précédent par le reste précédent jusqu'au dernier reste nul. Le PGCD cherché est le dernier reste non nul.


Exemple : Calcul du PGCD de 4851 et de 616.

donc le PGCD de 4851 et de 616 est 77, le dernier reste non nul.

Le programme de calcul du PGCD
Données :  deux entiers naturels a et b, a > b.
Résultat : PGCD( a ; b ).
Règle :
Tant que b > 0, faire :
         

Retourner à b ← r signifie que dans le registre noté b, on met le contenu du registre noté r.

Théorèmes
Si c est un diviseur de a et un diviseur de b, alors c est un diviseur du PGCD de a et de b.

Exemple : Tout diviseur de 4851 et de 616 est diviseur de leur PGCD, 77.

Si b est un diviseur de a, alors PGCD( a ; b ) = b.

Exemple: PGCD( 187 ; 17 ) = 17.

Quels que soient les entiers naturels non nuls a, b et k,
PGCD( ka ; kb ) = k x PGCD( a ; b ).

Exemple : PGCD ( 4500 ; 6300 ) = 100 x PGCD ( 45 ; 63 ) = 100 x 9 = 900.
2. Nombres premiers entre eux
Définition
« Les deux entiers naturels a et b sont premiers entre eux » signifie que PGCD( a ; b ) = 1.
On en déduit que le seul diviseur commun de deux entiers naturels premiers entre eux est 1.

Exemple :
Le seul diviseur commun de 14 et 25 est 1, donc 14 et 25 sont premiers entre eux.
7 est un diviseur commun de 14 et 21, donc 14 et 21 ne sont pas premiers entre eux.
Théorème
- Quels que soient les entiers non nuls a et b, si PGCD( a ; b ) = D, alors il existe deux entiers naturels a' et b' premiers entre eux tels que a = Da'  et b = Db'.

Ou

- Quels que soient les entiers non nuls a et b, si PGCD( a ; b ) = D, alors les nombres a/D et b/D sont premiers entre eux.

Exemple : PGCD ( 4500 ; 6300 ) = 900.

   et   ; PGCD( 5 ; 7 ) = 1.

Vous avez déjà mis une note à ce cours.

Découvrez les autres cours offerts par Maxicours !

Découvrez Maxicours

Comment as-tu trouvé ce cours ?

Évalue ce cours !

 

quote blanc icon

Découvrez Maxicours

Exerce toi en t’abonnant

Des profs en ligne

  • 6 j/7 de 17 h à 20 h
  • Par chat, audio, vidéo
  • Sur les matières principales

Des ressources riches

  • Fiches, vidéos de cours
  • Exercices & corrigés
  • Modules de révisions Bac et Brevet

Des outils ludiques

  • Coach virtuel
  • Quiz interactifs
  • Planning de révision

Des tableaux de bord

  • Suivi de la progression
  • Score d’assiduité
  • Un compte Parent

Inscrivez-vous à notre newsletter !

Votre adresse e-mail sera exclusivement utilisée pour vous envoyer notre newsletter. Vous pourrez vous désinscrire à tout moment, à travers le lien de désinscription présent dans chaque newsletter. Conformément à la Loi Informatique et Libertés n°78-17 du 6 janvier 1978 modifiée, au RGPD n°2016/679 et à la Loi pour une République numérique du 7 octobre 2016, vous disposez du droit d’accès, de rectification, de limitation, d’opposition, de suppression, du droit à la portabilité de vos données, de transmettre des directives sur leur sort en cas de décès. Vous pouvez exercer ces droits en adressant un mail à : contact-donnees@sejer.fr. Vous avez la possibilité de former une réclamation auprès de l’autorité compétente. En savoir plus sur notre politique de confidentialité