Verificatore di coprimalità

Il verificatore di coprimalità risponde a una domanda base di teoria dei numeri: due interi condividono solo uno come divisore comune positivo? Fornisci gli interi a e b e lo strumento restituisce sia il massimo comun divisore sia un flag booleano coprime che è true esattamente quando quell'mcd è uguale a uno. Il motore usa il classico algoritmo euclideo su valori assoluti, così il risultato è esatto, deterministico e privo di derive in virgola mobile. Non chiama mai la rete, non campiona mai casualità e non dipende mai dall'orologio.

Cosa significa coprimo e cosa contiene la risposta

Due interi sono coprimi, o primi tra loro, quando il loro unico divisore comune positivo è uno. Equivalentemente, l'mcd di a e b è uguale a uno. Esempi classici includono otto e quindici, i cui divisori non si sovrappongono oltre l'uno, e quattordici e ventuno, che condividono sette.

Questo verificatore restituisce gli interi originali a e b come interpretati, l'mcd positivo, e un campo booleano coprime che è true se e solo se quell'mcd è esattamente uno. Il caso speciale a uguale a zero e b uguale a zero viene respinto perché l'mcd di zero e zero non è definito in questo contesto e la coprimalità non può essere decisa. Al contrario, zero e cinque è valido: l'mcd è cinque e coprime è false.

Gli input negativi sono ammessi e vengono ridotti tramite valori assoluti, coerentemente con la consueta convenzione matematica secondo cui l'mcd è non negativo. Se ti servono i fattori primi di un singolo intero invece di un test di mcd a coppie, usa uno strumento di fattorizzazione; questa pagina risponde solo alla domanda sulla coprimalità e l'mcd di due interi.

Come vengono letti gli input e come l'mcd euclideo resta esatto

Il segno più o meno iniziale opzionale è ammesso; spazi incorporati, prefissi esadecimali e notazione esponenziale vengono respinti così che una cella sbagliata non diventi un flag errato. Il motore resta entro gli interi sicuri di JavaScript, il che è più che sufficiente per problemi in classe, gare di programmazione e la maggior parte delle verifiche applicate su inversi modulari o rapporti semplificati.

Internamente i valori assoluti vengono passati all'algoritmo euclideo: sostituisci ripetutamente la coppia con il maggiore e il resto finché il resto non è zero, poi l'ultimo resto diverso da zero è l'mcd. Questa procedura è secolare, richiede solo un pugno di divisioni per input ordinari e non approssima mai. Non c'è alcun passaggio in virgola mobile che potrebbe arrotondare un quasi-intero in una falsa dichiarazione di coprimalità.

Dove si usano i controlli di coprimalità nello studio, nell'intuizione crittografica e nel codice

Gli studenti incontrano le coppie coprime quando riducono frazioni, quando dimostrano che il toziente di Eulero conta gli interi fino a n coprimi con n, e quando un inverso modulare esiste proprio perché il coefficiente e il modulo sono coprimi. Gli insegnanti possono generare chiavi di risposta per schede di esercizi senza fidarsi di app di calcolo opache che nascondono l'mcd.

Gli sviluppatori usano lo stesso contratto per validare che due valori seme siano primi tra loro prima di costruire un generatore congruenziale lineare, per pre-verificare relazioni e e phi in stile RSA in dimostrazioni educative, o per bloccare un passaggio di normalizzazione di frazioni in pipeline di dati. La pratica in gare ha spesso bisogno di una fonte veloce e offline di risposte su mcd e coprimalità così le soluzioni possono essere verificate senza scaricare tabelle.

Abbinalo alla fattorizzazione in primi quando ti servono le potenze prime dietro un singolo intero, e a uno strumento per l'n-esimo primo quando ti servono ranghi invece di divisori a coppie.