Teorema di esistenza delle radici primitive nei numeri primi

Se $ p $ è un numero primo, allora esiste almeno un numero $ g $ tale che $ g $ è una radice primitiva modulo $ p $.

Questo significa che il gruppo moltiplicativo $ (\mathbb{Z}/p\mathbb{Z})^* $, formato dagli interi invertibili modulo $ p $, è ciclico.

In altre parole, tutti i numeri primi dispari $ p $ hanno almeno una radice primitiva modulo p.

Questo è un caso particolare di un teorema generale sull'esistenza delle radici primitive nei numeri primi.

Ogni numero primo $ p $ ha esattamente $ \varphi(p-1) $ radici primitive modulo $ p $, dove $ \varphi(p-1) $ è la funzione di Eulero che restituisce il numero di numeri coprimi con p-1 da 1 a p-1. $$ \phi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdot \cdots \cdot \left(1 - \frac{1}{p_k}\right) $$

Quindi un numero primo $ p $ può avere più radici primitive e il loro numero dipende da $ \varphi(p-1) $.

Ad esempio, il numero primo $ p = 7 $ ha solo 2 radici primitive perché $ \varphi(6) = 2 $ mentre il numero primo $ p = 17 $ ha 8 radici primitive, poiché $ \varphi(16) = 8 $.

Perché esiste sempre una radice primitiva modulo un numero primo $ p $? Il gruppo moltiplicativo $ (\mathbb{Z}/p\mathbb{Z})^* $ ha esattamente $ \varphi(p) = p - 1 $ elementi. Nella teoria dei gruppi, quando un gruppo ciclico ha ordine $ p - 1 $, allora esiste un elemento generatore. Questo elemento generatore è proprio la radice primitiva modulo $ p $, perché le sue potenze generano tutti gli elementi del gruppo.

Un esempio pratico

In questi esempi cerco le radici primitive di alcuni numeri primi:

Esempio 1

Gli elementi invertibili modulo $ p = 3 $ sono $ \{1,2\} $.

La potenza di 2 genera i seguenti elementi:

$$ 2^1 \equiv 2 \pmod{3} $$

$$ 2^2 \equiv 1 \pmod{3} $$

Dato che $ 2 $ genera l'insieme, allora $ g = 2 $ è una radice primitiva modulo 3.

Nota. Per trovare il numero delle radici posso anche usare il criterio di Eulero. $$ \phi(3-1) = 2 \cdot \left(1 - \frac{1}{2}\right) = 2 \cdot \frac{1}{2} = 1 $$ In questo caso il numero $ p=3 $ ha una sola radice primitiva ossia 2.

Esempio 2

Gli elementi invertibili di $ p =5 $ sono $ \{1,2,3,4\} $.

Analzzo la potenza di 2:

$$ 2^1 \equiv 2 \pmod{5} $$

$$ 2^2 \equiv 4 \pmod{5} $$

$$ 2^3 = 8 \equiv 3 \pmod{5} $$

$$ 2^4 = 16 \equiv 1 \pmod{5} $$

Dato che 2 genera tutto il gruppo, il numero 2 è una radice primitiva di p=5.

Analizzo la potenza di 3

$$ 3^1 \equiv 3 \pmod{5} $$

$$ 3^2 = 9 \equiv 4 \pmod{5} $$

$$ 3^3 = 27 \equiv 2 \pmod{5} $$

$$ 3^4 = 3^2 \cdot 3^2 = 4 \cdot 4 = 16 \equiv 1 \pmod{5} $$

Anche il numero 3 genera tutto il gruppo, quindi il numero 3 è un'altra radice primitiva di p=5.

Analizzo la potenza di 4

$$ 4^1 \equiv 4 \pmod{5} $$

$$ 4^2 = 16 \equiv 1 \pmod{5} $$

In questo caso, il numero 4 non è una radice primitiva di p=5 perché non genera l'intero gruppo.

Verifica. In base al criterio di Eulero il numero $ p = 5 $ ha effettivamente due radici primitive. $$ \phi(5-1) = \phi(4) = 4 \cdot \left(1 - \frac{1}{2}\right) = 4 \cdot \frac{1}{2} = 2$$

Esempio 3

Gli elementi invertibili di $ p = 7 $ sono $ \{1,2,3,4,5,6\} $.

Le potenza di 2 sono:

$$ 2^1 \equiv 2 \pmod{7} $$

$$ 2^2 \equiv 4 \pmod{7} $$

$$ 2^3 = 8 \equiv 1 \pmod{7} $$

Il numero 2 non è un generatore del gruppo.

Le potenza di 3 sono:

$$ 3^1 \equiv 3 \pmod{7} $$

$$ 3^2 = 9 \equiv 2 \pmod{7} $$

$$ 3^3 = 27 \equiv 6 \pmod{7} $$

$$ 3^4 = 3^2 \cdot 3^2 = 2 \cdot 2 \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} $$

Siccome 3 genera tutti i numeri invertibili, $ g = 3 $ è una radice primitiva di $ p = 7 $.

Quindi, il numero 3 è una radice primitiva del gruppo.

Le potenze di 4 sono:

$$ 4^1 \equiv 4 \pmod{7} $$

$$ 4^2 = 16 \equiv 2 \pmod{7} $$

$$ 4^3 = 64 \equiv 1 \pmod{7} $$

Il numero 4 non è un generatore del gruppo.

Le potenze di 5 sono:

$$ 5^1 \equiv 5 \pmod{7} $$

$$ 5^2 = 25 \equiv 4 \pmod{7} $$

$$ 5^3 = 5^2 \cdot 5^1 = 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^3 \cdot 5^2 = 6 \cdot 4 = 24 \equiv 3 \pmod{7} $$

$$ 5^6 = 5^3 \cdot 5^3 = 6 \cdot 6 = 36 \equiv 1 \pmod{7} $$

Quindi, il numero 5 è un'altra radice primitiva del gruppo.

Le potenze di 6 sono:

$$ 6^1 \equiv 6 \pmod{7} $$

$$ 6^2 = 36 \equiv 1 \pmod{7} $$

Il numero 6 non è un generatore del gruppo.

Questi esempi dimostrano che ogni numero primo ha almeno una radice primitiva.

Verifica. In base al criterio di Eulero il numero $ p = 7 $ ha effettivamente due radici primitive. $$ \phi(7-1) = \phi(6) = 6 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{3}\right) = 6 \cdot \frac{1}{2} \cdot \frac{2}{3} = 2$$

E così via.