Calculatrice de PGCD en ligne (algorithme d'Euclide)
Le PGCD de 1071 et 462 vaut 21, obtenu en trois étapes de la méthode d'Euclide, sans décomposer aucun des deux nombres. Saisissez deux entiers, négatifs ou avec un zéro, et servez-vous du résultat pour réduire 462/1071 en 22/51. Gratuit dans votre navigateur.
- Gratuit
- Fonctionne dans votre navigateur
- Sans inscription
- Vos données restent sur votre appareil
Lancer gratuitement
Exemple résolu
- A
- 1 071
- B
- 462
- Gcd
- 21
Les signes sont ignorés, un zéro unique est traité par la règle gcd(n, 0) = |n|, et le seul cas rejeté est le gcd(0, 0), mathématiquement indéfini. C'est un outil petit et exact : le même code déterministe tourne gratuitement dans votre navigateur et derrière le point d'accès payant, donc le nombre que vous voyez en test est celui que votre chaîne de traitement obtiendra en production.
Ce qu'est réellement le plus grand commun diviseur
Le plus grand commun diviseur de deux entiers est le plus grand entier positif qui les divise tous les deux exactement. Pour 1071 et 462, c'est 21, car 1071 = 21 × 51 et 462 = 21 × 22, et aucun entier plus grand ne divise les deux. Quand le résultat vaut 1, on dit que les deux nombres sont premiers entre eux : ils ne partagent aucun facteur.
Le concept est ancien — il est au cœur des Éléments d'Euclide — et il reste le moyen le plus rapide de répondre à des questions très pratiques : réduire une fraction à sa plus simple expression, vérifier si deux processus périodiques finiront par coïncider, ou simplifier un rapport avant de l'afficher. Ce point d'accès prend les deux entiers comme champs a et b, accepte n'importe quel signe, et renvoie un objet avec le diviseur positif. Il n'approche jamais et n'arrondit jamais : un entier entre, un entier exact sort.
Comment l'algorithme d'Euclide le calcule
L'implémentation est la version d'Euclide sans soustraction : remplacez à répétition le plus grand nombre par le reste de la division du plus grand par le plus petit, jusqu'à ce que le reste soit nul ; le dernier reste non nul est la réponse. Pour 1071 et 462, cela donne 1071 mod 462 = 147, puis 462 mod 147 = 21, puis 147 mod 21 = 0, donc le résultat est 21.
La boucle s'exécute en O(log min(a, b)) itérations, ce qui signifie que même des nombres proches de la limite des entiers sûrs se traitent en une poignée d'étapes, sans factorisation ni virgule flottante. Les signes sont retirés d'abord car la divisibilité n'en dépend pas, donc gcd(-12, 18) vaut 6.
Où il s'inscrit dans le travail réel
La réduction de fractions est l'usage canonique : divisez le numérateur et le dénominateur par leur gcd et la fraction est irréductible, ce qu'exigent les moteurs de facturation, les ajusteurs de recettes et les affichages de rapports avant de présenter un nombre. Il sous-tend aussi les tests de primalité relative — un gcd de 1 est le critère — ainsi que le reste chinois et l'inverse modulaire utilisés en cryptographie, où le gcd est la première étape de l'algorithme d'Euclide étendu.
La capacité tourne sur notre edge sans rien stocker : les deux entiers arrivent, le diviseur repart, et aucune trace de vos nombres n'est conservée.
Cas d’usage
Réduire les fractions à leur plus simple expression
Divisez le numérateur et le dénominateur par leur gcd avant de stocker ou d'afficher un rapport, ainsi 462/1071 devient 22/51.
Vérifier si deux nombres sont premiers entre eux
Un résultat de 1 signifie que la paire ne partage aucun facteur, la condition préalable de nombreuses constructions d'ordonnancement, de hachage et de cryptographie.
Aligner des processus périodiques
Combiné avec le lcm, le gcd indique quand deux cycles de longueurs différentes coïncident et comment découper le travail en lots égaux.
Questions fréquentes
Combien cela coûte-t-il ?
Il est aussi gratuit à exécuter dans votre navigateur sur cette page avec exactement le même code.
Les entrées peuvent-elles être négatives ?
Oui. Les signes sont ignorés car la divisibilité n'en dépend pas : gcd(-12, 18) renvoie 6, toujours sous forme d'entier positif.
Que se passe-t-il avec zéro ?
gcd(n, 0) renvoie |n| pour tout n non nul.
Quelle peut être la taille des entiers ?
Tout entier sûr au sens JavaScript, jusqu'à 2^53 − 1 en valeur absolue. Les valeurs hors de cette plage sont rejetées plutôt que calculées de façon imprécise.
Quel algorithme est utilisé ?
L'algorithme d'Euclide : des étapes de reste répétées jusqu'à un reste nul. Il s'exécute en O(log min(a, b)) itérations, sans factorisation ni virgule flottante.
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
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/gcd \
-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/gcd", {
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/gcd",
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/gcd", 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/gcd", 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.gcd",
"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
Le prix est publié, sans tokens ni crédits. Une tâche qui échoue n’est pas facturée.
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
L'API du plus grand commun diviseur prend deux entiers et renvoie le plus grand entier positif qui les divise tous les deux sans reste, calculé avec le classique algorithme d'Euclide.
Comment l'algorithme d'Euclide le calcule
Les cas limites suivent la convention standard : gcd(n, 0) = |n| pour tout n non nul, tandis que gcd(0, 0) est indéfini et rejeté avec une erreur invalid_input plutôt qu'un zéro silencieux et faux.
Où il s'inscrit dans le travail réel
Vous pouvez l'essayer gratuitement sur cette page avec le même code que celui de l'API, et vous ne payez le $0.002 par requête que lorsque vous l'appelez depuis vos propres systèmes, ce qui le rend assez bon marché pour être inséré dans une étape de nettoyage de données qui traite des millions de paires.