Calcolatore del teorema cinese del resto
Risolva congruenze simultanee in un colpo solo: x ≡ 2 (mod 3), x ≡ 3 (mod 5) e x ≡ 2 (mod 7) hanno 23 come più piccola soluzione non negativa, e la risposta si ripete ogni 105. Utile per compiti, gare e soluzionari. Gratis nel suo browser.
- Gratis
- Funziona nel suo browser
- Senza registrazione
- I suoi dati restano sul dispositivo
Esegui gratis nel browser
Esempio risolto
- Resti
- 2, 3, 2
- Moduli
- 3, 5, 7
- X
- 23
- Modulo
- 105
- Prodotto
- 105
- Quantità
- 3
Lei fornisce due array paralleli; il motore verifica la coprimalità, combina le congruenze con il CRT successivo usando gcd interi esatti e inversi modulari, e riporta il rappresentante canonico nell'intervallo da zero al prodotto meno uno. Il calcolo è aritmetica intera pura: nessuna rete, nessuna casualità e nessun orologio, quindi gli stessi array producono sempre la stessa x.
Che cosa dice il teorema cinese del resto
Il teorema risponde a un antico rompicapo: quale numero dà resto 2 se diviso per 3, resto 3 se diviso per 5 e resto 2 se diviso per 7? Quando i divisori, detti moduli, sono coprimi a due a due, cioè nessuna coppia ha un fattore comune maggiore di uno, esiste esattamente una risposta compresa tra zero e il loro prodotto meno uno. Qui il prodotto è 105 e la risposta è 23. Ogni altro numero che soddisfa le tre condizioni è 23 più o meno un multiplo di 105, quindi un solo risultato descrive un'intera famiglia di soluzioni.
Come si risolve e dove si sbaglia di solito
Il calcolatore parte dalla prima congruenza e unisce le altre una alla volta. A ogni passaggio trova un inverso modulare con l'algoritmo di Euclide esteso e corregge la soluzione parziale perché rispetti una condizione in più, finché tutte le congruenze sono coperte. Tutti i calcoli usano numeri interi, quindi non si arrotonda nulla lungo il percorso. L'errore più comune è usare moduli con un fattore in comune, come 4 e 6: un sistema così può non avere soluzioni o averne diverse, perciò viene rifiutato invece di essere indovinato. Un altro è dimenticare che la risposta rappresenta una classe di numeri, non un valore unico.
Come il CRT successivo calcola esattamente la soluzione e dove viene usato
Internamente il motore parte dalla prima congruenza e incorpora ripetutamente la successiva. Data una soluzione parziale x congruente a x0 modulo m e una nuova congruenza x congruente ad a modulo n con m e n coprimi, calcola l'inverso modulare di m modulo n con l'algoritmo euclideo esteso, lo moltiplica per la differenza ridotta a meno x0 e incrementa x0 di m volte tale passo per ottenere la nuova soluzione parziale modulo m per n.
Gli studenti incontrano questa costruzione quando i manuali chiedono di ricostruire un numero dai suoi resti; gli insegnanti possono generare soluzioni per schede di congruenze simultanee senza fidarsi di calcolatori opachi; gli sviluppatori usano lo stesso contratto per validare ricostruzioni modulari in demo RSA didattiche, dove il CRT con fattori primi coprimi accelera la decifratura, e per costruire vettori di test deterministici per librerie di aritmetica modulare.
Casi d'uso
Congruenze simultanee per compiti e gare
Risolva sistemi da manuale come x ≡ 2 mod 3, x ≡ 3 mod 5, x ≡ 2 mod 7 e ottenga la soluzione minima non negativa con il prodotto dei moduli.
Domande frequenti
Quanto costa il calcolatore del teorema cinese del resto?
È gratuito nel Suo browser su questa pagina.
I moduli devono essere coprimi a due a due?
Sì. Questo calcolatore richiede moduli coprimi a due a due, il che garantisce una soluzione unica modulo il loro prodotto.
L'algoritmo è randomizzato?
No. Usa il CRT successivo deterministico con gcd interi esatti e inversi modulari. Gli stessi resti e moduli producono sempre la stessa soluzione minima non negativa.
I resti possono essere negativi?
Sì. Ogni resto negativo viene prima ridotto modulo il proprio modulo, quindi è trattato come il valore equivalente compreso tra zero e il modulo meno uno, e il sistema si risolve normalmente.
Perché c'è una sola risposta sotto il prodotto dei moduli?
Perché il teorema garantisce un'unica classe di soluzioni modulo quel prodotto quando i moduli sono coprimi a due a due. Nell'esempio classico ogni altra soluzione differisce da 23 per un multiplo di 105, quindi 23 è la più piccola.
Strumenti correlati
Per sviluppatori — accesso via API
Tutto quello che vedi in questa pagina è disponibile anche via API. Questa sezione è per i team che vogliono integrarlo nei propri sistemi; chi non ne ha bisogno può semplicemente usare lo strumento qui sopra.
Endpoint
Autenticazione con Bearer token: un POST mette in coda l'attività e il risultato arriva via webhook o link firmato.
Chiamala dal tuo 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)Esempio di richiesta
{
"remainders": [
2,
3,
2
],
"moduli": [
3,
5,
7
]
}Esempio di risposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "math.chinese_remainder",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}L'API è asincrona: ricevi subito un task_id e puoi fare polling fino a 1 richiesta al secondo.
Prezzi
Prezzo pubblicato, senza token né crediti. Se l'attività fallisce, non paghi.
Limiti
max_items | 64 |
Errori
| HTTP | Codice | Significato |
|---|---|---|
401 | unauthorized | Chiave API mancante o non valida: controlla l'header Authorization. |
402 | insufficient_balance | Credito esaurito: ricarica per continuare a eseguire attività. |
404 | unknown_type | Tipo di attività sconosciuto: controlla il campo type della richiesta. |
429 | rate_limited | Troppe richieste in poco tempo: rallenta e riprova tra qualche secondo. |
Note tecniche
Il calcolatore del teorema cinese del resto risolve un sistema di congruenze simultanee — x congruente a ciascun resto a_i modulo ciascun modulo n_i — quando i moduli sono coprimi a due a due, e restituisce la soluzione minima non negativa insieme al prodotto dei moduli. Se una coppia di moduli condivide un fattore comune, la richiesta fallisce con un chiaro errore invalid_input invece di una risposta improvvisata.
Cosa garantisce il teorema cinese del resto per moduli coprimi
Il celebre esempio scolastico, x congruente a 2 modulo 3, x congruente a 3 modulo 5 e x congruente a 2 modulo 7, dà x uguale a 23 modulo 105, e 23 è la soluzione minima non negativa che questo strumento restituisce. I sistemi i cui moduli non sono coprimi a due a due vengono rifiutati anziché risolti, il che mantiene il contratto semplice e onesto. Il classico teorema cinese del resto afferma che se i moduli n_1 fino a n_k sono coprimi a due a due — ossia ogni coppia non condivide alcun fattore comune maggiore di uno — allora esiste esattamente una classe di resto modulo il prodotto di tutti gli n_i che soddisfa contemporaneamente ogni congruenza x congruente ad a_i modulo n_i. In caso di successo la risposta JSON include x, il modulus (che qui equivale al prodotto dei moduli in ingresso), il prodotto stesso, i resti ridotti nell'intervallo canonico da zero a n_i meno uno, una copia dei moduli e il numero di congruenze.
Come vengono validati gli input e perché i moduli non coprimi vengono rifiutati
Si tratta di una scelta progettuale deliberata, non di un limite della matematica: i sistemi CRT generali con fattori condivisi possono essere incoerenti, e piuttosto che cambiare silenziosamente semantica questo calcolatore mantiene un'unica promessa — moduli coprimi a due a due in ingresso, soluzione minima non negativa in uscita. I campi accettati sono remainders e moduli, due array JSON di interi di uguale lunghezza, con gli alias a, ai e residues che rimandano a remainders, e n, ni e mods che rimandano a moduli, così moduli web, query string e notebook legacy possono condividere un unico contratto. Ogni voce può essere un intero JSON o una stringa decimale con segno iniziale opzionale; frazioni, notazione scientifica e spazi interni vengono rifiutati. Ogni modulo deve essere un intero positivo sicuro, i resti possono essere negativi e vengono ridotti nell'intervallo canonico prima della combinazione, e si accettano al massimo sessantaquattro congruenze per richiesta. Prima di qualsiasi risoluzione, il motore controlla ogni coppia di moduli con l'algoritmo euclideo del gcd; se una coppia ha un gcd maggiore di uno, la richiesta fallisce con invalid_input e un messaggio che indica la coppia incriminata, ad esempio che il gcd di 4 e 6 è 2. Array mancanti, lunghezze diverse, voci non intere e prodotti che superano l'intervallo degli interi sicuri falliscono anch'essi con invalid_input, così una cella errata di un foglio di calcolo non diventa mai una risposta sbagliata silenziosa.
Come il CRT successivo calcola esattamente la soluzione e dove viene usato
In questa pagina il lavoro avviene interamente nel Suo browser gratuitamente; tramite l'API ogni risoluzione riuscita costa $0.002, la validazione fallita non viene addebitata e nulla viene conservato dopo la risposta.
Casi di integrazione
Demo didattiche di RSA e ricostruzione modulare
Ricomponga i resti modulo fattori coprimi in un unico intero spiegando le accelerazioni RSA basate sul CRT, enigmi di calendario o isomorfismi di anelli.
Fixture di test deterministiche per librerie modulari
Generi soluzioni CRT riproducibili per test unitari e asserzioni CI senza incorporare tabelle calcolate a mano che divergono dall'implementazione.
Domande tecniche
Cosa succede se i moduli non sono coprimi?
La richiesta fallisce con invalid_input e un messaggio come 'Moduli non coprimi a due a due: gcd(4, 6) = 2', invece di improvvisare una risposta con una semantica diversa.
Sono ammessi resti negativi?
Sì. I resti possono essere negativi; vengono ridotti nell'intervallo da zero a n_i meno uno prima della combinazione CRT. I moduli devono essere interi positivi.