Radice primitiva modulo n
Dati due numeri \( n \) e \( r \) interi positivi e coprimi, ossia tali che \( MCD(r, n) = 1 \), si dice che \( r \) è una radice primitiva modulo \( n \) se il sottogruppo ciclico \( G(n, r) \) generato da \( r \) ha ordine massimo \( \varphi(n) \). Dove \( \varphi(n) \) è la funzione di Eulero che conta quanti interi minori di \( n \) sono coprimi con \( n \).
In altre parole, \( r \) è una radice primitiva modulo \( n \) se le sue potenze modulo \( n \) generano tutti gli elementi invertibili di \( \mathbb{Z}_n \), ossia l'intero gruppo \( U(\mathbb{Z}_n) \).
Se \( r \) è una radice primitiva modulo \( n \), si dice anche che è un generatore del gruppo \( U(\mathbb{Z}_n) \).
Un esempio pratico
Considero il numero intero \( n = 4 \).
Gli interi coprimi con \( 4 \) sono \( \{1,3\} \) che formano un gruppo rispetto all’operazione di moltiplicazione modulo \( 4 \).
\[ U(\mathbb{Z}_4) = \{1, 3\} \]
Una radice primitiva modulo \( n \) è un elemento che genera il gruppo \( U(\mathbb{Z}_n) \), ossia un numero \( r \) tale che le sue potenze coprano tutti gli elementi del gruppo.
La funzione di Eulero del numero \( n = 4 \) conta tutti gli interi coprimi con \( n \) da 1 a 4. In questo caso sono due ossia 1 e 3.
$$ \varphi(4) = 2 $$
Devo verificare se \( 3 \) è una radice primitiva:
$$ 3^1 \equiv 3 \pmod{4} $$
$$ 3^2 \equiv 9 \equiv 1 \pmod{4} $$
Le potenze di \( 3 \) generano tutto \( U(\mathbb{Z}_4 = \{1, 3\}) \), quindi \( 3 \) è una radice primitiva modulo \( 4 \).
L'ordine del sottogruppo ciclico di \( 3^2 \) è 2 ed è uguale al numero dei coprimi con \( 4 \) ossia $ \varphi(4) = 2 $.
Nota. In un gruppo ciclico l'ordine di un elemento $ x $ è il più piccolo $k $ tale che $ x^k \equiv 1 \pmod{n} $. In questo caso è 2 perché $$ 3^2 \equiv 9 \equiv 1 \pmod{4} $$
Esempio 2
Considero il numero \( n = 8 \).
Il gruppo dei numeri coprimi con \( 8 \) è \( U(\mathbb{Z}_8) = \{1,3,5,7\} \).
In questo caso si tratta di un gruppo non ciclico, perché non c'è nessun numero le cui potenze generino tutto il gruppo.
- L'elemento 1 ha sempre ordine 1 $$ 1^1 = 1 \equiv 1 \pmod{8} $$
- L'elemento 3 ha ordine 2 $$ 3^1 \equiv 3 \pmod{8} $$ $$ 3^2 = 9 \equiv 1 \pmod{8} $$
- L'elemento 5 ha ordine 2 $$ 5^1 \equiv 5 \pmod{8} $$ $$ 5^2 = 25 \equiv 1 \pmod{8} $$
- L'elemento 7 ha ordine 2 $$ 7^1 \equiv 7 \pmod{8} $$ $$ 7^2 = 49 \equiv 1 \pmod{8} $$
Poiché il massimo ordine è \( 2 \) (e non \( \varphi(8) = 4 \)), non esistono radici primitive modulo 8.
Note aggiuntive
Alcune osservazioni e note personali sulle radici primitive modulo n.
- Se una radice primitiva esiste, allora ce ne sono \( \varphi(\varphi(n)) \).
Se esiste una radice primitiva modulo \( n \), allora ne esistono esattamente \( \varphi(\varphi(n)) \), ottenibili come potenze della radice primitiva. Pertanto, individuata una radice primitiva modulo n, è possibile determinare quante altre radici primitive esistono nello stesso modulo. Per trovarle, basta considerare le potenze $ g^m \pmod{n} $, dove \( m \) è un esponente coprimo con $ \varphi(n) $.
Esempio. Per \( n = 7 \) esistono \( \varphi(7) = 6 \) numeri coprimi con \( n \). Il numero \( 3 \) è una radice primitiva modulo \( 7 \) perché: $$ 3^1 \equiv 3 \pmod{7} $$ $$ 3^2 = 9 \equiv 2 \pmod{7} $$ $$ 3^3 = 27 \equiv 6 \pmod{7} $$ $$ 3^4 = 81 \equiv 4 \pmod{7} $$ $$ 3^5 = 3^2 \cdot 3^3 = 2 \cdot 6 = 12 \equiv 5 \pmod{7} $$ $$ 3^6 = 3^3 \cdot 3^3 = 6 \cdot 6 = 36 \equiv 1 \pmod{7} $$ Poiché \( 3 \) genera tutto \( U(\mathbb{Z}_7) \), è una radice primitiva. Esistono allora \( \varphi( \varphi(7) ) = \varphi( 6) = 2 \) radici primitive modulo \( 7 \), ottenute scegliendo esponenti \( m \) tali che \( MCD(m,6) = 1 \), cioè le potenze \( 3^1 = 3 \pmod{7} \) e \( 3^5 = 5 \pmod{7} \). Già conosco che 3 è un generatore del gruppo ciclico. Verifico se anche 5 lo è. $$ 5^1 \equiv 5 \pmod{7} $$ $$ 5^2 = 25 \equiv 4 \pmod{7} $$ $$ 5^3 = 5^2 \cdot 5 = 4 \cdot 5 = 20 \equiv 6 \pmod{7} $$ $$ 5^4 = 5^2 \cdot 5^2 = 4 \cdot 4 = 16 \equiv 2 \pmod{7} $$ $$ 5^5 = 5^2 \cdot 3 = 4 \cdot 6 = 24 \equiv 3 \pmod{7} $$ $$ 5^6 = 5^3 \cdot 5^3 = 6 \cdot 6 = 36 \equiv 1 \pmod{7} $$ Come previsto anche anche 5 è un generatore del gruppo ciclico ed è una radice primitiva modulo 7.
- Tutti i primi dispari hanno almeno una radice primitiva
Se \( n \) è un numero primo, allora esistono sempre radici primitive modulo \( n \). Questo significa che esiste almeno un numero intero minore di \( n \) i cui successivi multipli modulari generano tutti gli elementi invertibili di \( \mathbb{Z}_n \).Ad esempio, per \( n = 7 \), il gruppo degli elementi invertibili modulo \( 7 \) è \( U(\mathbb{Z}_7) = \{1, 2, 3, 4, 5, 6\} \), e si può verificare che il numero \( 3 \) è una radice primitiva, in quanto le sue potenze coprono tutti gli elementi di \( U(\mathbb{Z}_7) \). In totale, esistono esattamente \( \varphi(\varphi(7)) = \varphi(6) = 2 \) radici primitive, che in questo caso sono \( 3 \) e \( 5 \).
- Per alcuni numeri composti non esistono radici primitive
Questo accade quando il gruppo \( U(\mathbb{Z}_n) \) non è ciclico, ossia quando nessun elemento ha ordine \( \varphi(n) \).Ad esempio, per \( n = 8 \), il gruppo \( U(\mathbb{Z}_8) = \{1, 3, 5, 7\} \) ha ordine \( \varphi(8) = 4 \), ma ogni elemento ha ordine al massimo \( 2 \) (ossia, elevandolo al quadrato si ottiene \( 1 \) modulo \( 8 \)). Poiché nessun elemento genera l’intero gruppo, non esistono radici primitive modulo 8.
- Criterio per l'esistenza di radici primitive
Un intero positivo \( n \) ha almeno una radice primitiva se e solo se \( n \) è uno dei seguenti:- \( n = 2 \)
- \( n = 4 \)
- \( n = p^h \), con \( p \) primo dispari e \( h \) un intero positivo
- \( n = 2p^h \), con \( p \) primo dispari e \( h \) un intero positivo
Esempio. Questo teorema classifica utti i numeri \( n \) per cui esiste almeno una radice primitiva modulo \( n \). Ad esempio, se \( n \) è una potenza di un numero primo dispari che rientra nel caso \( p^h \) (es. \( 3, 9, 27, 5, 25, 125, \dots \)), allora ha almeno una radice primitiva. Se \( n \) è il doppio di una potenza di un numero primo dispari \( n = 2p^h \) (es. \( 6, 10, 18, 50, 250, \dots \)), allora ha almeno una radice primitiva. Quindi, non tutti gli interi hanno una radice primitiva. Ad esempio, \( n = 6, 8, 12, 15 \) non hanno radici primitive perché non rientrano nei casi elencati nel teorema.
n Esiste almeno una radice primitiva? 2 ✅ Sì 3 ✅ Sì (caso \( p^h = 3^1 \)) 4 ✅ Sì 5 ✅ Sì (caso \( p^h = 5^1 \)) 6 ❌ No 7 ✅ Sì (caso \( p^h = 7^1 \)) 8 ❌ No 9 ✅ Sì (caso \( p^h = 3^2 \)) 10 ✅ Sì (caso \( 2p^h = 2 \cdot 5^1 \)) 11 ✅ Sì (caso \( p^h = 11^1 \)) 12 ❌ No 13 ✅ Sì (caso \( p^h = 13^1 \)) 14 ✅ Sì (caso \( 2p^h = 2 \cdot 7^1 \)) 15 ❌ No - Le radici primitive modulo \( p^2 \)
Dato un numero primo e dispari \( n \), se \( r \) è una radice primitiva modulo \( p \) ma non modulo \( p^2 \), allora il numero \( r + p \) è una radice primitiva modulo \( p^2 \).In altre parole, a partire da una radice primitiva \( r \) modulo \( p \) si può costruire una radice primitiva modulo \( p^2 \) semplicemente considerando \( r + p \). Questa radice primitiva è comune sia per \( p \) che per \( p^2 \). Quindi, non solo questo mi garantisce che esistono radici primitive modulo \( p^2 \), ma posso anche essere sicuro che almeno una di esse funzioni sia modulo \( p \) che modulo \( p^2 \).
Esempio
Se \( r = 2 \) è una radice primitiva modulo \( p = 3 \), allora posso costruire una radice primitiva modulo \( p^2 = 9 \) sapendo che \[ r + p = 2 + 3 = 5 \] E verificando i calcoli, il numero intero \( 5 \) è effettivamente una radice primitiva modulo \( 9 \). - Teorema di propagazione delle radici primitive alle potenze di un primo
Se \( r \) è una radice primitiva modulo \( p \) e modulo \( p^2 \), allora è automaticamente una radice primitiva modulo tutte le potenze \( p^h \) con \( h \geq 2 \). In altre parole, una volta che \( r \) ha il massimo ordine modulo \( p^2 \), continua ad averlo per tutte le potenze superiori di \( p \), quindi non serve trovare nuove radici primitive per ogni \( p^h \), basta usare la stessa.
Esempio. Considero un numero primo dispari \( p = 3 \), una radice primitiva modulo $ 3 $ è $ r = 2 $ che è anche una radice modulo $ 3^2=9 $. In base a questo teorema, $ r=2 $ è anche una radice primitiva per tutte le potenze successive modulo $ 3^3 $, $ 3^4 $, $ 3^5 $, ecc.
E così via.
