PGCD et PPCM

a = b × q + r, puis PGCD(a, b) = PGCD(b, r)

Le PGCD par l'algorithme d'Euclide, avec la chaîne complète des divisions affichée : dividende = diviseur × quotient + reste, ligne après ligne, jusqu'au dernier reste non nul. C'est cette rédaction qu'on demande en copie, pas le résultat seul. Le PPCM s'en déduit par l'identité PGCD × PPCM = a × b, et la fraction a/b est rendue simplifiée. Trois entiers sont acceptés ; les nombres trop grands pour rester exacts sont refusés plutôt qu'arrondis.

PGCD

PPCM: 8640
Fraction simplifiée: 45 / 32

Algorithme d’Euclide

270 = 192 × 1 + 78
192 = 78 × 2 + 36
78 = 36 × 2 + 6
36 = 6 × 6 + 0

Le PGCD est 6 et le PPCM est 8640.

Chaque ligne est une division euclidienne : dividende = diviseur × quotient + reste. Le diviseur et le reste d’une ligne deviennent le dividende et le diviseur de la suivante, et le dernier reste non nul est le PGCD. C’est cette chaîne qu’on demande en copie.

Pour deux nombres, PGCD × PPCM = a × b, toujours : les deux résultats se contrôlent l’un l’autre. Pour trois nombres, l’identité ne tient plus telle quelle ; l’outil enchaîne les calculs deux à deux.

Dossier scientifique

Ce que l'outil calcule, ce qu'il suppose, où il cesse d'être valable et d'où viennent ses données.

Méthode & formulesa = b × q + r, puis PGCD(a, b) = PGCD(b, r)

a = b × q + r, puis PGCD(a, b) = PGCD(b, r)

PGCD × PPCM = a × b

a/b simplifiée = (a ÷ PGCD) / (b ÷ PGCD)

L'algorithme d'Euclide remplace le couple (a, b) par (b, r) tant que le reste n'est pas nul : le dernier reste non nul est le PGCD. L'identité PGCD × PPCM = a × b donne le PPCM sans chercher de multiples, et fournit un contrôle : les deux résultats doivent se multiplier en a × b.

PGCD: · le plus grand entier qui divise les deux nombres. Il simplifie les fractions et partage en parts égales maximales.
PPCM: · le plus petit entier non nul multiple des deux nombres. Il met les fractions au même dénominateur et synchronise les cycles.
Premiers entre eux: · PGCD égal à 1. Les nombres n’ont aucun facteur commun ; leur PPCM est leur produit.

Domaine de validitéL'outil travaille sur des entiers positifs et refuse le reste : les décimaux (multipliez par une puissance de 10 d'abord), les négatifs (le PGCD est celui des valeurs absolues), et les nombres au-delà de 90 000 000, car le PPCM peut atteindre le produit des entrées et sortirait des entiers exacts de la machine.

L'outil travaille sur des entiers positifs et refuse le reste : les décimaux (multipliez par une puissance de 10 d'abord), les négatifs (le PGCD est celui des valeurs absolues), et les nombres au-delà de 90 000 000, car le PPCM peut atteindre le produit des entrées et sortirait des entiers exacts de la machine. PGCD(0, b) vaut b par convention ; PGCD(0, 0) n'existe pas.

Lecture du résultatLa chaîne d'Euclide est le vrai livrable : chaque ligne est une division euclidienne dont le diviseur et le reste glissent d'un cran à la ligne suivante.

La chaîne d'Euclide est le vrai livrable : chaque ligne est une division euclidienne dont le diviseur et le reste glissent d'un cran à la ligne suivante. Sur une copie, on rédige exactement ces lignes puis on conclut « le dernier reste non nul est 6, donc PGCD(270, 192) = 6 ». Le PPCM sert l'autre moitié des exercices : mise au même dénominateur, problèmes de cycles qui se resynchronisent (deux bus partis ensemble repartent ensemble au bout du PPCM de leurs périodes).