Calculer le plus grand commun diviseur.
Deux méthodes utilisées ci-dessous.
Méthode 1. La décomposition des nombres en facteurs premiers:
Décomposition d'un nombre en facteurs premiers: il s'agit de trouver les nombres premiers qui se multiplient pour former ce nombre.
51 = 3 × 17;
51 n'est pas un nombre premier, est un nombre composé;
38 = 2 × 19;
38 n'est pas un nombre premier, est un nombre composé;
* Les nombres qui ne se divisent que par eux-mêmes et par 1, s'appellent des nombres premiers. Un nombre premier n'a que deux diviseurs: 1 et lui-même.
* Un nombre composé est un entier naturel différent de 0 qui possède un diviseur positif autre que 1 ou lui-même.
Calcule le plus grand commun diviseur:
Prenez tous les facteurs premiers communs, par les puissances les plus bas.
MAIS... Les deux nombres n'ont pas de facteurs premiers communs.
pgcd (51; 38) = 1;
nombres premiers entre eux (copremiers)
Nombres premiers entre eux (copremiers) (51; 38)? Oui.
Les nombres n'ont pas de facteurs premiers communs.
pgcd (38; 51) = 1.
Méthode 2. Algorithme d' Euclide:
Cet algorithme implique l'opération de division et de calcul des restes.
'a' et 'b' sont les deux entiers positifs, 'a' >= 'b'.
Divisez 'a' par 'b' et obtenez le reste, 'r'.
Si 'r' = 0, STOP. 'b' = le PGCD de 'a' et 'b'.
Sinon: Remplacez ('a' par 'b') et ('b' par 'r'). Revenir à l'étape de la division, ci-dessus.
L'opération 1. On divise le nombre le plus grand au nombre le plus petit:
51 : 38 = 1 + 13;
L'opération 2. On divise le nombre le plus petit au reste de l'opération ci-dessus:
38 : 13 = 2 + 12;
L'opération 3. On divise le reste de l'opération 1 par le reste de l'opération 2:
13 : 12 = 1 + 1;
L'opération 4. On divise le reste de l'opération 2 par le reste de l'opération 3:
12 : 1 = 12 + 0;
En ce moment, comme il n'y a plus de reste, on s'arrête:
1 est le nombre recherché, le dernier reste différent de zéro.
Ceci est le plus grand commun diviseur.
pgcd (51; 38) = 1;
Pourquoi la réponse est-elle un diviseur des valeurs initiales 'a' et 'b'?
Remarque: 'a' : 'b' = 'q' + 'r' est équivalente à l'équation: 'a' = 'q' × 'b' + 'r', où 'q' est le quotient de l'opération.
Lorsque la valeur finale de 'r' = 0, la valeur finale de 'b' est un diviseur de la valeur finale de 'a', puisque 'a' = 'q' × 'b' + 0.
Revenez en arrière dans chacune des étapes précédentes et analysez chaque équation, 'a' = 'q' × 'b' + 'r', et notez qu'à chaque étape la valeur finale de 'b' est un diviseur de chaque valeur de 'r' et de chaque valeur de 'b' et est donc un diviseur de chaque valeur de 'a'. Ainsi, la dernière valeur de 'b', qui est le dernier reste différent de zéro, est un diviseur des valeurs initiales de 'a' et 'b'.
Pourquoi la réponse est-elle égale au PGCD?
Regardez toutes les équations: 'a' = 'q' × 'b' + 'r'. Comme nous l'avons vu ci-dessus, la valeur finale de 'b' est un diviseur de toutes les valeurs de 'a', 'b' et 'r'.
Par conséquent, la valeur finale de 'b' doit également être un diviseur de la dernière valeur de 'r', celle qui est différente de zéro. Et la valeur finale de 'b' ne pourrait pas être supérieure à cette dernière valeur de 'r'. Puisque la valeur finale de 'b' est égale à cette dernière valeur de 'r', donc la valeur finale de 'b' est le plus grand diviseur des valeurs initiales de ('a' et 'b'). Et par définition, il est appelé le plus grand commun diviseur des nombres.
Nombres premiers entre eux (copremiers) (51; 38)? Oui.
pgcd (38; 51) = 1.