Tutoriel mathématique

Calcul du PGCD avec l’Algorithme d’Euclide

Dans ce tutoriel, nous allons utiliser l’Algorithme d’Euclide pour le calcul du PGCD.

Définition mathématique du PGCD (Plus Grand Commun Diviseur) :

Le PGCD de deux nombres entiers (a) et (b), noté (\text{PGCD}(a, b)), est le plus grand nombre entier qui divise à la fois (a) et (b) sans laisser de reste.

Algorithme d’Euclide pour calculer le PGCD :

L’algorithme d’Euclide est une méthode efficace pour calculer le PGCD de deux nombres. Voici les étapes de l’algorithme :

  1. Initialisation : Soit (a) et (b) les deux nombres dont nous voulons trouver le PGCD.
  2. Division : Divisez (a) par (b) et obtenez le reste (r).
  3. Test du reste : Si (r) est égal à zéro, alors (b) est le PGCD.
  4. Répétition : Sinon, remplacez (a) par (b) et (b) par (r), puis retournez à l’étape 2.

L’algorithme continue ce processus jusqu’à ce que le reste devienne zéro. À ce moment-là, le dernier diviseur non nul (c’est-à-dire la dernière valeur de (b)) est le PGCD recherché.

Exemple :
Prenons les nombres (a = 48) et (b = 18) pour illustrer l’algorithme d’Euclide :

  1. (48) divisé par (18) donne un quotient de (2) et un reste de (12).
  2. Remplaçons (a) par (b) et (b) par (r), donc maintenant (a = 18) et (b = 12).
  3. Répétons le processus : (18) divisé par (12) donne un quotient de (1) et un reste de (6).
  4. Encore une fois, remplaçons (a) par (b) et (b) par (r), donc maintenant (a = 12) et (b = 6).
  5. Continuons jusqu’à ce que le reste soit zéro. Les étapes suivantes donneront (a = 6), (b = 0), et le PGCD est (6).

Ainsi, (\text{PGCD}(48, 18) = 6).

Javascript

L’algorithme d’Euclide est une méthode classique pour calculer le PGCD de deux nombres. Voici un exemple d’implémentation de l’algorithme d’Euclide en JavaScript :

// Fonction pour calculer le PGCD avec l'algorithme d'Euclide
function euclideanGCD(a, b) {
    while (b !== 0) {
        const temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Exemples d'utilisation
const example1 = euclideanGCD(48, 18);
console.log("PGCD de 48 et 18 :", example1);

const example2 = euclideanGCD(60, 72);
console.log("PGCD de 60 et 72 :", example2);

Dans cet exemple, la fonction euclideanGCD prend deux paramètres, a et b, et utilise l’algorithme d’Euclide pour calculer leur PGCD. La boucle while est utilisée pour itérer jusqu’à ce que b devienne zéro, et à chaque itération, les valeurs de a et b sont mises à jour en fonction des opérations modulo. La fonction renvoie le PGCD une fois que b atteint zéro.

Les exemples d’utilisation démontrent comment utiliser cette fonction pour calculer le PGCD de deux paires de nombres (48, 18) et (60, 72). Vous pouvez remplacer ces valeurs par d’autres nombres pour effectuer d’autres calculs.

Python

Voici un exemple d’implémentation de l’algorithme d’Euclide pour calculer le PGCD en Python :

def euclidean_gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# Exemples d'utilisation
example1 = euclidean_gcd(48, 18)
print("PGCD de 48 et 18 :", example1)

example2 = euclidean_gcd(60, 72)
print("PGCD de 60 et 72 :", example2)

Dans cet exemple Python, la fonction euclidean_gcd réalise le même algorithme d’Euclide que dans l’exemple JavaScript. La boucle while est utilisée pour itérer jusqu’à ce que b soit égal à zéro, et à chaque itération, les valeurs de a et b sont mises à jour en fonction des opérations modulo. La fonction renvoie le PGCD une fois que b atteint zéro.

Les exemples d’utilisation montrent comment utiliser cette fonction pour calculer le PGCD de deux paires de nombres (48, 18) et (60, 72). Vous pouvez remplacer ces valeurs par d’autres nombres pour effectuer d’autres calculs en Python.

C

Voici un exemple d’implémentation de l’algorithme d’Euclide pour calculer le PGCD en langage C :

#include <stdio.h>

int euclidean_gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    // Exemples d'utilisation
    int example1 = euclidean_gcd(48, 18);
    printf("PGCD de 48 et 18 : %d\n", example1);

    int example2 = euclidean_gcd(60, 72);
    printf("PGCD de 60 et 72 : %d\n", example2);

    return 0;
}

Dans ce programme en langage C, la fonction euclidean_gcd implémente l’algorithme d’Euclide. La boucle while est utilisée pour itérer jusqu’à ce que b soit égal à zéro, et à chaque itération, les valeurs de a et b sont mises à jour en utilisant l’opération modulo. La fonction renvoie le PGCD une fois que b atteint zéro.

Le programme principal (main) utilise cette fonction pour calculer le PGCD de deux paires de nombres (48, 18) et (60, 72). Les résultats sont ensuite affichés à l’aide de la fonction printf. Vous pouvez remplacer les valeurs pour effectuer d’autres calculs en langage C.

Autres articles

Guide Complet : Symboles Mathématiques en LaTeX
LaTeX est un outil puissant pour écrire des équations et...
Read more
Parité d'une Fonction : Exercices Corrigés
La parité d'une fonction est un concept fondamental en mathématiques...
Read more
La Parité d'une Fonction : Utilisation et...
En mathématiques, la parité d'une fonction est un concept qui...
Read more
AZ

Recent Posts

Série d’exercices corrigés – Excel Perfectionnement

Voici une série d’exercices conçus pour perfectionner vos compétences Excel. Les corrigés sont inclus pour…

5 heures ago

Guide : Calculer une moyenne avec un filtre dans Excel

Excel offre plusieurs méthodes pour calculer une moyenne tout en tenant compte des filtres ou…

6 heures ago

Utiliser les fonctions pour afficher la date actuelle dans Excel

Excel propose plusieurs fonctions pour insérer ou manipuler la date actuelle. Voici les principales méthodes…

6 heures ago

Comment convertir des textes en chiffres dans Excel

Lorsque des nombres sont stockés sous forme de texte dans Excel, ils ne peuvent pas…

7 heures ago

Comment extraire les chiffres d’une cellule dans Excel

Extraire uniquement les chiffres d'une cellule contenant du texte et des nombres mélangés est une…

7 heures ago

Comment supprimer plusieurs caractères spécifiques dans Excel

Pour supprimer plusieurs caractères spécifiques (par exemple, des symboles, chiffres ou lettres indésirables) dans des…

7 heures ago

This website uses cookies.