Tutte le radici primitive modulo n

Prima stabilisce se il modulo appartiene a una famiglia che ammette radici primitive, quindi calcola la funzione phi di Eulero, trova un generatore e ricava tutti gli altri. La risposta comprende modulo, valore phi, quantità e lista completa delle radici. Valori inferiori a due e moduli privi di radici primitive producono un errore chiaro. La stessa aritmetica deterministica consente controlli rapidi e automazione riproducibile via API al costo di $0.002 per richiesta riuscita.

Significato dell’elenco completo delle radici primitive

Una radice primitiva modulo n è un residuo le cui potenze successive generano ogni classe invertibile modulo n. La parola fondamentale è «ogni»: un numero può essere coprimo con n e percorrere soltanto un sottogruppo proprio, quindi essere un’unità è necessario ma non sufficiente. Questa capacità restituisce tutti i rappresentanti positivi tra 1 e n meno 1 con ordine moltiplicativo esattamente phi(n). Per il modulo 14, per esempio, il gruppo delle unità contiene sei elementi e l’insieme completo dei generatori comprende due residui. La risposta indica n, la funzione phi di Eulero, il numero di radici primitive e l’array primitive_roots ordinato numericamente. Il conteggio offre un controllo utile: quando esistono radici primitive, il loro numero è phi(phi(n)). Il caso speciale 2 possiede correttamente la sola radice 1. Un modulo senza un generatore dell’intero gruppo viene rifiutato esplicitamente; un elenco vuoto nasconderebbe invece che il gruppo non è ciclico.

Come vengono verificate esistenza e generatori

Le radici primitive non esistono per ogni modulo. Il teorema di classificazione afferma che il gruppo moltiplicativo modulo n è ciclico esattamente quando n è 2, 4, una potenza di un primo dispari oppure il doppio di tale potenza. Il calcolatore fattorizza n e controlla questa condizione strutturale prima della ricerca. Per un modulo ammesso calcola phi(n), fattorizza l’ordine del gruppo e verifica le unità candidate con l’esponenziazione modulare. Un candidato g ha ordine pieno phi(n) se, per ogni divisore primo distinto q di phi(n), g elevato a phi(n) diviso q non è congruo a 1 modulo n. Trovato un g, tutte le radici sono le potenze g elevato a k con k coprimo con phi(n). L’implementazione enumera tali esponenti, calcola residui esatti e ordina il risultato. Non usa casualità, tabelle esterne, rete o ora corrente; lo stesso input genera sempre lo stesso contenuto numerico.

Uso del risultato in matematica e nel software

Gli elenchi completi servono quando un problema richiede più della minima radice primitiva. Gli studenti possono confrontare i residui restituiti con tabelle di potenze compilate a mano e capire perché il numero dei generatori è phi(phi(n)). I docenti possono preparare soluzioni che includano ogni risposta valida. Chi sviluppa software può generare fixture per routine sull’ordine moltiplicativo, verificare codice di enumerazione o selezionare fra più generatori secondo una regola applicativa separata. Anche gli errori sono istruttivi: provare i moduli 8 o 15 mostra che molti numeri composti comuni hanno gruppi di unità non ciclici pur contenendo numerosi residui invertibili. L’input è limitato a 10,000 perché la risposta richiesta è esaustiva e può contenere molte radici; il limite rende prevedibili rendering, dimensione dell’API e tempo di esecuzione. Inserisca n come intero o stringa decimale semplice. Ogni richiesta riuscita costa $0.002; gli input non supportati o malformati vengono segnalati chiaramente.