ForHosting KIT · Mathématiques

Algorithme d'Euclide

Pour 1071 et 462, le PGCD vaut 21, atteint en trois divisions : 1071 = 462 × 2 + 147, puis 462 = 147 × 3 + 21, puis un reste nul. Saisissez deux entiers et voyez chaque étape, pas seulement le résultat. Gratuit dans votre navigateur.

Gratuit
Fonctionne dans votre navigateur
Sans inscription
Vos données restent sur votre appareil

Lancer gratuitement Voir l’API

Utilisez-le depuis WebAPIE-mailTelegramApp bientôt

Exemple résolu

Si vous saisissez

A: 1 071
B: 462

Vous obtenez

Gcd: 21
Nombre d'étapes: 3

Le calculateur de l'algorithme d'Euclide prend deux entiers et calcule leur plus grand commun diviseur comme Euclide l'a décrit il y a plus de deux mille ans : en divisant à répétition et en conservant le reste. Au lieu de ne renvoyer que le nombre final, il renvoie la liste complète des étapes — chaque ligne de la forme dividende = diviseur × quotient + reste — pour que vous voyiez exactement comment la réponse a été obtenue. Il accepte les valeurs négatives (le PGCD utilise les valeurs absolues), rejette les entrées non entières et refuse le cas indéfini pgcd(0,0).

Ce que fait réellement l'algorithme d'Euclide

Le plus grand commun diviseur de deux entiers est le plus grand nombre qui les divise tous les deux sans laisser de reste. L'algorithme d'Euclide le trouve sans rien factoriser, et c'est pourquoi il reste rapide même pour de très grandes entrées. L'idée est simple : si un nombre divise à la fois a et b, il divise aussi le reste de la division de a par b.

On remplace donc le couple (a, b) par (b, a mod b) et on recommence. Chaque étape est une division longue — par exemple, 1071 = 462 × 2 + 147 — et l'on continue jusqu'à ce que le reste soit nul. Le dernier reste non nul est le PGCD.

Comme le reste décroît strictement à chaque étape, la boucle se termine toujours, et vite : le nombre d'étapes est proportionnel au logarithme de la plus petite entrée.

Entrées, cas limites et signalement des erreurs

Vous envoyez deux champs, a et b, et tous deux doivent être des entiers. Les entiers négatifs sont valides : le PGCD est défini sur les valeurs absolues, donc pgcd(-1071, 462) est identique à pgcd(1071, 462), et la liste des étapes est calculée sur les valeurs absolues. Zéro est une entrée valide pour l'un des champs — pgcd(a, 0) vaut |a|, et dans ce cas la liste des étapes est vide car aucune division n'est nécessaire —, mais les deux champs à zéro sont rejetés, car pgcd(0,0) est mathématiquement indéfini.

Les erreurs ne produisent jamais de réponse partielle : la requête est refusée avec un code lisible par machine et un message que vous pouvez afficher à l'utilisateur.

Où un PGCD pas à pas se révèle utile

Le PGCD brut est une commodité — chaque langage en a un dans sa bibliothèque standard. Ce que cette capacité ajoute, c'est la trace. Enseignants et étudiants utilisent la liste des étapes pour vérifier qu'un exercice a été résolu avec le véritable algorithme d'Euclide plutôt qu'en devinant des diviseurs.

Les développeurs l'utilisent pour déboguer la simplification de fractions, la réduction de rapports d'aspect ou les tests de primalité relative, car voir 252 = 105 × 2 + 42 montre exactement où un calcul manuel diverge du code. Celles et ceux qui apprennent la cryptographie rencontrent l'algorithme comme fondation de la version étendue qui produit les coefficients de Bézout et les inverses modulaires ; voir d'abord les simples étapes de division rend ce saut bien plus facile.

Cas d’usage

Vérifier un exercice rédigé

Collez les deux nombres d'un devoir et comparez vos étapes de division manuscrites avec celles que l'algorithme produit réellement.

Simplifier des fractions et des rapports

Obtenez le PGCD d'un numérateur et d'un dénominateur pour réduire une fraction, avec la liste des étapes comme piste d'audit de la façon dont le diviseur a été trouvé.

Enseigner l'algorithme avant la version étendue

Montrez d'abord aux élèves la trace de division simple, puis passez aux coefficients de Bézout et aux inverses modulaires construits sur la même boucle.

Questions fréquentes

Combien cela coûte-t-il ?

L'exécution est également gratuite dans votre navigateur sur cette page.

Pourquoi pgcd(0,0) est-il rejeté ?

Parce que le plus grand commun diviseur de zéro et zéro est indéfini : tout entier divise zéro, il n'y en a donc aucun qui soit le plus grand. Fournissez au moins une valeur non nulle.

Puis-je passer des nombres négatifs ?

Oui. Le PGCD est calculé sur les valeurs absolues, donc pgcd(-1071, 462) renvoie le même résultat que pgcd(1071, 462).

Que contient le tableau steps ?

Un objet par division : dividende, diviseur, quotient et reste, de sorte que chaque ligne se lit dividende = diviseur × quotient + reste. Le dernier reste non nul est le PGCD.

Quelle taille maximale pour les entrées ?

Jusqu'à l'entier sûr maximal, 9007199254740991, de sorte que chaque quotient et chaque reste de la sortie est exact.

Outils associés

Pour les développeurs — accès API

Tout sur cette page est disponible par programmation. Cette section s'adresse aux équipes qui veulent l'intégrer à leurs systèmes ; les autres peuvent simplement utiliser l'outil ci-dessus.

Endpoint

POSThttps://api.kit.forhosting.com/math/euclidean-algorithm

Authentification par jeton Bearer : un seul POST met la tâche en file d’attente, et le résultat vous parvient par webhook ou lien signé.

Appeler depuis votre stack

curl -X POST https://api.kit.forhosting.com/math/euclidean-algorithm \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"a":1071,"b":462}'

const res = await fetch("https://api.kit.forhosting.com/math/euclidean-algorithm", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "a": 1071,
    "b": 462
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/math/euclidean-algorithm",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "a": 1071,
    "b": 462
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/math/euclidean-algorithm", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"a":1071,"b":462}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"a":1071,"b":462}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/math/euclidean-algorithm", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

Exemple de requête

{
  "a": 1071,
  "b": 462
}

Exemple de réponse

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "math.euclidean_algorithm",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

L’API est asynchrone : chaque appel renvoie un task_id immédiatement, puis vous interrogez l’état à raison d’une requête par seconde.

Tarifs

par requête$0.002

Le prix est publié, sans tokens ni crédits. Une tâche qui échoue n’est pas facturée.

Limites

max_abs 9007199254740991

Erreurs

HTTP	Code	Signification
`401`	`unauthorized`	Clé API absente ou invalide : vérifiez l’en-tête Authorization.
`402`	`insufficient_balance`	Solde insuffisant : rechargez votre compte pour lancer cette tâche.
`404`	`unknown_type`	Type de tâche inconnu : vérifiez le champ type de votre requête.
`429`	`rate_limited`	Trop de requêtes : ralentissez la cadence, puis réessayez.

Notes techniques

Le même code s'exécute gratuitement dans votre navigateur sur cette page et via l'API payante.

Ce que fait réellement l'algorithme d'Euclide

Ce endpoint exécute exactement cette procédure et vous renvoie chaque division effectuée, pas seulement la conclusion, ce qui le rend utile aussi bien pour vérifier des devoirs que pour auditer un calcul au sein d'un système plus vaste.

Entrées, cas limites et signalement des erreurs

Les chaînes numériques qui représentent des entiers exacts, comme "1071", sont acceptées ; les décimaux, les fractions, la notation scientifique et les valeurs non numériques sont rejetés avec une erreur invalid_input qui explique le problème. Les valeurs sont bornées par la plage des entiers sûrs des doubles IEEE 754, environ 9 billiards, de sorte que chaque quotient et chaque reste de la sortie est exact.

Questions techniques

Qu'est-ce qui compte comme un entier ?

Un nombre JSON sans partie fractionnaire, ou une chaîne de chiffres avec un signe initial facultatif. Les décimaux, la notation scientifique et les valeurs non numériques sont rejetés avec une erreur invalid_input.

Consulter la documentation complète du KIT →

Lancer gratuitement

Exemple résolu

Ce que fait réellement l'algorithme d'Euclide

Entrées, cas limites et signalement des erreurs

Où un PGCD pas à pas se révèle utile

Cas d’usage

Vérifier un exercice rédigé

Simplifier des fractions et des rapports

Enseigner l'algorithme avant la version étendue

Questions fréquentes

Outils associés

Pour les développeurs — accès API

Endpoint

Appeler depuis votre stack

Exemple de requête

Exemple de réponse

Tarifs

Limites

Erreurs

Notes techniques

Ce que fait réellement l'algorithme d'Euclide

Entrées, cas limites et signalement des erreurs

Questions techniques

merci