Calculateur du théorème chinois des restes
Résolvez des congruences simultanées en une fois : x ≡ 2 (mod 3), x ≡ 3 (mod 5) et x ≡ 2 (mod 7) ont 23 pour plus petite solution positive, et la réponse revient tous les 105. Utile pour les devoirs et les concours. Gratuit dans votre navigateur.
- Gratuit
- Fonctionne dans votre navigateur
- Sans inscription
- Vos données restent sur votre appareil
Lancer gratuitement
Exemple résolu
- Restes
- 2, 3, 2
- Modules
- 3, 5, 7
- X
- 23
- Module
- 105
- Produit
- 105
- Quantité
- 3
Vous fournissez deux tableaux parallèles ; le moteur vérifie la coprimalité, fusionne les congruences par CRT successif avec des pgcd entiers exacts et des inverses modulaires, puis indique le représentant canonique dans l'intervalle de zéro au produit moins un. Le calcul est une arithmétique entière pure : aucun réseau, aucun aléa, aucune horloge, donc les mêmes tableaux donnent toujours le même x.
Ce que le théorème chinois des restes garantit pour des modules copremiers
Le célèbre exemple de cours, x congru à 2 modulo 3, x congru à 3 modulo 5 et x congru à 2 modulo 7, donne x égal à 23 modulo 105, et 23 est la plus petite solution non négative que cet outil renvoie. Ce calculateur exige délibérément des modules copremiers deux à deux : lorsque cette condition préalable est remplie, l'existence et l'unicité sont garanties, la réponse est toujours bien définie et l'étape de fusion n'a jamais à raisonner sur des facteurs partagés.
Les systèmes dont les modules ne sont pas copremiers deux à deux sont rejetés plutôt que résolus, ce qui maintient le contrat simple et honnête.
Comment le CRT successif calcule exactement la solution et où il est utilisé
En interne, le moteur part de la première congruence et fusionne successivement la suivante. Étant données une solution partielle x congru à x0 modulo m et une nouvelle congruence x congru à a modulo n avec m et n copremiers, il calcule l'inverse modulaire de m modulo n avec l'algorithme d'Euclide étendu, le multiplie par la différence réduite a moins x0, et élève x0 de m fois ce pas pour obtenir la nouvelle solution partielle modulo m fois n.
Les étudiants rencontrent cette construction lorsque leurs manuels leur demandent de reconstruire un nombre à partir de ses résidus ; les enseignants peuvent générer des corrigés pour des feuilles d'exercices de congruences simultanées sans faire confiance à des calculateurs opaques ; les développeurs utilisent le même contrat pour valider des reconstructions modulaires dans des démonstrations pédagogiques de RSA, où le CRT avec des facteurs premiers copremiers accélère le déchiffrement, et pour construire des vecteurs de test déterministes pour les bibliothèques d'arithmétique modulaire.
Cas d’usage
Congruences simultanées pour devoirs et concours
Résolvez des systèmes de manuels comme x ≡ 2 mod 3, x ≡ 3 mod 5, x ≡ 2 mod 7 et obtenez la plus petite solution non négative avec le produit des modules.
Jeux d'essai déterministes pour bibliothèques modulaires
Générez des solutions CRT reproductibles pour les tests unitaires et les assertions CI sans intégrer de tables calculées à la main qui dériveraient de l'implémentation.
Questions fréquentes
Combien coûte le calculateur du théorème chinois des restes ?
Il est gratuit dans votre navigateur sur cette page.
Les modules doivent-ils être copremiers deux à deux ?
Oui. Ce calculateur exige des modules copremiers deux à deux, ce qui garantit une solution unique modulo leur produit.
L'algorithme est-il aléatoire ?
Non. Il utilise un CRT successif déterministe avec pgcd entier exact et inverses modulaires. Les mêmes restes et modules donnent toujours la même plus petite solution non négative.
Les restes peuvent-ils être négatifs ?
Oui. Chaque reste négatif est d'abord réduit modulo son propre module : il est traité comme la valeur équivalente comprise entre zéro et le module moins un, puis le système est résolu normalement.
Pourquoi n'y a-t-il qu'une seule réponse sous le produit des modules ?
Parce que le théorème garantit une seule classe de solutions modulo ce produit lorsque les modules sont premiers entre eux deux à deux. Dans l'exemple classique, toute autre solution diffère de 23 d'un multiple de 105, donc 23 est la plus petite.
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/chinese-remainder \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"remainders":[2,3,2],"moduli":[3,5,7]}'const res = await fetch("https://api.kit.forhosting.com/math/chinese-remainder", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"remainders": [
2,
3,
2
],
"moduli": [
3,
5,
7
]
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/math/chinese-remainder",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"remainders": [
2,
3,
2
],
"moduli": [
3,
5,
7
]
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/math/chinese-remainder", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"remainders":[2,3,2],"moduli":[3,5,7]}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"remainders":[2,3,2],"moduli":[3,5,7]}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/math/chinese-remainder", 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
{
"remainders": [
2,
3,
2
],
"moduli": [
3,
5,
7
]
}Exemple de réponse
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "math.chinese_remainder",
"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.
Limites
max_items | 64 |
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 calculateur du théorème chinois des restes résout un système de congruences simultanées — x congru à chaque reste a_i modulo chaque module n_i — lorsque les modules sont copremiers deux à deux, et renvoie la plus petite solution non négative ainsi que le produit des modules. Si un couple de modules partage un facteur commun, la requête échoue avec une erreur invalid_input explicite au lieu d'une réponse devinée. Utilisez-le gratuitement dans votre navigateur pour vos devoirs et vos démonstrations d'arithmétique modulaire, ou appelez l'API à $0.002 par requête réussie lorsque vos scripts et jeux d'essai CI exigent des réponses reproductibles.
Ce que le théorème chinois des restes garantit pour des modules copremiers
Le théorème chinois des restes classique affirme que si les modules n_1 à n_k sont copremiers deux à deux — c'est-à-dire qu'aucun couple ne partage de facteur commun supérieur à un — alors il existe exactement une classe de résidus modulo le produit de tous les n_i qui satisfait simultanément chaque congruence x congru à a_i modulo n_i. En cas de succès, la réponse JSON comprend x, le module (qui vaut ici le produit des modules fournis), le produit lui-même, les restes réduits dans l'intervalle canonique de zéro à n_i moins un, une copie des modules et le nombre de congruences.
Comment les entrées sont validées et pourquoi les modules non copremiers sont rejetés
Il s'agit d'un choix de conception délibéré, pas d'une limite mathématique : les systèmes CRT généraux à facteurs partagés peuvent être incohérents, et plutôt que de changer silencieusement de sémantique, ce calculateur tient une seule promesse — modules copremiers en entrée, plus petite solution non négative en sortie. Les champs acceptés sont remainders et moduli, deux tableaux JSON d'entiers de même longueur, avec les alias a, ai et residues correspondant à remainders, et n, ni et mods correspondant à moduli, de sorte que formulaires, chaînes de requête et anciens notebooks partagent un même contrat. Chaque élément peut être un entier JSON ou une chaîne décimale avec un signe initial facultatif ; les fractions, la notation scientifique et les espaces incorporés sont rejetés. Chaque module doit être un entier sûr positif, les restes peuvent être négatifs et sont réduits dans l'intervalle canonique avant la fusion, et au maximum soixante-quatre congruences sont acceptées par requête. Avant toute résolution, le moteur vérifie chaque couple de modules avec l'algorithme du pgcd d'Euclide ; si un couple a un pgcd supérieur à un, la requête échoue avec invalid_input et un message qui nomme le couple fautif, par exemple que le pgcd de 4 et 6 vaut 2. Les tableaux manquants, les longueurs inégales, les éléments non entiers et les produits qui dépassent la plage des entiers sûrs échouent également avec invalid_input, de sorte qu'une cellule de tableur erronée ne devient jamais une réponse fausse silencieuse.
Comment le CRT successif calcule exactement la solution et où il est utilisé
Sur cette page, le calcul s'exécute entièrement dans votre navigateur, gratuitement ; via l'API, chaque résolution réussie coûte $0.002, la validation échouée n'est pas facturée, et rien n'est conservé après le renvoi de la réponse.
Cas d'intégration
Démonstrations pédagogiques de RSA et de reconstruction modulaire
Remontez des résidus modulo des facteurs copremiers vers un entier unique pour expliquer les accélérations RSA fondées sur le CRT, les énigmes de calendrier ou les isomorphismes d'anneaux.
Questions techniques
Que se passe-t-il si les modules ne sont pas copremiers ?
La requête échoue avec invalid_input et un message tel que 'Moduli are not pairwise coprime: gcd(4, 6) = 2', au lieu de deviner une réponse selon une autre sémantique.
Les restes négatifs sont-ils autorisés ?
Oui. Les restes peuvent être négatifs ; ils sont réduits dans l'intervalle de zéro à n_i moins un avant la fusion CRT. Les modules doivent être des entiers positifs.