Indice di un numero rispetto a una radice primitiva modulo n

L’indice di un numero $ x $ rispetto a una radice primitiva $ r $ modulo n è semplicemente il numero di volte $ m $ che bisogna elevare la radice primitiva per ottenere quel numero. $$ r^m \equiv x \pmod{n} $$

In altre parole, l'indice mi dice quindi "quanto grande" deve essere l'esponente di una radice primitiva modulo n per ottenere il numero desiderato.

Ad esempio, nel modulo $ n=14 $ una radice primitiva è il numero $ r = 5 $:

$ 5^0 \equiv 1 \pmod{14} $ Quindi, l'indice di 1 è 0
$ 5^1 \equiv 5 \pmod{14} $ , l'indice di 5 è 1
$ 5^2 \equiv 11 \pmod{14} $ , l'indice di 11 è 2
$ 5^3 \equiv 13 \pmod{14} $ l'indice di 13 è 3
$ 5^4 \equiv 9 \pmod{14} $ , l'indice di 9 è 4
$ 5^5 \equiv 3 \pmod{14} $ , l'indice di 3 è 5**

Le proprietà degli indici

L'indice di un numero rispetto a una radice primitiva $ r $ ha diverse proprietà fondamentali che rendono più semplice il calcolo in aritmetica modulare.

L'indice di 1 è sempre zero
L'indice della costante 1 è sempre 0, perché qualsiasi numero elevato alla potenza zero è uguale a 1. \[ \text{ind}_r(1) = 0 \]
Esempio. Se $ r = 5 $ è una radice primitiva modulo 14, allora $ 5^0 = 1 $, quindi $ \text{ind}_5(1) = 0 $.
Il numero e il suo indice sono collegati
Se $ r^h \equiv m \pmod{n} $, allora $ h $ è proprio $ \text{ind}_r(m) $. Questo significa che per trovare l'indice di un numero basta determinare a quale esponente della radice primitiva corrisponde. \[ r^{\text{ind}_r(m)} \equiv m \pmod{n}
\]
Esempio. Se $ r = 5 $ e $ 5^3 \equiv 13 \pmod{14} $, allora $ \text{ind}_5(13) = 3 $.
L’indice si moltiplica quando il numero viene elevato a una potenza
Se elevo un numero a una potenza $ h $, il suo indice si moltiplica per $ h $: \[ \text{ind}_r(m^h) = h \cdot \text{ind}_r(m) \pmod{\varphi(n)} \] Dove $ \varphi(n) $ è la funzione di Eulero che conta i numeri coprimi con $ n $.

Esempio. Se $ \text{ind}_5(3) = 5 $, allora \[ \text{ind}_5(3^2) = 2 \cdot 5 = 10 \pmod{6} \equiv 4 \]
Il prodotto di due numeri ha un indice che è la somma degli indici
Se moltiplichiamo due numeri, gli indici si sommano: \[ \text{ind}_r(m \cdot m') = \text{ind}_r(m) + \text{ind}_r(m') \pmod{\varphi(n)} \] Dove $ \varphi(n) $ è la funzione di Eulero.
Esempio. Se $ \text{ind}_5(3) = 5 $ e $ \text{ind}_5(11) = 2 $, allora: \[ \text{ind}_5(3 \cdot 11) = 5 + 2 = 7 \pmod{6} \equiv 1 \]

Queste proprietà sono molto utili per risolvere equazioni modulari, semplificando calcoli altrimenti complessi.

Esempio

Considero l’equazione modulare:

\[ 3x^5 \equiv 11 \pmod{14} \]

Come posso risolverla?

Sapendo che $ 3 $ e $ 11 $ hanno certi indici rispetto alla radice primitiva $ r = 5 $ modulo 14

$$ \text{ind}_5(3) = 5 $$

$$ \text{ind}_5(11) = 2 $$

Allora, posso scrivere l’equazione $ 3x^5 \equiv 11 \pmod{14} $ in termini di indici:

\[ \text{ind}_5(3) + \text{ind}_5(x^5) \equiv \text{ind}_5(11) \pmod{\varphi(14)} \]

\[ 5 + \text{ind}_5(x^5) \equiv 2 \pmod{\varphi(14)} \]

Applico la proprietà $ \text{ind}_5(x^5) = 5 \cdot \text{ind}_5(x) $

\[ 5 + 5 \cdot \text{ind}_5(x) \equiv 2 \pmod{\varphi(14)} \]

Introduco una variabile temporanea $ y = \text{ind}_5(x) $

\[ 5 + 5 y \equiv 2 \pmod{\varphi(14)} \]

Sapendo che ci sono $ \varphi(14)=6 $ numeri coprimi con 14 ossia 1, 3, 5, 9, 11, 13.

\[ 5 + 5y \equiv 2 \pmod{6} \]

Sottraggo 5 da entrambi i lati:

\[ 5 + 5y - 5 \equiv 2 -5 \pmod{6} \]

\[ 5y \equiv -3 \equiv 3 \pmod{6}. \]

Risolvo questa congruenza per $ y $ cercando il valore che mi dà $ y \equiv 3 \pmod{6} $.

$ y = 0 \Rightarrow 5(0) = 0 \not\equiv 3 \pmod{6} $
$ y = 1 \Rightarrow 5(1) = 5 \not\equiv 3 \pmod{6} $
$ y = 2 \Rightarrow 5(2) = 10 \equiv 4 \pmod{6} $
$ y = 3 \Rightarrow 5(3) = 15 \equiv 3 \pmod{6} $ ✅

Quindi, $ y \equiv 3 \pmod{6} $.

$$ y = \text{ind}_5(x) = 3 $$

Questo significa che $ x $ è il numero il cui indice $ ind}_5(x) = 3 $ della radice $ r=5 $, cioè

$$ x = 5^3 \equiv 13 \pmod{14} $$

Quindi, la soluzione dell’equazione è $ x \equiv 13 \pmod{14} $.

E così via.