Une méthode de calcul du plus grands commun diviseur (pgcd) pour les grands nombres

• Pour les grands nombres, le processus de décomposition des nombres en facteurs premiers (la factorisation première) est long et difficile. Si nous avions besoin de calculer le plus grand commun diviseur (pgcd) pour des nombres aussi grands, alors une méthode qui n'est pas basée sur la factorisation première des nombres serait plus que bienvenue. L'algorithme euclidien est l'une de ces méthodes de calcul du pgcd. Have a look at the example below. Nous expliquerons également pourquoi cela fonctionne.

• Cet algorithme commence par diviser les nombres et enregistrer le reste de l'opération.
• Si 'a' et 'b' sont les deux entiers positifs, 'a' >= 'b'.
• Divisez 'a' par 'b' et obtenez le reste, 'r'.
• Si 'r' = 0, STOP. 'b' est le pgcd de 'a' et 'b'.
• Sinon : Remplacez ('a' par 'b') et ('b' par 'r'). Revenez à l'étape ci-dessus.

Voyons quel est le plus grand diviseur commun (pgcd) des nombres 53.667 et 25.527 :

• [1] Commencer par diviser le plus grand nombre par le plus petit :
• 53.667 : 25.527 = 2 et le Reste = 2.613 => 53.667 = 25.527 × 2 + 2.613
• [2] Divisez ensuite le plus petit nombre par le reste de l'opération ci-dessus :
• 25.527 : 2.613 = 9 et le Reste = 2.010 => 25.527 = 2.613 × 9 + 2.010
• [3] Divisez le reste de la première opération par le reste de la deuxième opération :
• 2.613 : 2.010 = 1 et le Reste = 603 => 2.613 = 2.010 × 1 + 603
• [4] Divisez le reste de la deuxième opération par le reste de la troisième opération :
• 2.010 : 603 = 3 et le Reste = 201 => 2.010 = 603 × 3 + 201
• [5] Divisez le reste de la troisième opération par le reste de la quatrième opération :
• 603 : 201 = 3 et le Reste = 0 => 603 = 201 × 3
• A cette étape, le reste est nul, donc on s'arrête : 201 est le nombre que l'on cherchait.
• Conclusion :
• 201 est le dernier reste non nul. C'est le plus grand commun diviseur, pgcd, des deux nombres.

Le plus grand commun diviseur des deux nombres est le dernier reste non nul.

• Si ce dernier reste est égal à 1, alors les deux nombres sont premiers entre eux.
• Pour les opérations ci-dessus, le dernier reste non nul, 201, est le plus grand commun diviseur (pgcd) des nombres 53.667 et 25.527.
• En utilisant l'algorithme d'Euclide, nous pouvons prouver que deux nombres sont premiers entre eux, voir l'exemple ci-dessous.

Calculez le pgcd (87, 41) :

• [1] Commencez par diviser le plus grand nombre par le plus petit :
• 87 : 41 = 2 et le Reste = 5 => 87 = 41 × 2 + 5
• [2] Divisez ensuite le plus petit nombre par le reste de l'opération ci-dessus :
• 41 : 5 = 8 et le Reste = 1 => 41 = 5 × 8 + 1
• [3] Divisez le reste de la première opération par le reste de la deuxième opération :
• 5 : 1 = 5 et le Reste = 0 => 5 = 1 × 5 + 0
• Le dernier reste non nul des opérations ci-dessus est égal à 1.
• pgcd (87, 41) = 1, donc les nombres sont premiers entre eux.

Mais pourquoi le nombre ainsi obtenu est-il un diviseur des valeurs initiales 'a' et 'b' ?

• Remarque : La division 'a' : 'b' = 'q' + 'r' correspond à l'équation : 'a' = 'b' × 'q' + 'r', où 'q' est le quotient de la division.
• Si la dernière valeur de 'r' = 0, alors la dernière valeur de 'b' est un diviseur de la dernière valeur de 'a' puisque 'a' = 'b' × 'q' + 0.

• Calculons le pgcd (a, b):
• 1. Étape : 'a' = 'b' × 'q₁' + 'r₁', 'r₁' pas nul.
• 2. Étape : 'b' = 'r₁' × 'q₂' + 'r₂', 'r₂' pas nul.
• 3. Étape : 'r₁' = 'r₂' × 'q₃' + 'r₃', 'r₃' pas nul.
• ...
• (n-3). Étape : 'r_(n-5)' = 'r_(n-4)' × 'q_(n-3)' + 'r_(n-3)', 'r_(n-3)' pas nul.
• (n-2). Étape : 'r_(n-4)' = 'r_(n-3)' × 'q_(n-2)' + 'r_(n-2)', 'r_(n-2)' pas nul.
• (n-1). Étape : 'r_(n-3)' = 'r_(n-2)' × 'q_(n-1)' + 'r_(n-1)', 'r_(n-1)' pas nul.
• n. Étape : 'r_(n-2)' = 'r_(n-1)' × 'q_n' + 'r_n', 'r_n' = zéro.
• Le reste est nul, donc on s'arrête.

• Si 'r_n' = 0 => selon la n^ième étape : 'r_(n-1)' est un diviseur de 'r_(n-2)'.
• 'r_(n-1)' est aussi le dernier reste non nul.
• Selon la (n-1)^ième étape : 'r_(n-1)' est un diviseur de 'r_(n-1)' (le nombre lui-même) et de 'r_(n-2)', donc c'est aussi un diviseur de 'r_(n-3)'.
• Selon la (n-2)^ième étape : 'r_(n-1)' est un diviseur de 'r_(n-2)' et de 'r_(n-3)', donc c'est aussi un diviseur de 'r_(n-4)'.
• Selon la (n-3)^ième étape : 'r_(n-1)' est un diviseur de 'r_(n-3)' et de 'r_(n-4)', donc c'est aussi un diviseur de 'r_(n-5)'.
• ...
• Selon la 3^ème étape : 'r_(n-1)' est un diviseur de 'r₃' et de 'r₂', donc c'est aussi un diviseur de 'r₁'.
• Selon la 2^ème étape : 'r_(n-1)' est un diviseur de 'r₂' et de 'r₁', donc c'est aussi un diviseur de 'b'.
• Selon la 1^ère étape : 'r_(n-1)' est un diviseur de 'r₁' et de 'b', donc c'est aussi un diviseur de 'a'.

• Ainsi, nous venons de montrer que le dernier reste non nul, r_(n-1), est un diviseur de 'a' et de 'b'.

Pourquoi le nombre ainsi obtenu est-il toujours égal au plus grand commun diviseur, pgcd ?

• Comme nous l'avons vu plus haut, le reste final non nul divise sans reste à la fois 'a' et 'b'. Appelons ce diviseur 't'.
• Selon la 1^ère étape de division : Si 't' est un diviseur de 'a' et de 'b', alors c'est aussi un diviseur de 'r₁'.
• Selon l'étape de 2^ème division : Si 't' est un diviseur de 'b' et de 'r₁', alors c'est aussi un diviseur de 'r₂'.
• Et ainsi de suite, jusqu'à la (n-1)^ième étape : Si 't' est un diviseur de 'r_(n-3)' et de 'r_(n-2)', alors c'est aussi un diviseur de 'r_(n-1)'. Mais comme nous l'avons calculé ci-dessus, ce diviseur est le dernier reste non nul, qui dans notre cas est 'r_(n-1)'.
• Donc 't' ne peut pas être plus grand que 'r_(n-1)' puisqu'il doit en être un diviseur.

Comment utiliser l'algorithme d'Euclide pour plus de deux nombres :

• L'algorithme d'Euclide peut également être utilisé pour trouver le plus grand commun diviseur de plusieurs nombres, plus de deux, tels que 'a', 'b' et 'c'.
• Calculez d'abord le pgcd ('a', 'b') = 'd' et ensuite calculez le pgcd ('c', 'd').

L'algorithme d'Euclide : calcul du plus petit commun multiple (ppcm) pour les grands nombres

• Pour les très grands nombres, il devient très difficile de calculer le plus petit commun multiple (ppcm) car la décomposition de ces nombres en facteurs premiers (la factorisation première) prend trop de temps.
• A l'aide de l'algorithme d'Euclide non seulement le plus grand commun diviseur (pgcd) doit être calculé - comme vu ci-dessus, mais aussi le plus petit commun multiple (ppcm) est calculé selon la formule :

• ppcm ('a', 'b') = ^{('a' × 'b')} / _{pgcd ('a', 'b')}

• Cette méthode peut être utilisée lorsqu'il n'y a pas plus de deux nombres.

Preuve que la formule ppcm est correcte

• Supposons que les factorisations premières de 'a' et 'b' soient :
• 'a' = 'm' × 'n' × 'p', où 'm', 'n', 'p' sont des nombres premiers.
• 'b' = 'm' × 'q' × 't', où 'm', 'q', 't' sont des nombres premiers.
• => ppcm ('a', 'b') = 'm' × 'n' × 'p' × 'q' × 't'
• => pgcd ('a', 'b') = 'm'

• Donc :
• ^{('a' × 'b')} / _{pgcd ('a', 'b')} =
• ^{('m' × 'm' × 'n' × 'p' × 'q' × 't')} / _'m' =
• 'm' × 'n' × 'p' × 'q' × 't' =
• ppcm ('a', 'b').

Qu'est-ce qu'un nombre premier ? Définition, exemples

Qu'est-ce qu'un nombre composé ? Définition, exemples

Les nombres premiers, jusqu'à 1,000

Les nombres premiers, jusqu'à 10,000

Le crible d'Eratosthène

L'algorithme d'Euclide

Simplifiez les fractions les plus possibles. Étapes et exemples