Piccolo teorema di Fermat
Inserisca una base e un modulo e veda se a^(n−1) mod n vale 1: con 2 e 7 il resto di 2^6 è 1, con 2 e 15 è 4. Le serve per controllare i compiti o scovare un controesempio composto. Gratis nel suo browser.
- Gratis
- Funziona nel suo browser
- Senza registrazione
- I suoi dati restano sul dispositivo
Esegui gratis nel browser
Esempio risolto
- A
- 2
- N
- 7
- Risultato
- 1
- Primo testo
- 2
- N
- 7
- Esponente
- 6
Il piccolo teorema di Fermat è l’affermazione chiara dell’aritmetica modulare: se n è primo e la base a non è divisibile per n, allora a elevato a n meno uno è congruente a uno modulo n. Studenti, tutor e sviluppatori hanno spesso bisogno di valutare rapidamente quel residuo esatto di potenza—non un riassunto della dimostrazione—per controllare compiti, esplorare controesempi composti o collaudare routine modulari. Questo verificatore del piccolo teorema di Fermat accetta gli interi a e n, rifiuta la coppia quando gcd(a, n) non è uno e altrimenti restituisce a^(n−1) mod n con un flag booleano che Le indica se il resto è uno.
Cosa afferma il piccolo teorema di Fermat e cosa calcola questo strumento
Nella forma usuale da manuale, il piccolo teorema di Fermat afferma: se n è un numero primo e a è un intero non divisibile per n, allora a alla potenza n meno uno è congruente a uno modulo n. Scritto con l’operatore modulare che i programmatori usano ogni giorno, ciò significa a^(n−1) mod n uguale a 1 ogni volta che valgono quelle ipotesi. Lei fornisce la base a e il modulo n.
Il verificatore richiede innanzitutto che n sia un intero almeno pari a due, perché la riduzione modulare con modulo inferiore a due non è un contratto utile in aula. Poi richiede che il massimo comun divisore di a e n sia uno—l’ipotesi di coprimalità che coincide con l’enunciato classico quando n è primo (a non divisibile per n) e resta sensata per n composto quando vuole esplorare cosa accade fuori dalla garanzia del teorema.
Quando entrambi i controlli passano, il motore esegue l’esponenziazione modulare binaria (elevazione al quadrato e moltiplicazione) su BigInt affinché i prodotti intermedi restino esatti anche se l’esponente n−1 è grande.
In classe, per i compiti e i controesempi
I docenti usano un verificatore del piccolo teorema di Fermat affinché gli studenti verifichino a mano a^(p−1) mod p su primi piccoli prima di scrivere una dimostrazione, e affinché provino di proposito n composti e vedano che il resto non è sempre uno. I generatori di esami e i plugin LMS necessitano di un oracolo deterministico che rifiuti input non coprimi invece di restituire in silenzio un resto che confonda la correzione.
I notebook dei corsi di crittografia spesso richiedono un unico passo esatto di potenza modulare per introdurre chiavi RSA giocattolo o illustrare perché compare l’esponente n−1 nella teoria elementare dei numeri prima che il teorema di Eulero generalizzi il racconto con φ(n). Quando in seguito le serviranno il teorema di Eulero con φ(n), inverse modulari o scomposizioni col teorema cinese del resto, chiami quelle capacità separate; questa resta la landing dedicata a Fermat a^(n−1) mod n così l’intento di ricerca e la forma della risposta restano chiari.
Casi d'uso
Controlli FLT per compiti e aula
Gli studenti inseriscono la base a e un primo n per confermare che a^(n−1) mod n vale 1, oppure provano n composti per vedere quando il resto non è 1.
Test unitari per la potenza modulare
Gli script fissano residui noti come 2^6 mod 7 = 1 e 2^14 mod 15 = 4 senza reimplementare BigInt square-and-multiply in ogni linguaggio.
Domande frequenti
Perché gcd(a, n) deve essere uguale a 1?
Il piccolo teorema di Fermat è enunciato per basi coprime al modulo (equivalente a non divisibili dal primo n).
Un risultato pari a 1 dimostra che n è primo?
No. Quando n è primo e gcd(a,n)=1 il resto è sempre 1, ma i composti possono dare 1 per alcune basi. Usi uno strumento dedicato di primalità per quella domanda.
Come verifico il piccolo teorema di Fermat con base 2 e modulo 7?
Inserisca 2 come base e 7 come modulo. Lo strumento eleva 2 alla sesta potenza, divide per 7 e restituisce resto 1: il teorema vale per questo primo, come previsto.
Perché 2^14 mod 15 dà 4 e non 1?
Perché 15 non è primo e in quel caso il teorema non garantisce nulla. La base 2 non ha divisori comuni con 15, quindi lo strumento calcola il resto di 2 elevato alla 14 e ottiene 4: il 15 non supera la prova.
Posso usare una base negativa o un modulo molto grande?
Sì. Una base negativa viene prima ridotta modulo n, e il modulo deve solo essere un intero di almeno 2. La potenza si calcola elevando al quadrato e moltiplicando con numeri interi esatti, quindi anche con esponenti enormi il resto è esatto.
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/numth/fermat-little-check \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":2,"n":7}'const res = await fetch("https://api.kit.forhosting.com/numth/fermat-little-check", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 2,
"n": 7
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/fermat-little-check",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 2,
"n": 7
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/fermat-little-check", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":2,"n":7}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":2,"n":7}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/fermat-little-check", 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
{
"a": 2,
"n": 7
}Esempio di risposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.fermat_little_check",
"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.
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
La stessa logica pura BigInt alimenta lo strumento gratuito del browser e il percorso API a pagamento a $0.002 per richiesta riuscita, così le demo in aula e gli script di produzione non divergono mai su un residuo.
Cosa afferma il piccolo teorema di Fermat e cosa calcola questo strumento
La dimostrazione non è il prodotto di questo endpoint; il prodotto è il resto esatto di quella potenza. La risposta ripete a e n come stringhe decimali, riporta l’esponente n−1, il resto non negativo result, gcd come la stringa "1", un booleano congruent_to_one vero esattamente quando result vale 1, e una breve expression da stampare accanto alla risposta. Controllo classico con primo: a uguale a 2 e n uguale a 7 dà 2^6 mod 7 uguale a 1, quindi congruent_to_one è vero. Sonda classica con composto: a uguale a 2 e n uguale a 15 dà 2^14 mod 15 uguale a 4, quindi congruent_to_one è falso—esattamente il tipo di controesempio che mostra che a^(n−1) ≡ 1 non è, da solo, un certificato di primalità.
Contratto di input, errori e come leggere la risposta
Se n è minore di due, l’attività fallisce con un messaggio che indica che il modulo deve essere almeno due. Se gcd(a, n) non è uno, l’attività fallisce con un messaggio che nomina il gcd—ad esempio gcd(2, 4) uguale a 2—così chi chiama sa che la coppia è fuori dall’ipotesi di coprimalità invece di indovinare perché la potenza non è stata calcolata. Le basi negative sono accettate e ridotte nel sistema di residui non negativi modulo n prima dell’elevamento, in linea con l’aritmetica modulare standard. Invii un corpo JSON con POST e due campi interi obbligatori: a (alias base) e n (alias modulus, mod). Ogni campo può essere un numero JSON o una stringa di intero decimale; la forma stringa è preferita quando i valori escono dall’intervallo di interi sicuri di JavaScript. Frazioni, stringhe vuote, token non numerici e valori più lunghi di sessantaquattro cifre decimali falliscono con invalid_input e non vengono addebitati. In caso di successo ogni campo numerico del corpo è una stringa decimale tranne congruent_to_one, che è booleano, così i grandi interi transitano in JSON senza perdita di precisione. Abbini questo verificatore a uno strumento separato di fattorizzazione o primalità quando il flusso richiede più del residuo di potenza; questo endpoint risponde solo a^(n−1) mod n sotto il cancello di coprimalità per mantenere l’intento SEO focalizzato e la risposta minimale. Il prezzo è un $0.002 fisso per richiesta riuscita sull’unità item; la validazione fallita non consuma il saldo prepagato.
Demo in aula, sonde su composti e automazione API
Gli sviluppatori collegano l’API a test di proprietà che affermano a^(n−1) ≡ 1 per basi casuali coprime a un modulo primo noto, o a suite di regressione che fissano controesempi composti noti come 2^14 mod 15 uguale a 4. Mantenga a e n entro il limite di cifre pubblicato, fissi nei test il result in forma di stringa e il flag congruent_to_one, e otterrà residui riproducibili per compiti, piattaforme di tutoraggio e edge worker senza montare un intero sistema di algebra computazionale.
Casi di integrazione
Oracoli di correzione automatica LMS ed esami
Valuti voci di aritmetica modulare con un resto deterministico e rifiuti le coppie non coprime come non valide invece di inventare un payload di successo.
Domande tecniche
Cosa calcola questo verificatore del piccolo teorema di Fermat?
Dati interi a e n con n ≥ 2 e gcd(a,n)=1, restituisce a^(n−1) mod n e se quel resto vale 1 (congruent_to_one).
Cosa succede se n è composto?
Il verificatore calcola ancora a^(n−1) mod n quando gcd(a,n)=1. congruent_to_one può essere vero o falso; i casi falsi sono controesempi utili in aula.
Quanto costa il verificatore del piccolo teorema di Fermat?
Lo strumento nel browser è gratuito. Le richieste API usano il saldo prepagato KIT a $0.002 per chiamata riuscita; l’input non valido non viene addebitato.